This program shows how to convert an infix expression to postfix expression. Before proceeding to program, first understand what is difference between infix expression and postfix expression. Infix notation: X + Y. Operators are written in-between their operands. Postfix notation (also known as “Reverse Polish notation”) : X Y + . Operators are written after their operands.
An infix expression is accepted as input.The expression is pushed into the stack character by character.While pushing the expression,it is pushed as per the priority of the operands.Finally,when the expression is popped out of the stack,it gets converted into post fix expression.An algorithm to convert an infix expression to postfix expression.
Input: A bracket or unbracketed infix expression.
Output: A postfix expression.
Data structure : character type operator stack (opt_stk),
character type operand stck(opd_stk),
character type exp array to store an expression
Detail steps :
1. Initialize the stacks(set opd_top and opt_top to -1)
2. Read an infix expression into exp array.
3. Start processing given expression from first symbol till getting ‘\0? by using one symbol at a time. For each symbol (current token) do the following :
i) If current token is ‘(‘ then push it in opt_stk.
ii)If the current token is ‘)’ then
while opt_stk top operator is not an opening bracket do
begin
pop an operator from opt_stk and print it
end
pop an opening bracket from opt_stk.
iii) If current token is an operand then push it in opd_stk.
iv) If current token is an operand then
a) If an opt_stk is empty, push a current token in opt_stk
b) If a priority of current_token > a priority of opt_stk top operator then push a current token in opt_stk
c) While priority current token <= priority opt_stk top operator do
begin
pop an operator from opt_stk and print it
end
push a current token in opt_stk
4. While opt_stk is not empty do
begin
pop an operator from opt_stk and print it
end
include< stdio.h >
#include< conio.h >
#define max 50
void main()
{
char exp[100],opt_stk[max],ch;
int opt_top,i;
clrscr();
opt_top=-1;
printf(“\nEnter an infix exp \n”);
gets(exp);
//Process the expression by taking one token(symbol) at a time
for(i=0;exp[i]!=’\0′;i++)
{
if (exp[i]=='(‘)
{
push_opt(opt_stk,&opt_top,&exp[i]);
}
else if (exp[i]==’)’)
{
//while opt stk top operator is not an openeing
//bracket pop an operator and print it on screen
while(opt_stk[opt_top]!= ‘(‘)
{
pop_opt(opt_stk,&opt_top,&ch);
printf(“%c”,ch);
}
pop_opt(opt_stk,&opt_top,&ch); //skip ‘(‘
}
else
if (chk_opt(exp[i])==0) //current token is an operand
printf(“%c”,exp[i]);
else //current token is an operator
{
if(opt_top==-1) //opt stack is empty
{
push_opt(opt_stk,&opt_top,&exp[i]);
}
else
if (priority(exp[i]) > priority(opt_stk[opt_top]))
{
push_opt(opt_stk,&opt_top,&exp[i]);
}
else
{
while (priority (exp[i])<=priority(opt_stk[opt_top]))
{
if (opt_top == -1)
break;
pop_opt(opt_stk,&opt_top,&ch);
printf(“%c”,ch);
}//while
push_opt(opt_stk,&opt_top,&exp[i]);
}//else
}//else
}//for
while(opt_top!=-1)
{
pop_opt(opt_stk,&opt_top,&ch);
printf(“%c”,ch);
}//while
}//main
//check whether given character is an operator or not
//Return 1 if an operator else return 0
int chk_opt(char ch)
{
switch(ch)
{
case ‘^’:
case ‘*’:
case ‘/’:
case ‘%’:
case ‘+’:
case ‘-‘: return(1);
default : return(0);
}//switch
}//chk_opt
//Return a priority of specific operator if a valid operator elese return 0
int priority (char opt)
{
switch(opt)
{
case ‘^’ : return(4);
case ‘*’ :
case ‘/’ :
case ‘%’ : return(3);
case ‘+’ :
case ‘-‘ :return(2);
case ‘(‘ : return(1);
default : return (0);
}//switch
}//priority
//Push an operator(ch) in opt_stack
int push_opt(char opt_stk[max],int *opt_top,char *ch)
{
if(*opt_top==max-1)
{
return(-1);
}
else
{
(*opt_top)++;
opt_stk[*opt_top]=*ch;
return(1);
}
}
//Pop an operator(ch) in opt_stack
int pop_opt(char opt_stk[max],int *opt_top,char *ch)
{
if (*opt_top==-1)
{
return(-1);
}
else
{
*ch=opt_stk[*opt_top];
(*opt_top)–;
return(1);
}
- MongoDB Operators Tutorial – What are Different Operators Available? - October 5, 2019
- MongoDB Projection Tutorial : Return Specific Fields From Query - March 9, 2019
- MongoDB Index Tutorial – Create Index & MongoDB Index Types - July 6, 2018
Wonderful, what a blog it is! This webpage presents useful information to us, keep it up.