Question

Implement an infix expression to postfix expression convertor in C++.

Note: - Support +, -, *, /, ( and ) in infix expressions.

- Operands will be nonnegative only.

- Assume infix expressions are valid and well formatted (one blank space to separate operand/operator)

For example,

- 3 * 4 + 5 ➔ 3 4 * 5 +

- 3 + 4 * 5 ➔ 3 4 5 * +

- (3 + 4) * (5 + 6) ➔ 3 4 + 5 6 + *

Answer 1

#include<bits/stdc++.h>
using namespace std;
  
//Function to return precedence of operators
int precedence(char c)
{
if(c == '^')
return 3;
else if(c == '*' || c == '/')
return 2;
else if(c == '+' || c == '-')
return 1;
else
return -1;
}
  
// The main function to convert infix expression
//to postfix expression
void infixToPostfix(string s)
{
std::stack<char> st;
st.push('N');
int l = s.length();
string ns;
for(int i = 0; i < l; i++)
{
// If the scanned character is an operand, add it to output string.
if((s[i] >= '0' && s[i] <= '9'))
ns+=s[i];
  
// If the scanned character is an ‘(‘, push it to the stack.
else if(s[i] == '(')
  
st.push('(');
  
// If the scanned character is an ‘)’, pop and to output string from the stack
// until an ‘(‘ is encountered.
else if(s[i] == ')')
{
while(st.top() != 'N' && st.top() != '(')
{
char c = st.top();
st.pop();
ns += c;
}
if(st.top() == '(')
{
char c = st.top();
st.pop();
}
}
  
//If an operator is scanned
else{
while(st.top() != 'N' && precedence(s[i]) <= precedence(st.top()))
{
char c = st.top();
st.pop();
ns += c;
}
st.push(s[i]);
}
  
}
//Pop all the remaining elements from the stack
while(st.top() != 'N')
{
char c = st.top();
st.pop();
ns += c;
}
  
cout << ns << endl;
  
}
  
//Driver program to test above functions
int main()
{
string exp = "3*4+5";
infixToPostfix(exp);
exp = "3+4*5";
infixToPostfix(exp);
exp = "(3+4)*(5+6)";
infixToPostfix(exp);
return 0;
}

output: