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.
Next: Epilogue >>
More C++ Articles
More By Gabor Bernat
/ 5 
