Home arrow C++ arrow Page 3 - Dijkstra`s Shunting Algorithm with STL and C++
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
TABLE OF CONTENTS:
  1. · Dijkstra`s Shunting Algorithm with STL and C++
  2. · The Theory
  3. · Getting in Deep Waters
  4. · Epilogue

print this article
SEARCH DEVARTICLES

Dijkstra`s Shunting Algorithm with STL and C++ - Getting in Deep Waters
(Page 3 of 4 )

We already observed from the previous section that if we build an expression tree with a simple postfix traversal of the tree, Reverse Polish Form is already acquired and solution isn't too far away. However, it looks as if building up the expression tree takes more resources and frustration that it should. Back in 1960 when Dijkstra himself faced this problem, he managed to figure out an optimal and also quite easy to behold algorithm.

The Shunting algorithm is a method for transforming mathematical expressions from the infix representation (what we write in our everyday life) to postfix/suffix/Reverse Polish form. The algorithm, just like the evaluation, is based on stacks.

The main idea is to get each token, item by item, from the input; if it is a number it will be added to the output stack. If it is an operator, which has a greater priority, we need to delay it until we find a lower one, and to accomplish this we must add the operator in another stack.

For implementing the algorithm I decided to create a class that will contain three data members: one for the infix form, one for the Polish form, and a final one that contains any error message which may occur. By choosing this path you can create, in the case of a compiler type expression, a sort of precompiled header since you may only need to check in those segments for mistakes where something additional was added.

To start, we need to define the operators and the applied priorities for them.

0)      =

1)      &&, ||

2)      !

3)      ==, != , <, > , <=, >=

4)      +, -

5)      *, /, %

6)      ~ (replaces the - (negative)), ^

Additionally we'll note with -1 the priority for "(" and -2 the ")". For fast search of the priority we should use a map with the following declaration:

map<std::string,int> operator_Priority;

So with an operator_Priority["+"] for example we can find in minimal time the priority of the operator. But first let's see the code which manages the conversion part in order to understand more easily. First, declare a stack to hold the delayed operators and a string for the output, if we want to save the resulting expression for a later time and not just evaluate the expression. If you want only to evaluate the expression, then another stack should be enough. And we start iteration for each token from the input data.

stack<string> stackOperator;//delayed operator's stack

string token;

 

while( (type =nextToken(token)))

{

Now we act according to what type we have. First, the simpler ones: the parentheses. This is quite simple because whenever we find a "(" we just simply add it to the operator stack. Now as the "(" has a low priority, every other operator will go to the operator stack from now on -- at least until we get the closing match.

As soon as we have a closing parenthesis we start to go step-by-step through each item from the operator stack and push it to the end of the resulting expression. If, for whatever reason, we run out of operators on the operator stack and we still don't have the closing one, then we have an invalid data input that is lacking a ")" somewhere in it.

I have also implanted in the class a member for containing the error message for whatever reason the program fails to complete. By this I tried to bring this expression evaluator closer to the compilers as, upon failure, you can ask for the current error message from the class and display it on the screen so the user can make the needed correction without being forced to observe for himself what the problem is in the input data. Additionally, the 0 type stands for invalid type as a result and invalid data entry.

switch(type)

{

case -1: // ( -> Push it on the delayed stack

{ stackOperator.push(token); break;}

case -2: // )

{

do {

if(stackOperator.empty()) {

error = "A unmatched ) operator has been found";

return false; }

topOperator = stackOperator.top();

 

if(topOperator != "(")

polishForm.push_back(topOperator); //add

stackOperator.pop(); //delete

}while(topOperator != "(" );

break;

}

case 0: // number

{

return false; break; } // error code

Now we have the issue of operators. Regardless of the type of the operator (unary or binary) the same steps should be covered, and due to the wisely created operator priority list we can kill two birds with one stone. So here it goes.

Moreover, unless we have an invalid operator we need to move to the output/polishForm all operators which are of lower priority until we find one which has a higher priority.

case 1: //unary operator

case 2: // binary operator -> cover them together

{

tokenPriority = priority(token);

if(tokenPriority == -3) // invalid operator

return false;

do

{

if (stackOperator.empty( ))

break;

else

{

topOperator = stackOperator.top();

 

iteratingPriority = priority(topOperator);

if(iteratingPriority == -1 || iteratingPriority < tokenPriority || iteratingPriority == 6)

break; //finish the iteration

else

{

polishForm.push_back(topOperator);

stackOperator.pop(); // remove the item from the stack }

}

}while(!stackOperator.empty());

 

stackOperator.push(token);

break;

}

If we have a number, simply add it to the polishForm. At the end, when we run out of tokens, we need to get each item from the stack and add it to the output.

case 3: //number

{

polishForm.push_back(token); //convert token and add

break;

}

 

}

}

while (!stackOperator.empty()) //what remained just add it

{

if(stackOperator.empty()) {

error = "A unmatched ) operator has been found";

return false;

}

topOperator = stackOperator.top(); //assign

polishForm.push_back(topOperator); //add

stackOperator.pop(); //delete

}

And that is it; with this little extra work we have created the code capable of making the transfer. Now apply the lesson learned on the previous page to this output/polishForm vector and the result will be at your disposal.

The class is written as a template so you can evaluate the expression just as easily with double, float, and even more. You may even use a specific class which handles large numbers or very precise ones if the specific operators for it are defined. If you are one of those really brave programmers I have also written an introduction to how to write yourself a class like this. It's a two-part series, and it will published soon here on ASP Free.


blog comments powered by Disqus
C++ ARTICLES

- 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 
Support 

Developer Shed Affiliates

 




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