Convert infix to postfix notation C++/C# implementation (shunting yard method)


Suppose we wanted to convert a mathematical expression like 3^4+(11-(3*2))/2 into a reverse polish notation expression to evaluate the answer. This is called an infix expression. To convert it(to be able to evaluate the expression as well), we will use shunting yard algorithm. This algorithm is stack based and also includes an output list. The stack will handle operators, and the output queue will handle numbers.

Algorithm explained:

Step 1:

Scan the Infix expression from left to right for tokens (Operators, Operands & Parentheses) and perform the steps 2 to 5 for each token in the Expression

Step 2:

If token is operand, Append it in postfix expression

Step 3:

If token is a left parentheses “(“, push it in stack.

Step 4:

If token is an operator,
Pop all the operators which are of higher or equal precedence then the incoming token and append them (in the same order) to the output Expression.
After popping out all such operators, push the new token on stack.

Step 5:

If “)” right parentheses is found,
Pop all the operators from the Stack and append them to Output String, till you encounter the Opening Parenthesis “(“.
Pop the left parenthesis but don’t append it to the output string (Postfix notation does not have brackets).

Step 6:

When all tokens of Infix expression have been scanned. Pop all the elements from the stack and append them to the Output String.

The Output string is the Corresponding Postfix Notation.

Step 7:

     Exit or evaluate rpn and return final result

C++ implementation

#include <iostream>
#include <iterator>
#include <stack>
#include <sstream>
#include <vector>
#include <main.h>
using namespace std;

bool TryParse(const string &symbol);
int Priority(const string &c);
bool isOperator(const string &c);
int main()
{
    string infix = "3 ^ 4 + ( 11 - ( 3 * 2 ) ) / 2";//our infix expression
    istringstream iss(infix);
    vector<string> tokens;//store the tokens here
    while(iss)
    {
        string temp;
        iss >>temp;
        tokens.push_back(temp);
    }
    vector<string> outputList;//output vector
    stack<string> s;//main stack

    //operator: +, -, *, /, ^, ()
    //operands: 1234567890
    for(unsigned int i = 0; i < tokens.size(); i++)  //read from right to left
    {
        if(TryParse(tokens[i]))
        {
            outputList.push_back(tokens[i]);
        }
        if(tokens[i] == "(")
        {
            s.push(tokens[i]);
        }
        if(tokens[i] == ")")
        {
            while(!s.empty() && s.top() != "(")
            {
                outputList.push_back(s.top());
                s.pop();
            }
            s.pop();
        }
        if(isOperator(tokens[i]) == true)
        {
            while(!s.empty() && Priority(s.top()) >= Priority(tokens[i]))
            {
                outputList.push_back(s.top());
                s.pop();
            }
            s.push(tokens[i]);
        }
    }
    //pop any remaining operators from the stack and insert to outputlist
    while(!s.empty())
    {
        outputList.push_back(s.top());
        s.pop();
    }

    for(unsigned int i = 0; i < outputList.size(); i++)
    {
        cout<<outputList[i];
    }
    return 0;
}
bool TryParse(const string &symbol)
{
    bool isNumber = false;
    for(unsigned int i = 0; i < symbol.size(); i++)
    {
        if(!isdigit(symbol[i]))
        {
            isNumber = false;
        }
        else
        {
            isNumber = true;
        }
    }
    return isNumber;
}
int Priority(const string &c)
{
    if(c == "^")
    {
        return 3;
    }
    if(c == "*" || c == "/")
    {
        return 2;
    }
    if(c== "+" || c == "-")
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
bool isOperator(const string &c)
{
    return (c == "+" || c == "-" || c == "*" || c == "/" || c == "^");
}

C# Implementation

Java Implementation

Illustrations:
Shunting_yard.svg

Advertisements

6 thoughts on “Convert infix to postfix notation C++/C# implementation (shunting yard method)

  1. Hello. The whole code is amazing, great job, but I’ve been wondering if you can replace typing the equation in program by typing it from the keyboard while running the program, so you can create something like a start for an advanced calculator. It turns out you can’t. I copied the entire code, but instead of line “string infix = “3 ^ 4 + ( 11 – ( 3 * 2 ) ) / 2”; i want to have string infix;
    cin>>infix;
    When I run the program, it gives me only the first token. Is there any chance of fixing that, or did I do something wrong? It would be really great if you would explain that to me

    Like

    • It looks like you need to store that input somewhere than just using cin>>. Use an array or vector to store that input. Here’s a hint to what you’re looking for:
      while (true)
      {
      cin >> number >> operator
      vector.push(number)
      stack.push(operator)
      }
      Hope this helps. Thanks for commenting!

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s