# 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:

### 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 == "^");
}
```

### Illustrations:

1. Otto says:

This is great. but shunting yard method and your code creates postfix notation not prefix notation.

Liked by 1 person

• Harrison Howard says:

The title is still incorrect

Like

2. Bogdan says:

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

3. Bex Spivey says:

Hi – How would i change the C# code to print the outcome to the screen ? I am wanting to take user input for the infix equation and then print to screen the postfix equation once it has been determined ?

Like

• you can simply append tokens to a string and print it out using WriteLine, if I’m understanding you correctly?

Like