In 1993 Alex Stepanov wrote the STL library. The library redefined the way people code in C/C++. Using it gradually became synonymous with elegance and speed. Later, as STL fought its way into the standards, it became even more popular and the numbers of people who used it increased exponentially. In the first two parts of this article series I presented the basics of STL; in this third part I will show you more complex code. You’ll also learn how to write an expression evaluator/compiler.
Dijkstra`s Shunting Algorithm with STL and C++ - The Theory (Page 2 of 4 )
Before looking deeper into the aforementioned Dijkstra's algorithm we should understand what we need to accomplish with it. And for this, we need to return to the binary trees. Yes, you read that right-binary trees. We are given the following expression:
Now we're going to build from it an expression tree. An expression tree is a binary tree with the following main properties: the leaves are operands (numbers), while the interior vertices are operators. According to this we can create the following tree:
Now let's traverse the tree in a postfix way. This would result in the following expression:
2 ! 3 4 2 ^ * +
From here the expression can be evaluated effortlessly thanks to a genius Polish mathematician named JAN ŁUKASIEWICZ. In his memory the upper notation is named reverse Polish notation (RPN). Simplifying the problem to given numbers 3 and 4, Polish notation is called if we write first the operatorfollowed by the operands, like this:
+ 3 4
And we talk about reverse Polish notation when there are first, the operands, and the operators are standing on the final positions. This is the same thing we have acquired after traversing the tree using the postfix form; it's just that we applied it recursively for more numbers/operators. Strictly on two numbers it looks like this:
3 4 +
If you still don't see how we can now solve the problem easily, let me put it in a different light. Take "a" and "b" numbers and the operator *. The evaluation can be made in different ways, depending upon which class we are currently using. We may say we have "a" and we need to multiply it with "b" on a math class.
Using Polish notation, we would say that we have operator * and we need to apply it to the following two numbers: "a" and "b". Now you can easily figure out that fort Reverse Polish Notation this would transform into a take number "a" and "b" and execute upon them collectively the * operator.
Of course, there are two types of operators: binary and unary. Binaries need to have arguments, however, a unary operator only needs one number. So for the unary operator we only need to take the number "b" into account. Apply the upper method for the RPN way of showing the result after Reverse Polish Notation and, once we finish the iteration through the expression the result should be at hand.
Calculating the input from the binary tree is reduced to iterating through RPN expressions -- when we find an operator, we execute it on the previous two (or one depending on the type of the operator) numbers. A step-by-step approach is below:
1)First item 2, no operator, put it in a stack.
2)Second item operator, unary. Get the last item from the stack and evaluate the operator on the number. Put the result back into the stack.
3)Third item number. Push it onto the stack.
4)Fourth item will be treated just as the previous one
5)Fifth item will be treated the same as the third and fourth items.
6)Sixth and the following are all binary operators, so we take the last two items form the stack. Evaluate them according to the operator and finally put the result back into the stack.
Following the stack's evaluation we shall see the following.
2)0 // because !2 = 0
4)0 3 4
5)0 3 4 2
6)0 3 16 // because 4^2 = 16
7)0 48 // because 3 * 16 = 48
8)48 // because 0+ 48 = 48
What we have at the end in the stack is the outcome/result. If we have more than one item, we have an invalid input expression. Now that we know how to calculate the result, the question remains: how do we form, in a simple and an efficient way, Reverse Polish Notation? Here Edsger Dijkstra and his "Shunting algorithm" enter the picture. The name comes from the fact that the algorithm resembles that of a railroad shunting yard.