PROG-T1013: Expression

#include <bits/stdc++.h>
using namespace std;

struct node {
    char dat;
    vector<node*> nxt;
    node(char dat): dat(dat) {};
};

int prior(char c){
    if(c == '+'){
        return 1;
    } else if(c == '*'){
        return 2;
    } else if(c == '^'){
        return 3;
    }
    return -1;
}

node *fuse(node *f, node *op, node *s){
    if(f -> dat == op -> dat){
        f -> nxt.push_back(s);
        return f;
    }
    op -> nxt.push_back(f);
    op -> nxt.push_back(s);
    return op;
}

void inOrder(node *root){
    if(root -> dat == '('){
        cout << '(';
        inOrder(root -> nxt[0]);
        cout << ')';
        return;
    }
    if(root -> nxt.empty()){
        cout << root -> dat;
        return;
    }
    for(int i = 0; i < (int)(root -> nxt.size()) - 1; ++i){
        inOrder(root -> nxt[i]);
        cout << root -> dat;
    }
    inOrder(root -> nxt.back());
}

void query(node *root, int i, vector<int> &acc){
    if(i == acc.size()){
        inOrder(root);
        return;
    }
    if(acc[i] > root -> nxt.size()){
        if(acc[i] == 1){
            cout << root -> dat;
        } else {
            cout << "null";
        }
        return;
    }
    query(root -> nxt[acc[i] - 1], i + 1, acc);
}

int main(){

    string str;
    cin >> str;
    str = '(' + str + ')';
    stack<node*> stk;
    for(int i = 0; i < str.size(); ++i){
        char c = str[i];
        if(c == '('){
            stk.push(new node('('));
        } else if(c == ')'){
            node *s, *op, *f;
            while(!stk.empty()){
                s = stk.top();
                stk.pop();
                op = stk.top();
                stk.pop();
                if(op -> dat == '('){
                    stk.push(new node('('));
                    stk.top() -> nxt.push_back(s);
                    break;
                }
                f = stk.top();
                stk.pop();
                stk.push(fuse(f, op, s));
            }
        } else if(prior(c) != -1){
            node *s, *op, *f;
            while(!stk.empty()){
                s = stk.top();
                stk.pop();
                op = stk.top();
                stk.pop();
                if(op -> dat == '(' || prior(op -> dat) < prior(c)){
                    stk.push(op);
                    stk.push(s);
                    break;
                }
                f = stk.top();
                stk.pop();
                stk.push(fuse(f, op, s));
            }
            stk.push(new node(c));
        } else {
            stk.push(new node(c));
        }
    }
    node *root = stk.top() -> nxt[0];
    int Q;
    scanf("%d", &Q);
    while(Q--){
        vector<int> acc;
        while(true){
            int x;
            scanf("%d", &x);
            if(x == 0){
                break;
            }
            acc.push_back(x);
        }
        for(int i = (int)acc.size() - 1; i >= 0; --i){
            cout << "op(" << acc[i] << ',';
        }
        cout << 'p';
        for(int i = 0; i < acc.size(); ++i){
            cout << ')';
        }
        cout << '=';
        query(root, 0, acc);
        cout << '\n';
    }

    return 0;
}