What is Infix, Prefix, and Postfix Notation?
Operators vs Operands
Operators are symbols like +, -, *, /, ^, anything that operates on...
Operands, which are values like 8, 21; things to be operated on.
The Three Notations
Ex:
- 24 / 7
- 8 - 2 * 3 + 7
Ex:
- / 24 7
- + - 8 * 2 3 7
Ex:
- 24 7 /
- 8 2 3 * - 7 +
Why not stick with Infix notation?
Notice how in the second example, 8 - 2 * 3 + 7, we had to evaluate the multiplication before the subtraction and finally the addition? This is inconvenient for computers to evaluate as parentheses need to be applied according to the order of operations. However, prefix and postfix notation don't suffer from this ambiguity and follow an easy and consistent set of instructions to evaluate, making it very suitable for computers!
What's an Expression Tree?
Expression Tree
Expression Trees are binary trees whose parent nodes are operators and children nodes are operands of which the operators will execute on. Refer to the Expression Tree Visualizer for the Expression Tree representation of the expression (8 - 2 * 3 + 7).
What's so special about it?
There are three basic ways to traverse binary trees: Preorder, Inorder, and Postorder. Sound familiar? Yup, for expression trees, preorder traversal outputs prefix notation, inorder outputs infix, postorder outputs postfix!
How do these three traversals work?
- Put current node in result
- Go to left child, repeat
- Go to right child, repeat
- Go to left child, repeat
- Put current node in result
- Go to right child, repeat
- Go to left child, repeat
- Go to right child, repeat
- Put current node in result
How do you evaluate Prefix/Postfix notation?
What is a Stack?
- 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: answerFor more information
While reviewing information about this topic, I primarily used UCSB Lecturer Mike Costanza's slides for CS12 linked below. Sadly he retired in 2018 so I won't be able to meet him in college :(