Conversion of Infix to Postfix Expression
What is Infix Expression?
An expression having operator in between the operands is known as infix expression.
For Example: a + b, a * b
What is Postfix Expression?
An expression having operator after operands is known as postfix expression.
How to convert any infix expression to postfix expression?
We follow the following steps to convert any infix expression to postfix expression:
We are going to use stack data structure to convert any infix expression to postfix expression:
1. Scan the Infix expression (string) from left to right.
2. Initialize an empty stack.
3. If the scanned symbol is an operand then add it to the Postfix expression(string).
4. If the scanned symbol is an operator and if the stack is empty push the symbol to stack.
5. If the scanned symbol is an Operator and the stack is not empty, compare the precedence of the symbol with the element on top of the stack.
6. If top Stack has higher precedence over the scanned symbol pop the stack else push the scanned symbol to stack. Repeat this step until the stack is not empty and top Stack has precedence over the symbol.
7. Repeat 4 and 5 steps till all the symbols are scanned.
8. After all symbols are scanned, we have to add any symbol that the stack may have to the Postfix string.
9. If stack is not empty add top Stack to Postfix string and Pop the stack.
10. Repeat this step as long as stack is not empty.
Note: we can put higher precedence operator over lower precedence operator on the stack, but we can't put a lower precedence operator over a higher precedence operator on the stack. In this case we need to pop all the higher precedence operators from stack to the postfix expression and then push that operator in the stack.
Example 1:
#include<stdio.h>
#include<stdlib.h> /* for exit() */
#include<ctype.h> /* for isdigit(char ) */
#include<string.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char n)
{
if(top >= MAX-1)
{
printf("\nStack Overflow.");
}
else
{
stack[++top] = n;
}
}
char pop()
{
char n ;
if(top <0)
{
printf("stack underflow: invalid infix expression");
getchar();
/* underflow may occur for invalid expression */
/* where ( and ) are not matched */
exit(1);
}
else
{
n = stack[top];
top = top-1;
return(n);
}
}
/* define function that is used to determine whether any symbol is operator or not (that is *symbol is operand) this function returns 1 if symbol is operator else return 0 */
int is_operator(char symbol)
{
if(symbol == '^' || symbol == '*' || symbol == '/' || symbol == '+' || symbol =='-')
{
return 1;
}
else
{
return 0;
}
}
/* define function that is used to assign precedence to the operator. Here ^ denotes exponent *operator. In this function we assume that higher integer value means higher precedence */
int precedence(char symbol)
{
if(symbol == '^')/* exponent operator, highest precedence*/
{
return(3);
}
else if(symbol == '*' || symbol == '/')
{
return(2);
}
else if(symbol == '+' || symbol == '-') /* lowest precedence */
{
return(1);
}
else
{
return(0);
}
}
void InfixToPostfix(char infix_exp[], char postfix_exp[])
{
int i, j;
char n;
char x;
push('('); /* push '(' onto stack */
strcat(infix_exp,")"); /* add ')' to infix expression */
i=0;
j=0;
n=infix_exp[i]; /* initialize before loop*/
while(n != '\0') /* run loop till end of infix expression */
{
if(n == '(')
{
push(n);
}
else if( isdigit(n) || isalpha(n))
{
postfix_exp[j] = n; /* add operand symbol to postfix expr */
j++;
}
else if(is_operator(n) == 1) /* means symbol is operator */
{
x=pop();
while(is_operator(x) == 1 && precedence(x)>= precedence(n))
{
postfix_exp[j] = x; /* so pop all higher precedence operator and */
j++;
x = pop(); /* add them to postfix expression */
}
push(x);
/* because just above while loop will terminate we have popped one extra
n for which condition fails and loop terminates, so that one*/
push(n); /* push current operator symbol onto stack */
}
else if(n == ')') /* if current symbol is ')' then */
{
x = pop(); /* pop and keep popping until */
while(x != '(') /* '(' encountered */
{
postfix_exp[j] = x;
j++;
x = pop();
}
}
else
{ /* if current symbol is neither operand not '(' nor ')' and nor
operator */
printf("\nInvalid infix Expression.\n"); /* the it is illegal symbol */
getchar();
exit(1);
}
i++;
n = infix_exp[i]; /* go to next symbol of infix expression */
} /* while loop ends here */
if(top>0)
{
printf("\nInvalid infix Expression.\n"); /* the it is illegal symbol */
getchar();
exit(1);
}
if(top>0)
{
printf("\nInvalid infix Expression.\n"); /* the it is illegal symbol */
getchar();
exit(1);
}
postfix_exp[j] = '\0'; /* add sentinel else puts() function */
/* will print entire postfix[] array upto MAX */
}
int main()
{
char infix[MAX], postfix[MAX]; /* declare infix string and postfix string */
/* why we asked the user to enter infix expression in parentheses ( ) What changes are
*required in program to get rid of this restriction since it is not in algorithm */
printf("ASSUMPTION: The infix expression contains single letter variables and single digit
constants only.\n");
printf("\nEnter Infix expression : ");
gets(infix);
InfixToPostfix(infix,postfix); /* call to convert */
printf("Postfix Expression: ");
puts(postfix); /* print postfix expression */
return 0;
}
OUTPUT:-
Helpful
ReplyDelete