Reverse Polish Notation

Infix Notation

A + B

What we humans use is infix notation. We just don't refer to it as that. W To write in infix notation, we read it from left to right. The previous example uses letters, but a more specific example would be 2 + 5. If we did 4 * 2 + 5, we would have to use bidmas/bodmas or brackets. The problem is that computers have a hard time doing this.

Prefix/Polish Notation

In polish notation, A + B would be replaced by +AB. This method is less vague and makes it easier for the computer to perform. The plus sign is placed between the letters A and B.

Postfix notation/ Reverse Polish Notation

This is the inverse of polish notation, where +AB is replaced with AB+. This is just another way of writing A + B. You can use a stack by using reverse polish notation (RPS). As an example, consider the number 438+*.

First you push all the numbers onto the stack until you meet an operator.

When you meet the operator you pop out the item and put it to the left of the operator and pop the other one and put it to the right of the operator You then you push the result back in.

When you meet the next operator, you pop the item and put it to the left of it and pop the other operator and put it to the right of it. The result is then pushed onto the stack.

Converting infix notation to reverse polish notation

When the answer is asked, it will be popped out of the stack.

6*(3+4)

To convert 6*(3+4) into reverse polish notation, we use a binary tree

First we start with the left hand number.

Then we start with the operator. Operators are always in the central position(the parent nodes).

Then we put the next expression.

We now separate the expressions into subtrees.

You then do a post order traversal on the tree. Click here to learn how to do post order traversal. After traversing, you will get 634+*

Summery

A + B is Infix Notation

+AB is prefix/polish notation

AB+ is postfix/reverse polish notation.