Data Structures and Algorithms - Old Questions
2. What is Postfix expression? Write an algorithm to evaluate value of postfix expression. Trace the following expression into postfix expression.
(A+B*C)+(D-E/ F)
The expression in which operator is written in after the operands is called postfix expression. For example: AB+
Algorithm to evaluate value of postfix expression
1. Create a stack to store operands.
2. Scan the given expression from left to right.
3. a) If the scanned character is an operand, push it into the stack.
b) If the scanned character is an operator, POP 2 operands from stack and perform operation and PUSH the result back to the stack.
4. Repeat step 3 till all the characters are scanned.
5. When the expression is ended, the number in the stack is the final result.
Given,
infix expression = (A+B*C)+(D-E/ F)
Now, converting it into postfix:
|
Characters |
stack |
Postfix expression |
|
( |
( |
|
|
A |
( |
A |
|
+ |
(+ |
A |
|
B |
(+ |
AB |
|
* |
(+* |
AB |
|
C |
(+* |
ABC |
|
) |
|
ABC*+ |
|
+ |
+ |
ABC*+ |
|
( |
+( |
ABC*+ |
|
D |
+( |
ABC*+D |
|
- |
+(- |
ABC*+D |
|
E |
+(- |
ABC*+DE |
|
/ |
+(-/ |
ABC*+DE |
|
F |
+(-/ |
ABC*+DEF |
|
) |
+ |
ABC*+DEF/- |
|
|
|
ABC*+DEF/-+ |
The postfix expression of given infix expression is: A B C * + D E F / - +