How to Evaluate a Postfix Expression Using Stack
In case you're not familiar, a stack is a collection or list wherein the last element added to the stack is always the first element to be removed.
When evaluating postfix expressions, using a stack to temporarily store operands is necessary because as we are evaluating each character of the postfix expression from left to right, we can't instantly know an operator's right-hand operand. Therefore we need to temporarily add (push) operands to the stack and only remove (pop) them from the stack once we know an operator's right operand.
So now that you know what a stack is and why it is used, here is the process for evaluating a postfix expression using stack.
Moving from left to right, one character at a time, if a character is an operand (number), push it to the top of the stack.
Otherwise, if a character is an operator (^ * / + -), pop (remove) the top element from the stack to form the operator's right operand, and then pop the next top element from the stack to form the operator's left operand. Finally, solve the expression formed by the operator and its operands, and push the result to the top of the stack.
Repeat the above until all characters have been processed, at which point the last element remaining in the stack becomes the result.
Postfix Evaluation Examples
Here are a couple of examples of how to evaluate postfix expressions using the stack method.
Example #1: 4 5 + 7 2 - *
4 5 + 7 2 - *
The first character scanned is "4", which is an operand, so push it to the stack.
| 4 | ||
| Stack | Expression |
4 5 + 7 2 - *
The next character scanned is "5", which is an operand, so push it to the stack.
| 5 4 | ||
| Stack | Expression |
4 5 + 7 2 - *
The next character scanned is "+", which is an operator, so pop its two operands from the stack. Pop 5 from the stack for the right operand and then pop 4 from the stack to make the left operand.
4 + 5 = 9 | ||
| Stack | Expression |
Next, push the result of 4 + 5 (9) to the stack.
| 9 | ||
| Stack | Expression |
4 5 + 7 2 - *
The next character scanned is "7", which is an operand, so push it to the stack.
| 7 9 | ||
| Stack | Expression |
4 5 + 7 2 - *
The next character scanned is "2", which is an operand, so push it to the stack.
| 2 7 9 | ||
| Stack | Expression |
4 5 + 7 2 - *
The next character scanned is "-", which is an operator, so pop its two operands from the stack. Pop 2 from the stack for the right operand and then pop 7 from the stack to make the left operand.
| 9 | 7 - 2 = 5 | |
| Stack | Expression |
Next, push the result of 7 - 2 (5) to the stack.
| 5 9 | ||
| Stack | Expression |
4 5 + 7 2 - *
The next character scanned is "*", which is an operator, so pop its two operands from the stack. Pop 5 from the stack for the right operand and then pop 9 from the stack to make the left operand.
9 * 5 = 45 | ||
| Stack | Expression |
Next, push the result of 9 * 5 (45) to the stack.
| 45 | ||
| Stack | Expression |
Since we are done scanning characters, the remaining element in the stack (45) becomes the result of the postfix evaluation.
Postfix notation: 4 5 + 7 2 - *Result: 45
Example #2: 4 2 3 5 1 - + * +
4 2 3 5 1 - + * +
The first character scanned is "4", which is an operand, so push it to the stack.
| 4 | ||
| Stack | Expression |
4 2 3 5 1 - + * +
The next character scanned is "2", which is an operand, so push it to the stack.
| 2 4 | ||
| Stack | Expression |
4 2 3 5 1 - + * +
The next character scanned is "3", which is an operand, so push it to the stack.
| 3 2 4 | ||
| Stack | Expression |
4 2 3 5 1 - + * +
The next character scanned is "5", which is an operand, so push it to the stack.
| 5 3 2 4 | ||
| Stack | Expression |
4 2 3 5 1 - + * +
The next character scanned is "1", which is an operand, so push it to the stack.
| 1 5 3 2 4 | ||
| Stack | Expression |
4 2 3 5 1 - + * +
The next character scanned is "-", which is an operator, so pop its two operands from the stack. Pop 1 from the stack for the right operand and then pop 5 from the stack to make the left operand.
| 3 2 4 | 5 - 1 = 4 | |
| Stack | Expression |
Next, push the result of 5 - 1 (4) to the stack.
| 4 3 2 4 | ||
| Stack | Expression |
4 2 3 5 1 - + * +
The next character scanned is "+", which is an operator, so pop its two operands from the stack. Pop 4 from the stack for the right operand and then pop 3 from the stack to make the left operand.
| 2 4 | 3 + 4 = 7 | |
| Stack | Expression |
Next, push the result of 3 + 4 (7) to the stack.
| 7 2 4 | ||
| Stack | Expression |
4 2 3 5 1 - + * +
The next character scanned is "*", which is an operator, so pop its two operands from the stack. Pop 7 from the stack for the right operand and then pop 2 from the stack to make the left operand.
| 4 | 2 * 7 = 14 | |
| Stack | Expression |
Next, push the result of 2 * 7 (14) to the stack.
| 14 4 | ||
| Stack | Expression |
4 2 3 5 1 - + * +
The next character scanned is "+", which is an operator, so pop its two operands from the stack. Pop 14 from the stack for the right operand and then pop 4 from the stack to make the left operand.
4 + 14 = 18 | ||
| Stack | Expression |
Next, push the result of 4 + 14 (18) to the stack.
| 18 | ||
| Stack | Expression |
Since we are done scanning characters, the remaining element in the stack (18) becomes the result of the postfix evaluation.
Postfix notation: 4 2 3 5 1 - + * +Result: 18