Postfix Expression Evaluation Using Stack
Concept Overview
In an infix expression (e.g., A + B * C), the computer must keep track of operator precedence
and parentheses, which makes evaluation complicated.
In contrast, a postfix expression (Reverse Polish Notation) determines operator precedence by its
structure — operators come after operands.
Therefore, postfix expressions are easier for computers to evaluate, as no parentheses or
precedence rules are needed.
Evaluation Rules for Postfix Expression
1. Read the expression from left to right.
2. If the element is an operand, push it onto the stack.
3. If the element is an operator (except NOT): pop two operands, evaluate, and push the result.
4. If the element is the NOT operator: pop one operand, evaluate, and push the result.
5. Continue this process until the end of the expression.
Algorithm for Postfix Evaluation
1. Append a right parenthesis ')' to the end of P.
2. Scan P from left to right and repeat steps 3–4 until ')' is encountered.
3. If an operand is encountered, push it onto the stack.
4. If an operator is encountered:
a. Pop the top two elements (A = top, B = next-to-top).
b. Evaluate B (operator) A.
c. Push the result back onto the stack.
5. The top element of the stack is the VALUE of the expression.
6. Exit.
Example
Infix Expression: Q = 10 * (8 + 4) – 6 / 3
Equivalent Postfix Expression: P = 10, 8, 4, +, *, 6, 3, /, –
(Commas are used here just to separate elements.)
Step-by-Step Evaluation
Step Symbol Scanned Stack Contents Operation / Comment
(1) 10 10 Push 10
(2) 8 10, 8 Push 8
(3) 4 10, 8, 4 Push 4
(4) + 10, 12 8 + 4 = 12
(5) * 120 10 × 12 = 120
(6) 6 120, 6 Push 6
(7) 3 120, 6, 3 Push 3
(8) / 120, 2 6÷3=2
(9) – 118 120 – 2 = 118
(10) ) — End of expression
Final Result: VALUE = 118
Key Points for Students
• Postfix evaluation eliminates the need for parentheses and precedence rules.
• Stack is the core data structure used for evaluation.
• Pop two operands for binary operators and one operand for unary operators (like NOT).
• The final result remains at the top of the stack.
