Computing - Reverse Polish Notation
Is Reverse Polish Notation prefix, infix or postfix?
Postfix.
What’s another name for Reverse Polish Notation?
Postfix notation.
What is Reverse Polish Notation?
A notation for maths where the operator comes after the operands.
Why is Reverse Polish Notation used?
Because it means evaluation can be done using a stack.
What does RPN eliminate the need for?
Brackets.
#####
\[8 \times 7 + 6 \div 3 ^ 2\]What does this look like with brackets showing the order of operations??
\[(8 \times 7) + (6 \div (3 ^ 2))\]\[8 \times 7 + 6 \div 3 ^ 2\]
What does this look like with brackets showing the order of operations?
#####
\[a \times (b + c) \div d\]What does this look like with brackets showing the order of operations??
\[((a \times (b + c)) \div d)\]#####
\[((a \times (b + c)) \div d)\]What does this look like with the operators moved to the end of the brackets??
\[((a\, (b + c)\, \times)\, d\div)\]#####
\[((a\, (b + c)\, \times)\, d\div)\]What is this in RPN??
\[a\,b\,c\,\times\,d\,\div\]2021-01-18
What are the three steps to convert an infix expression to a postfix expression?
- Add brackets for everything
- Move the operator inside each bracket to the end
- Remove all brackets
\[a \times (b + c) \div d\]
What does this look like with brackets showing the order of operations?
\[((a \times (b + c)) \div d)\]
What does this look like with the operators moved to the end of the brackets?
\[((a\, (b + c)\, \times)\, d\div)\]
What is this in RPN?
What would $a\times(b + c)$ be as two nodes of a binary tree?
- Left: $a$
- Right: $a \times b$
What traversal algorithm do you use when using a binary tree to convert to postfix notation?
Post-order traversal.
When splitting an expression into parts using a binary tree, does the root node become the operator with the most precedence or the least precedence?
The least precedence.
When traversing a binary tree to convert to postfix notation, where should you put the dot?
On the right.
What does the first part of the binary tree look like for $w \wedge x + z - x \div w$?
If you’ve written down
\[a\,b\,c\]whilst converting from RPN to infix and the next item in the stack is $+$, what would you write next??
\[a\\,(b + c)\]