How to Evaluate a Prefix 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 prefix expressions, using a stack to temporarily store operands is necessary because as we are evaluating each character of the prefix expression from right to left, we can't instantly know what operation will be performed on the two operands. Therefore we need to temporarily add (push) operands to the stack and only remove (pop) them from the stack once we know what operation will be performed on them.
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 right to left, 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 left operand, and then pop the next top element from the stack to form the operator's right 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.
Prefix Evaluation Examples
Here are a couple of examples of how to evaluate prefix expressions using the stack method.
Example #1: + - 20 * 3 4 1
+ - 20 * 3 4 1
The first character scanned is "1", which is an operand, so push it to the stack.
| 1 | ||
| Stack | Expression |
+ - 20 * 3 4 1
The next character scanned is "4", which is an operand, so push it to the stack.
| 4 1 | ||
| Stack | Expression |
+ - 20 * 3 4 1
The next character scanned is "3", which is an operand, so push it to the stack.
| 3 4 1 | ||
| Stack | Expression |
+ - 20 * 3 4 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 left operand and then pop 3 from the stack to make the right operand.
| 1 | 3 * 4 = 12 | |
| Stack | Expression |
Next, push the result of 3 * 4 (12) to the stack.
| 12 1 | ||
| Stack | Expression |
+ - 20 * 3 4 1
The next character scanned is "20", which is an operand, so push it to the stack.
| 20 12 1 | ||
| Stack | Expression |
+ - 20 * 3 4 1
The next character scanned is "-", which is an operator, so pop its two operands from the stack. Pop 12 from the stack for the left operand and then pop 20 from the stack to make the right operand.
| 1 | 20 - 12 = 8 | |
| Stack | Expression |
Next, push the result of 20 - 12 (8) to the stack.
| 8 1 | ||
| Stack | Expression |
+ - 20 * 3 4 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 left operand and then pop 8 from the stack to make the right operand.
8 + 1 = 9 | ||
| Stack | Expression |
Next, push the result of 8 + 1 (9) to the stack.
| 9 | ||
| Stack | Expression |
Since we are done scanning characters, the remaining element in the stack (9) becomes the result of the prefix evaluation.
prefix notation: + - 20 * 3 4 1Result: 9
Example #2: - * 3 + 3 7 / ^ 4 2 2
- * 3 + 3 7 / ^ 4 2 2
The first character scanned is "2", which is an operand, so push it to the stack.
| 2 | ||
| Stack | Expression |
- * 3 + 3 7 / ^ 4 2 2
The next character scanned is "2", which is an operand, so push it to the stack.
| 2 2 | ||
| Stack | Expression |
- * 3 + 3 7 / ^ 4 2 2
The next character scanned is "4", which is an operand, so push it to the stack.
| 4 2 2 | ||
| Stack | Expression |
- * 3 + 3 7 / ^ 4 2 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 left operand and then pop 4 from the stack to make the right operand.
| 2 | 4 ^ 2 = 16 | |
| Stack | Expression |
Next, push the result of 4 ^ 2 (16) to the stack.
| 16 2 | ||
| Stack | Expression |
- * 3 + 3 7 / ^ 4 2 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 left operand and then pop 16 from the stack to make the right operand.
16 / 2 = 8 | ||
| Stack | Expression |
Next, push the result of 16 / 2 (8) to the stack.
| 8 | ||
| Stack | Expression |
- * 3 + 3 7 / ^ 4 2 2
The next character scanned is "7", which is an operand, so push it to the stack.
| 7 8 | ||
| Stack | Expression |
- * 3 + 3 7 / ^ 4 2 2
The next character scanned is "3", which is an operand, so push it to the stack.
| 3 7 8 | ||
| Stack | Expression |
- * 3 + 3 7 / ^ 4 2 2
The next character scanned is "+", which is an operator, so pop its two operands from the stack. Pop 7 from the stack for the left operand and then pop 3 from the stack to make the right operand.
| 8 | 3 + 7 = 10 | |
| Stack | Expression |
Next, push the result of 3 + 7 (10) to the stack.
| 10 8 | ||
| Stack | Expression |
- * 3 + 3 7 / ^ 4 2 2
The next character scanned is "3", which is an operand, so push it to the stack.
| 3 10 8 | ||
| Stack | Expression |
- * 3 + 3 7 / ^ 4 2 2
The next character scanned is "*", which is an operator, so pop its two operands from the stack. Pop 10 from the stack for the left operand and then pop 3 from the stack to make the right operand.
| 8 | 3 * 10 = 30 | |
| Stack | Expression |
Next, push the result of 3 * 10 (30) to the stack.
| 30 8 | ||
| Stack | Expression |
- * 3 + 3 7 / ^ 4 2 2
The next character scanned is "-", which is an operator, so pop its two operands from the stack. Pop 8 from the stack for the left operand and then pop 30 from the stack to make the right operand.
30 - 8 = 22 | ||
| Stack | Expression |
Next, push the result of 30 - 8 (22) to the stack.
| 22 | ||
| Stack | Expression |
Since we are done scanning characters, the remaining element in the stack (22) becomes the result of the prefix evaluation.
prefix notation: - * 3 + 3 7 / ^ 4 2 2Result: 22