Dijkstra`s Shunting Algorithm with STL and C++
(Page 1 of 4 )
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.
The structure of the article will be the following: first, I will approach the problem of evaluating an arithmetic expression, how it can be completed and how we can make it simple. Here I should discuss the advantages of Reverse Polish notation, because, as you will see, evaluating an expression is almost child's play with it.
In the second part of this article, I'll approach the implementation problems, how Dijkstra's algorithm works, and I'll also present some code samples. The code will be full of STL and even include some templates, so I hope you have practiced to develop your knowledge of STL after you finished reading the first two parts and also the article covering C++ templates (search for it, too).
To understand the blocks of code, the information in those articles will be just as crucial as air in order to breathe. If you haven't until now I advise you to suspend this article and read those first.
In the early days of programming the first issue faced by the designers was how to create/allow the programmer to write an expression which is pretty close to the real mathematical form and evaluate it. It was crucial to be pretty close to the mathematical form as learning a new syntax and thinking about complex expressions in such a different way could overly complicate the life of the programmer and scare people away from new technologies. This was never an option.
Let's think about the problem a little. We have an expression like this:
!(x+y)*36+48/26*exp(3 && 4)
But as you will see later on, a simple idea implemented in an efficient and elegant way can reduce this scary-looking problem. However, back then getting a correct machine output was one of the biggest breakthroughs. In fact, in recognition of this, the first main programming language was named FORTRAN (it stands for FORMULA TRANSLATOR).
The main strength of the method that's going to be presented is that it doesn't need to do a repeated iteration through the expression, or to take account of the operator priorities or parentheses upon the evaluation. For this we'll first transform our input expression so that we'll only need to conduct iteration on the expression and find out the result. Let's start with the theory part.
Next: The Theory >>
More C++ Articles
More By Gabor Bernat
/ 6 
