Infix to Postfix Expression

Infix to Postfix Expression

Infix expression:The expression of the form a op b. When an operator is in-between every pair of operands.

Postfix expression:The expression of the form a b op. When an operator is followed for every pair of operands.

PROBLEM STATEMENT :

Transform the algebraic expression with brackets into postfix form. Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,...,z. Assume that there is only one f=postfix form (no expressions like a*b*c).

Input :

t [the number of expressions <= 100]

expression [length <= 400]

[other expressions]

Text grouped in [ ] does not appear in the input file.

Output :

The expressions in postfix form, one per line.

Example

Input:

3

(a+(b*c))

((a+b)*(z+x))

((a+t)*((b+(a+c))^(c+d)))

Output:

abc*+

ab+zx+*

at+bac++cd+^*

SOLUTION : 

Note : We can solve this problem using STACK.

#include <bits/stdc++.h>
int priority(char c)
{
    if(c=='+'||c=='-') return 1;
    else if(c=='*'||c=='/') return 2;
    else if(c=='^') return 3;
    return -1;
}
using namespace std;

int main() {
	int t,i;
	cin>>t;
	stack<char> st;
	while(t--)
	{
	    string s;
	    cin>>s;
	    for(i=0;i<s.size();++i)
	    {
	        if(isalnum(s[i]))
	        {
	            cout<<s[i];
	        }
	        else if(s[i]=='(')
	        {
	            st.push(s[i]);
	        }
	        else if(s[i]==')')
	        {
	            while(st.top()!='(')
	            {
	                cout<<st.top();
	                st.pop();
	            }
	            st.pop();
	        }
	        else
	        {
	            while(priority(st.top())>=priority(s[i]))
	            {
	                cout<<st.top();
	                st.pop();
	            }
	            st.push(s[i]);
	        }
	    }
	    while(!st.empty()) 
	    {
	        cout<<st.top();
	        st.pop();
	    }
	    cout<<"\n";
	}
	return 0;
}

Never Stop Learning !!