What is the Polish Notation?

In school we learned how to write numerical expressions such as 5 X (9 - 2). We also learned how to write algebraic expressions such as (n + 6)(n - 8). As we learned these, we also learned about rules of precedence, i.e., do what's in parentheses first, then do exponents, then multiplications and divisions, and finally additions and subtractions, and in the case of equal precedence, go from left to right.

The notation that we use for writing expressions in this way is called the infix notation, because the binary operators (i.e., +, -, x, and ÷) are placed in-between their two operands.

---

In 1924, the Polish logician Jan Łukasiewicz invented a new notation, called the prefix notation, where the operator is written first and then it's followed by its operands. He invented it because the prefix notation made it a lot easier for him to prove certain theorems in mathematics. The prefix notation became known as the Łukasiewicz notation, and also as the Polish notation.

For example:

5 X (9 - 2) in infix notation becomes
* 5 - 9 2 in Polish notation.

(n + 6)(n - 8) in infix notation becomes
* + n 6 - n 8 in Polish notation.

(Note that in above two examples, the asterisk "*" is used as the multiplication symbol, as is customarily done when working with computers.)

When learning Polish notation for the first time, the best way to proceed is to first convert the infix expression into a tree diagram, and then get the expression into Polish notation by traversing the tree, as is shown in this video.

The first thing that you might notice about Polish notation is that you never need to use parentheses. Neither do you have to worry about rules of precedence. Polish notation is completely unambiguous as to the order of the operations. This is the big advantage of the Polish notation over the infix notation!

---

In the 1950's, when computer scientists were designing general purpose computers, they needed to figure out how the computers would evaluate numerical expressions. Having the expressions in infix notation would require extensive algorithms that could handle parentheses (including nested parentheses to many levels) while following the rules of precedence. Such algorithms would have to occupy a lot of computer memory, require possibly a lot of additional memory for scratch work, and would take up a lot of computer time to execute. So, the computer scientists decided to simply avoid all these problems by using Polish notation for all their expressions.

Actually, they went even a step further beyond that. Computer scientists were already familiar with a structure that they could create in computer memory that they called a stack. They were already using stacks as temporary storage locations for other purposes. So, could they somehow use a stack while evaluating an expression in Polish notation? Well, yes -- except that it certainly would be a lot easier if in the Polish notation the operator would be written after its operands instead of before its operands. That way, as the expression was read from left to right, an operand would always be pushed onto the stack; an operator would cause its operands to be popped off the stack, the operation performed, and the result pushed back on the stack; and this method would continue until the expression was finished and then the only thing remaining on the stack was the final answer.

So, they invented a new notation called the postfix notation. They also called it the Reverse Polish notation, or RPN.

For example:

5 X (9 - 2) in infix notation becomes
5 9 2 - * in Reverse Polish notation.

(n + 6)(n - 8) in infix notation becomes
n 6 + n 8 - * in Reverse Polish notation.

(Note that the Reverse Polish notation is not just the Polish notation read backwards.)

Here too, when learning Reverse Polish notation for the first time, the best way to proceed is to first convert the infix expression into a tree diagram, and then get the expression into Reverse Polish notation by traversing the tree, as is shown in this video.

---

The first hand-held calculators that became available around 1970 required that data be entered to it using RPN (Reverse Polish notation). Today's scientific calculators have become smart enough to handle input entered in infix notation.

It may seem that using a calculator that requires RPN would be cumbersome. After all, don't you first have to convert your problem into a tree, then from the tree write down what the expression in RPN before you can enter it into the calculator?

Well, not necessarily. For one thing, with practice, you can skip drawing the tree and convert from infix notation to RPN quite easily. But, even more so, RPN follows the order of the steps you would be taking if you were figuring out the answer using pencil and paper, as is shown in this video.