727 Equation

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <list>
#include <climits>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iomanip>
using namespace std;
/*** typedef ***/
#define MEMSET_INF 127
#define MEMSET_HALF_INF 63
#define stream istringstream
#define rep(i,n) for(__typeof(n) i=0; i<(n); i++)
#define repl(i,n) for(__typeof(n) i=1; i<=(n); i++)
#define FOR(i,a,b) for(__typeof(b) i=(a); i<=(b); i++)
#define INF (1<<30)
#define PI acos(-1.0)
#define pb push_back
#define ppb pop_back
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof(x))
#define memsp(x) mem(x,MEMSET_INF)
#define memdp(x) mem(x,-1)
#define memca(x) mem(x,0)
#define eps 1e-9
#define pii pair<int,int>
#define pmp make_pair
#define ft first
#define sd second
#define vi vector<int>
#define vpii vector<pii>
#define si set<int>
#define msi map<string , int >
#define mis map<int , string >
typedef long long i64;
typedef unsigned long long ui64;
/** function **/
#define SDi(x) sf("%d",&x)
#define SDl(x) sf("%lld",&x)
#define SDs(x) sf("%s",x)
#define SD2(x,y) sf("%d%d",&x,&y)
#define SD3(x,y,z) sf("%d%d%d",&x,&y,&z)
#define pf printf
#define print(x) pf("%d ", x)
#define println(x) pf("%d\n", x)
#define sf scanf
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)

/** My algorithm:
 * Define a stack
 * Go through each character in the string
 * If it is between 0 to 9, append it to output string.
 * If it is left brace push to stack
 * If it is operator *+-/ then
         * If the stack is empty push it to the stack
         * If the stack is not empty then start a loop:
                             * If the top of the stack has higher precedence
                                 * Then pop and append to output string
                             * Else break
                     * Push to the stack

* If it is right brace then
            * While stack not empty and top not equal to left brace
               * Pop from stack and append to output string
               * Finally pop out the left brace.

* If there is any input in the stack pop and append to the output string
**/

stack <char> Stack;
vector <char> output;
queue <char> input;

bool isOperator(char c) {

    if(c == '*' || c == '/' || c == '+' || c == '-' )
        return true;

    return false;
}

bool hasHigherPrecedence(char top, char c) {

    if((top == '*' || top == '/') && (c == '-' || c == '+'))
        return true;

    if((top == '+' || top == '-') && (c == '+' || c == '-'))
        return true;

    if((top == '*' || top == '/') && (c == '/' || c == '*'))
        return true;

    return false;
}

void infixToPostfix() {

    Stack = stack <char> ();
    output.clear();

    while(!input.empty()) {

        char front = input.front();
        input.pop();

        if(isdigit(front))
            output.pb(front);

        else if(front == '(')
           Stack.push(front);

        else if(isOperator(front)) {
            while(!Stack.empty()) {
                char top = Stack.top();
                if(top != '(' && hasHigherPrecedence(top, front))
                    output.pb(top), Stack.pop();
                else break;
            }
            Stack.push(front);
        }

        else if(front == ')') {
            while(!Stack.empty()) {
                char top = Stack.top();
                Stack.pop();
                if(top == '(')
                    break;
                output.pb(top);
            }
        } else {
            //nothing
        }
    }

    while(!Stack.empty()) {
        char top = Stack.top();
        output.pb(top), Stack.pop();
    }
}

int main() {
    #ifndef ONLINE_JUDGE
        READ("input.txt");
    #endif
    int tcase;
    SDi(tcase);
    bool blank = true;
    char ch[2];
    getchar(), getchar();
    while(tcase--) {
        while(gets(ch) && strlen(ch)) {
            input.push(ch[0]);
        }

        infixToPostfix();
        rep(i, output.size()) pf("%c", output[i]);
        pf("\n");
        if(!tcase) blank = false;
        if(blank) pf("\n");
    }
    return 0;
}