Polish Notation Converter
- Arithmetical and logical notations
- What is the infix notation?
- What is the Polish notation?
- Types of Polish notation
- Some examples of Polish notation expressions
- How to convert from and to the prefix and postfix notations
- Examples of conversion from infix to the Polish notations (and vice-versa)
- How to use our Polish notation converter?
- Why use our Polish notation converter?
There are other ways to write operations than the standard "symbols-between-numbers" fashion: with our Polish notation converter, you'll learn all about them!
The order in which we write every operation is one of these conventions: the one everyone knows is called infix notation. But are you sure that's the best way to write equations?
Let's find out! Keep on reading to learn more about Polish notation and reverse Polish notation. Here we will teach you:
- What the infix notation is;
- The elements of an arithmetic notation;
- What the Polish notation is;
- The two types of Polish notation;
- How to convert between notations; and
- How to use our Polish notation converter.
Arithmetical and logical notations
To write, compute, or communicate mathematical operations or statements, we need to introduce their building blocks. We are specifically talking about:
- Operands: numbers (e.g., , , , ) or letters representing unknowns (e.g., , , );
- Operators: everything that acts on operands (e.g., , , , ).
Operators follow specific rules and properties that let us use them in the correct order.
- Precedence indicates which operator has to be applied first.
- Grouping uses brackets to indicate that certain operations must be performed directly without following precedence.
- Associativity determines the direction in which operators act in case of equal precedence and absence of brackets.
The precedence of the basic arithmetic operators is, from the highest to the lowest:
Now it's clear that in the case of operations with equal precedence (or when the order has to be changed), additional rules are required. Brackets prioritize certain parts of the operation, insulating them from the standard precedence order.
For example, consider . Following the standard precedence rules, we would compute it as . If we need to compute the addition first, we need to add brackets around the interested operands: .
Notice how we can also write the first, precedence-ruled expression: . In this case, brackets are not necessary, but are implied to be surrounding the operands in order of precedence.
The last rule is used when two or more operators with the same precedence appear in the same expression. In which order should they be evaluated? It is necessary to introduce the concept of associativity — note that this is not the same thing as the property of operations like the distributive property!
Take the expression . Addition and subtraction have the same precedence, and according to how we place brackets, we can get two different results: or .
Which one is correct? The answer is "it depends". Traditionally, all of the binary operators (acting on two operands, like multiplication, addition, and so on) are left-associative, which means that the operators are grouped from the left. The other situation is right-associative, and the operators are enclosed in brackets from the right.
What is the infix notation?
The traditional way to write operations is called infix notation. The operators lie between the operands, like in where the lies between the and the . To understand which operand belongs to which operator, it is necessary to use associativity and precedence rules. Brackets are often necessary to ensure the correct evaluation of the operation.
What is the Polish notation?
In 1924, a Polish logician Jan Łukasiewicz invented a different way to write operations, making brackets and precedence rules unnecessary. This notation, called Polish notation, sees the operators and the operands grouped in a way that avoids interposing the former with the latter if they are parts of the same operation.
For now, it may sound unclear, but stay here because it is easier than you expect!
Remember that operators are not necessarily all together, and they can still appear between operands; however, as the calculation proceeds, they eventually disappear.
🔎 The Polish notation is thought to be easier and faster to use, but this is not yet scientifically proved: it may just be that it requires a more shortened version of the expression rather than an actual reduction of the difficulty.
Types of Polish notation
The Polish notation, also known as prefix notation, proved its value in logic as an alternative to the infix notation, as the operators now appear in front of the relative operands. In the '50s, with the diffusion of informatics and computers, another kind of notation arose.
The postfix, or reverse Polish notation (so-called because the operators follow their operands) is in almost every aspect similar to the Polish notation. This way of writing an arithmetic expression moves the operators toward the end of the expression, grouping the operands on the left side of their operators. Such an implementation is faster on a computer since it requires less memory, and efficiently uses the stack: we will see later how popping and pushing on it is fundamental in the conversion and calculation of Polish notation expressions.
💡 We will use the pairs of terms "prefix" – "Polish notation" and "postfix" – "reverse Polish notation" interchangeably across the text.
- Polish notation = Prefix notation; and
- Reverse Polish notation = Postfix notation.
Some examples of Polish notation expressions
Are you ready for an expression written in Polish notation?
Does it look strange? Maybe a little. Let's see how to evaluate it. First, look at where numbers group, on the right. Take the ones closest to the operator :
In Polish notation, the expression is the same as in infix notation. The first step is then:
Now all of the operators and operands are grouped with their kin, and we can easily proceed with the same rule we just saw in action.
So how would we write the same expression in infix notation? Easy — it's . It may look a bit more complicated, even if more familiar and regular. But how to evaluate it?
First thing, we have to know where to start. From the left? From the right? In this case, we start from the left. However, we first evaluate the second operation rather than the initial one since the precedence of the multiplication is higher than the one of the sum.
We have , which gives .
And now, since all the operators have the same precedence, we proceed from left to right: , and then becomes .
As you can see, the infix notation requires more rules than the Polish notation: knowing the precedence, scanning the expression in its entirety before executing, and checking for brackets.
How to convert from and to the prefix and postfix notations
Conversion from the infix notation to the postfix notation
When you have an expression written using the infix notation and you need to convert it to postfix notation, you can follow a simple algorithm called the shunting-yard algorithm. The Dutch computer scientist Edsger W. Dijkstra first proposed it in 1961.
Assuming the input is a string containing both operators and operands in the general form , for example, and that there are two "arrays" wherein we store the various elements, an output array, and an operator stack.
Here is the pseudocode for the conversion:
Read the first element of the input string:
- If it's a number, then push it on the output.
- If it's an operator
- While there is an operator
O2at the top of the operator stack with greater or equal precedence than
O2from the operator stack and push it on the output.
O1on the operator stack.
- While there is an operator
- If it is a left bracket
(, then push it on the operator stack.
- If it is a right bracket
- While the last element of the operator stack is a left bracket, pop the operators from the operator stack and push them on the output.
- Pop the left bracket.
Repeat until the input is empty. Then, if the operator stack is not empty, pop all of the content of the operator stack and push it on the output.
Conversion from the infix notation to the prefix notation
The conversion from the infix to the Polish notation is a bit more tricky, and there is no named algorithm for the procedure.
In a way less elegant manner, the steps are:
- Reverse the infix expression, making particular attention to the brackets (we will see this later in an example).
- Apply the shunting yard algorithm, but changing the condition on the precedence of the operators from greater or equal to just greater.
- Reverse the newly found quasi-postfix expression to find the prefix expression.
Converting from the Polish notations to the infix notation is almost more effortless. The only difficulty arises in choosing when to include or omit brackets. We will skip that step in the following procedure so as not to make it too heavy, but we will tell you how to do that later.
First, let's check how to convert from prefix to infix.
- Take a prefix expression. All of the symbols are stacked at the left of their operands. Scan the expression from the right until you find an operator.
- If you find an operator before you pass two operands, there is an error in your expression.
- Now take the last two operands you encountered, place the operator between them (see that it's an infix expression?), and wrap it in brackets. That operation will be considered a single composite operand from now on.
- Keep scanning the expression until you find the next operator, and place it between the last two operands.
- Proceed until the expression is completely read.
Conversions back to the infix notation
The procedure to convert from postfix to infix is similar.
- Take the postfix expression, and scan it from left to right.
- When you meet an operator, take the last two operands you scanned and place the operator between them.
- If you didn't see two operands before the operator, you are not scanning a correct expression.
- Wrap the resulting infix expression between brackets.
- Proceed to scan the expression and build infix blocks until you run out of operators on the right side.
We told you that we would explain how to correctly place brackets. It's better to leave this to a computer, but here is the explanation if you want to go on.
When you meet an operator while scanning the expression, you have to check the precedence of the operands associated with it. Then wrap the operand in brackets (NOT the expression you will obtain by placing the newly scanned operator in between them) only if the operator's precedence is higher or equal than the associated to the operand.
This is pretty easy if the operand is a number: we can say that it has infinite precedence, and therefore it is never closed between brackets.
The case of single operators is again pretty easy. However, when you have a composite operand (containing two or more operators), it is necessary to check all of them and select the lowest priority.
Here are some examples:
For , both operands (on the left and right side of ) are numbers — no brackets here. The result is .
For , the precedence of is lower than that of ; hence, we need brackets. The precedence of the operators on the right side, and is the same: no brackets. The end result is .
Last one! Multiple operators:
- In , the right side is a number, so no brackets there. On the left side, we find both a and a . The lowest precedence () wins. The current operator is , so we have the same situation as before: brackets! The outcome is .
The conversion from the prefix notation to the infix one is straightforward, and only requires you to reverse the expression before applying the algorithm we just saw!
⚠️ If a set of brackets already encloses an operation, ignore its operator while computing the lowest precedence!
Examples of conversion from infix to the Polish notations (and vice-versa)
Now it's time to see how to apply all of those algorithms. We'll do just four examples, and then we are sure you will be able to write everything in Polish notation!
Let's convert from infix to postfix first. Here is our expression:
It's time for the shunting yard algorithm. We start reading it from the left.
First, we meet a left bracket; we push it on the stack. The number 3 is pushed on the output.
We then encounter the operator. The stack doesn't contain other operators, so we push it directly there. You can easily do it on a piece of paper — or if you are good with remembering things, use your memory.
Let's continue. Next is a number — push it on the output.
We've reached the right bracket: we need to pop operators from the stack until we meet the paired left bracket.
Remember to pop also the left bracket. Now we read . The operator stack is empty, so we push it there.
Keep on scanning. We meet another left bracket. Now you know how it works:
Here comes another operation. The is pushed on the stack, the numbers on the output. Just a few steps left!
At last, the right bracket. We pop the minus sign and the left bracket from the stack. Remember the bracket!
Now the expression is over, but the is still on the stack. Pop it and push it on the output, and you will get a new, shiny, reverse Polish notation expression: .
Next episode: the conversion to prefix notation.
We chose an expression that will show you how it differs from the postfix notation conversion:
First step, reverse it!
Now, follow these steps: we will speak up only if it's needed.
Yes, now we need to talk! The next symbol we meet is a , but look, there is a symbol with the same precedence on the top of the stack: ! Here, the only modification to the shunting yard algorithm comes into play, and since the operators are popped only if their precedence is greater (and not equal) to the one on the top of the stack, we simply push there:
The expression is over, and we get this almost postfix result:
We reverse it, and here is our prefix expression!
🔎 Feeding the reversed infix expression in the unmodified shunting yard algorithm would have returned — quite different from the result we obtained earlier!
The conversion back to infix notation is even easier. We will give you an example only for the one from postfix notation. The other one is straightforward.
The expression we take is a little bit more complex than the one we showed before. Ready? Here it is: .
We read it from the left. You will see both a right and a left stack containing the operators, one for each side of the operand we consider at each "building" step. If an operand is a number, then you will see in the stack. It will remember you that you won't need brackets there!
We read the operator , so we build the expression , pop everything we used from the output, and then push the result. Remember to empty the stacks.
Now we read another number, and then a symbol, . Let's see what happens:
Now in the left stack we have a . Its precedence is smaller than the one of , so we put some bracket around that operand. Then we clean the stacks, and rearrange the output:
From now we won't add comments, but follow closely each step!
In the last step, we had to ignore the since a set of brackets encloses it, and then we added a new set only on the right side: the left side had the same precedence, and we ignored it.
The resulting expression in infix notation is then .
How to use our Polish notation converter?
We offer you a calculator that you can use in many modes. But be careful; it is not that easy to use, and you cannot always detect your errors!
First thing, choose what you want to do: you can either convert an expression in the four modes we explained above or calculate the result of a Polish notation expression.
If you choose convert, then you have to select one of the four modes of conversion:
- From infix to prefix notation;
- From infix to postfix notation;
- From prefix to infix notation; or
- From postfix to infix notation.
Now write the expression! Remember that you can input the four operators
⚠️ Our Polish notation converter can read only positive numbers, either integers or decimal. If you try to input a negative number, bad things... won't happen: you will just get a really bad result!
If you decide to convert back from the Polish notation to the infix notation, we need to teach you how to input the expression. Since you can't use spaces, you need to separate pairs of adjacent numbers through a couple of periods:
.. — but be careful, as their position changes according to the desired conversion.
- If you are converting from the prefix notation, then the two periods must be inserted before the number, like so:
- If you are converting from the postfix notation, then you must add the periods at the end of each number:
The other choice you had would bring you to the calculation mode. Here you can insert a Polish notation or a reverse Polish notation expression and see the result!
⚠️ You don't have to choose the type of Polish notation in which you are writing the expression, because our calculator can detect it independently. But remember to add the periods!
If you need to check the result of an infix expression, select advanced mode, and switch to infix notation. Remember that you can input operations only with the symbols
Why use our Polish notation converter?
Now that you know what is the Polish notation, how to read it, convert it from infix notation and back, and you can calculate any expression written that way, you may wonder, "do I need this?".
Probably not. This strange way of writing operations may not be your cup of tea. Some calculators used reverse Polish notation in the past years, but now they are limited to a restricted group of enthusiasts. It remains mostly a curiosity and a beautiful example of how being open-minded about other possibilities can create interesting and curious things.
Enjoy our Polish notation converter!
What is the Polish notation?
The Polish notation is a different way to write arithmetic operations. There are two types of Polish notations: one in which operators are grouped on the left of the operations, and one in which the operators are grouped on the right.
Is Polish notation better?
The question is still open! Some say that using the Polish notation leads to faster and more efficient calculations, but the scientific community hasn't decided yet.
However, it may be better for you, so try it out!