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?
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?
2021-01-18
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$?
What does the next stage in the binary tree look like?
What does the next stage in the binary tree look like?
What does the next stage in the binary tree look like?
What does the next stage in the binary tree look like?
When creating a binary tree for an infix expression, what must you remember to do first?
Add brackets around every operator.
What are the three steps in the process to convert RPN to infix?
- Move left to right, writing down operators.
- If you find an operator, place it between the two operands you have written down.
- If you’re inserting an operator, add brackets.