Shunting-yard algorithm

The need for solving a large number of computational problems was the reason why scientists began studying the recording of arithmetic expressions. The Reverse Polish Notation, or RPN, is one of the most popular methods that allows you to avoid additional lines in the program code associated with the description of the prioritization of parentheses.

Converting expressions to RPN

Let's learn now how to switch over from the usual notation to the postfix one. We just need to rewrite operands in the same order as before and move operators next to the closing parenthesis associated with this operator.

Let's also look at the following expression:

$(A + B) \cdot C - (D - E) \cdot (F + G)$

Firstly, we put the parentheses around:

$(((A + B) \cdot C) - ((D - E) \cdot (F + G)))$

Then we move operators to the parentheses:

As a result, we get the RPN:

$AB + C \cdot DE - FG + \cdot -$

That is something! We have learned how to do this ourselves, so let's teach the computer as well. We need to create an algorithm that can correctly switch any expression from the infix entry to the RPN. Let's try to describe it.

Take another look at the expressions $A+B\cdot C$ and $ABC\cdot+$, and compare them. Why did $+$ move to the end of the expression and $\cdot$ stay behind? Remember the operators' precedence: multiplication comes before addition. This is exactly why it happened. Also, during the converting process, we should store the $+$ operator somewhere. Creating a stack for storing operators until we need them is the most convenient way to do this. Just to remind you: a stack is a list of elements that are organized according to the LIFO principle (last in — first out). So, we will add operators to the stack in the same order, and take them out in reverse order.

Now we can create an algorithm for translating any infix notation into the RPN and name it after ourselves. Unfortunately, we are way too late. Edsger Dijkstra invented this algorithm in 1950.

Shunting-yard algorithm in details

The algorithm for notation conversion is the shunting yard algorithm named after railway shunting yards because of the same basic concept. The conversion involves two strings: input and output. The process uses a stack. It stores operations that have not yet been added to the output line. Our program reads the input string character by character and performs some actions at every step. It depends on what character it has read.

The scheme below shows a railroad from New York to California with a branch line to Texas.

Each car represents a symbol of the expression. Cars should arrive in California in the order required for the RPN, so we need to change their positions on the way. These are the rules of how cars are moving:

1. Each car must stop before the railroad point. Then we determine their route.
2. Cars with variables always go straight to California and never go to Texas.
3. Cars with operators take the detour to Texas and then go to California.

Let's have a look at the case study:

Now, let's write down the algorithm itself, and not forget about the parentheses. The algorithm analyzes the expression from left to right:

1. If the algorithm encounters an operand, it immediately puts it in the output string.
2. If the algorithm encounters a left parenthesis, it puts it onto the stack.
3. If the algorithm encounters a right parenthesis, it places the elements from the stack in the output string until it finds the corresponding left parenthesis. Then it removes the parentheses.
4. If the algorithm encounters an operator, there can be several outcomes:

• If the operator's stack is empty, the algorithm puts an incoming operator onto the stack.
• If the incoming operator has higher precedence than the one currently at the top of the stack, the incoming operator is placed at the top of the stack.
• If the incoming operator has the same precedence, the top operator is extracted from the stack and pushed to the output string. The incoming operator is placed onto the stack.
• If the precedence of the incoming operator is lower, the top operator is extracted from the stack to the output string. The incoming operator is compared with the new vertex of the stack.

As you see, we have converted an expression from the infix notation to the postfix one. Now, all we have to do is a check-up.

Testing expressions using a stack

To test the result, we will use a stack again. However, instead of putting the operators onto it, we will add the operands. Let's do the following:

1. Convert an expression to the reverse Polish notation, as we already did.
2. Put the operands onto the stack without changing their order.
3. If you encounter an operator, make the top two operands accomplish the operation.
4. Put the result onto the stack.
5. After all counting, the final result remains at the top of the stack.

This is the stack of operations for the expression $(2 + 4)\cdot(4 + 6)$ with Postfix notation $2 4 + 4 6 + \cdot$ :

In the end, the number $60$ remains in our stack. Let's check whether it corresponds with the original expression:

$(2 + 4)\cdot(4 + 6) = 6\cdot10 = 60$

Great, it worked! Now we know how to teach a computer to count arithmetic expressions.

Conclusion

In this topic, we have learned how to convert the infix notation to the postfix one. We have familiarized ourselves with two algorithms: an algorithm that translates any infix notation into a postfix notation, and an algorithm for calculating expressions in RPN.