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: