Infix expression uses operator between the operands and it requires parenthesis for proper evaluation and one has to know the priorities of the operators while evaluating it Ex: Infix expression: (a + b)*c + d * e
Postfix expression uses operator after the operands and it does not include parenthesis. You need not know the priorities of the operators while evaluating it
Ex: Postfix expression: a b + c * d e * +
Process of converting “infix expression” to “postfix expression”:
Initially stack must be empty and the infix expression is scanned from left to right one at a time.
1. When an operand is encountered, it is directly printed
2. When a left parenthesis ‘(‘ is encountered, it is pushed onto stack.
3. When a right parenthesis ‘)’ is encountered, pop all till matching left parenthesis is encountered. Print all the popped elements excluding parenthesis.
4. When an operator is encountered and the operator at the top of the stack has lower priority, push it onto the stack.
5. Otherwise, pop all the elements till an element with lower priority is found or till the stack is empty and print them.
6. Now, push the operator onto the stack.
7. Repeat the same process till the end of the equation
8. Finally pop all the elements of the stack and print them.
Consider the infix expression “ (a + b) * c + d * e ”
Symbol | output | Stack contents |
Start | | Empty |
( | | ( |
a | a | ( |
+ | a | ( + |
b | a b | ( + |
) | a b + | Empty |
* | a b + | * |
c | a b + c | * |
+ | a b + c * | + |
d | a b + c * d | + |
* | a b + c * d | + * |
e | a b + c * d e | + * |
End | a b + c * d e * + | Empty |
0 comments:
Post a Comment