BOJ 4817 괄호

struct Node{
    char type;
    char var;
    Node *left, *right;

    Node(char c){ // var
        type = 'v';
        var = c;
        left = right = nullptr;
    }

    Node(char op, Node *l, Node *r){ // op
        type = 'o';
        var = op;
        left = l;
        right = r;
    }
};

struct AST{
    Node *root;

    AST(Node *r) : root(r) {}

    string emit(Node *n, char parOp){
        if(n->type == 'v') return string(1, n->var);
        if(n->var == '+'){
            string L = emit(n->left, '+');
            string R = emit(n->right, '+');
            if(parOp == '*') return "(" + L + "+" + R + ")";
            return L + "+" + R;
        }

        return emit(n->left, '*') + emit(n->right, '*');
    }

    string toString(){
        return emit(root, 0);
    }
};

struct Parser{
    const string &S;
    int pos;

    Parser(const string &s): S(s), pos(0){}

    Node *parseVal(){
        if(S[pos] == '('){
            pos++;
            Node *node = parsePlus();
            pos++;
            return node;
        }
        return new Node(S[pos++]);
    }

    Node *parseMul(){
        Node *node = parseVal();
        while(pos < (int)S.size() && (islower(S[pos]) || S[pos] == '(')){
            Node *right = parseVal();
            node = new Node('*', node, right);
        }
        return node;
    }

    Node *parsePlus(){
        Node *node = parseMul();
        while(pos < (int)S.size() && S[pos] == '+'){
            pos++;
            Node *right = parseMul();
            node = new Node('+', node, right);
        }
        return node;
    }

    AST parse(){
        return AST(parsePlus());
    }
};

void solve(){
    string S;
    while(cin >> S){
        Parser parser(S);
        AST ast = parser.parse();
        cout << ast.toString() << "\n";
    }
}