# Computing - Reverse Polish Notation

> Source: https://ollybritton.com/notes/a-level/computing/topics/reverse-polish-notation/ · Updated: 2021-01-15 · Tags: computing, regular-languages

##### 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))
$$

##### 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)
$$

##### $$((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 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$??
![PHOTO POSTFIX BINARY TREE 1](postfix-binary-tree-1.png)

##### ![PHOTO POSTFIX BINARY TREE 1](postfix-binary-tree-1.png) What does the next stage in the binary tree look like??
![PHOTO POSTFIX BINARY TREE 2](postfix-binary-tree-2.png)

##### ![PHOTO POSTFIX BINARY TREE 2](postfix-binary-tree-2.png) What does the next stage in the binary tree look like??
![PHOTO POSTFIX BINARY TREE 3](postfix-binary-tree-3.png)

##### 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.

##### 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)
$$

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt