How do you evaluate Prefix/Postfix notation?
What is a Stack?
Stacks are an abstract data type with two primary operations:
- Push: Add an element to the top of the stack
- Pop Remove an element from the top of the stack
A stack behaves just like a stack of plates: you push plates to the top and also pop plates from the top.
A stack follows LIFO, or Last in First Out.
How to evaluate Postfix and Prefix expressions with a stack?
Note: Prefix is basically evaluated the same way as Postfix but backwards! Just reverse the input expression or read it backwards! Also note that since it is reversed, the left and right operands are flipped too!
Postfix Pseudocode:
1
2
3
4
5
6
7
8
9
10
11
for each token in input {
if token is operand
push to stack
else if token is operator
pop two operands from stack
(first popped is right operand)
(second popped is left operand)
perform operation on the operands
push result of operation to stack
}
stack should only have one item: answerPrefix Pseudocode:
1
2
3
4
5
6
7
8
9
10
11
for each token in reversed input {
if token is operand
push to stack
else if token is operator
pop two operands from stack
(first popped is left operand)
(second popped is right operand)
perform operation on the operands
push result of operation to stack
}
stack should only have one item: answerStack Evaluation Visualizer
Input
Stack