ONP : Transform the Expression

ONP: Transform the Expression


Link for the Problem: ONP


SOLUTION:

In this problem, we have to convert given infix expression to postfix expression. To know more about postfix expression follow the link: Postfix wiki.

IMPLEMENTATION:

In the input string, we will encounter four types of characters-
1.) Opening bracket '('
2.) Closing bracket ')'
3.) Operands
4.) Operators {+,-,*,/}
To solve this problem, we will traverse from left in the string.
i) If the character is '(', Push it in the stack.
ii) If it is an operand character, then print it.
iii) If it is an operator, the push it in the stack.
iv) if it is ')' i.e. closing bracket, then print the top of the stack and pop the stack until we get '(' as top.
     pop '(' also from the stack.


CODE:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        string s;
        cin>>s;
        int l;
        l=s.size();
        stack <char> st;
        int i,j,k;
        for(i=0;i<l;i++)
        {
            if(s[i]=='(')
            {
                st.push(s[i]);
            }
            else if(s[i]>='a'&&s[i]<='z')
            {
                cout<<s[i];
            }
            else if(s[i]==')')
            {
                while(st.top()!='(')
                {
                    cout<<st.top();
                    st.pop();
                }
                st.pop();
            }
            else
            st.push(s[i]);
        }
        cout<<endl;
    }
    return 0;

}