Solution UVA: 727 - Equation

 

#

Problem

Verdict

Language

Run Time

Submission Date

28543935

727

Equation

Accepted

C++11

0.020

2023-06-13 16:28:33

Problem: 727

Suggest:

Algorithm for converting an infix expression to postfix:

If an operand is encountered (a number or a variable), write it to the output (the output string is the infix expression).

If an opening parenthesis is encountered, push it onto the stack.

If an operator is encountered (let's call it t1), perform the following steps:

If the stack is not empty and there is an operator t2 at the top of the stack, and the precedence of t1 is less than or equal to the precedence of t2, pop t2 from the stack and write it to the output.

If the stack is empty or the operator t2 at the top of the stack has lower precedence than t1, push t1 onto the stack.

If a closing parenthesis is encountered, repeatedly pop operators from the stack and write them to the output until an opening parenthesis is popped from the stack.

After traversing the entire infix expression, sequentially pop all operands (if any) from the stack and write them to the output string.

Here is the table illustrating the conversion process for the infix expression (2 * 3 + 7 / 8) * (5 - 1):

The final output is 2 3 * 7 8 / + 5 1 - * which represents the postfix expression corresponding to the given infix expression.

#include<bits/stdc++.h>

using namespace std;

int t;

string s;

int priority(char x){

    if (x == '*' || x== '/') return 3;

    if (x == '+' || x== '-') return 2;

    if (x == '(') return 1;

    return 0;

}

       

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

   

    cin >> t;

    getline(cin, s);

    getline(cin, s);

    while(t--){

        stack<char> st;

        while(getline(cin, s)){

            if (s=="") break;

           

            if ('0' <= s[0] && s[0] <= '9')

                cout<<s[0];

            else

            if (s[0] == '(') st.push(s[0]);

            else

            if (s[0] == ')'){

                 while (st.top()!='('){

                    cout<<st.top();

                    st.pop();

                }

                st.pop();

            }

            else{

                while(!st.empty() && priority(s[0]) <= priority(st.top())){

                    cout<<st.top();

                    st.pop();

                }

                st.push(s[0]);

            }

        }

        while(!st.empty()){

            cout<<st.top();

            st.pop();

        }

        cout << "\n";

        if (t) cout << "\n";

    }

}