Home arrow C++ arrow Dijkstra`s Shunting Algorithm with STL and C++

Dijkstra`s Shunting Algorithm with STL and C++

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.

Author Info:
By: Gabor Bernat
Rating: 4 stars4 stars4 stars4 stars4 stars / 11
July 08, 2008
  1. · Dijkstra`s Shunting Algorithm with STL and C++
  2. · The Theory
  3. · Getting in Deep Waters
  4. · Epilogue

print this article

Dijkstra`s Shunting Algorithm with STL and C++
(Page 1 of 4 )

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.

blog comments powered by Disqus

- Intel Threading Building Blocks
- Threading Building Blocks with C++
- Video Memory Programming in Text Mode
- More Tricks to Gain Speed in Programming Con...
- Easy and Efficient Programming for Contests
- Preparing For Programming Contests
- Programming Contests: Why Bother?
- Polymorphism in C++
- Overview of Virtual Functions
- Inheritance in C++
- Extending the Basic Streams in C++
- Using Stringstreams in C++
- Custom Stream Manipulation in C++
- General Stream Manipulation in C++
- Serialize Your Class into Streams in C++

Watch our Tech Videos 
Dev Articles Forums 
 RSS  Articles
 RSS  Forums
 RSS  All Feeds
Write For Us 
Weekly Newsletter
Developer Updates  
Free Website Content 
Contact Us 
Site Map 
Privacy Policy 

Developer Shed Affiliates


© 2003-2019 by Developer Shed. All rights reserved. DS Cluster - Follow our Sitemap
Popular Web Development Topics
All Web Development Tutorials