/**
 * Definition for a binary tree node.
 * struct Node {
 *     char val;
 *     Node *left;
 *     Node *right;
 *     Node() : val(' '), left(nullptr), right(nullptr) {}
 *     Node(char x) : val(x), left(nullptr), right(nullptr) {}
 *     Node(char x, Node *left, Node *right) : val(x), left(left), right(right) {}
 * };
 */
// struct Node {
//     char val;
//     Node *left;
//     Node *right;
//     Node() : val(' '), left(nullptr), right(nullptr) {}
//     Node(char x) : val(x), left(nullptr), right(nullptr) {}
//     Node(char x, Node *left, Node *right) : val(x), left(left), right(right) {}
// };

class Solution {
    stack<Node*> nodes;
    stack<char> ops;
    int priority[256] = {
        ['+'] = 1,
        ['-'] = 1,
        ['*'] = 2,
        ['/'] = 2
    };
public:
    void calc() {
        Node *right = nodes.top(); nodes.pop();
        Node *left = nodes.top(); nodes.pop();
        char op = ops.top(); ops.pop();
        nodes.push(new Node(op, left, right));
    }
    Node* expTree(string s) {
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (isdigit(s[i])) {
                nodes.push(new Node(s[i]));
            } else if (s[i] == '(') {
                ops.push(s[i]);
            } else if (s[i] == ')') {
                while (!ops.empty() && ops.top() != '(') {
                    calc();
                }
                ops.pop(); // pop '('
            } else {
                while (!ops.empty() && ops.top() != '(' && priority[ops.top()] >= priority[s[i]]) {
                    calc();
                }
                ops.push(s[i]);
            }
        }
        while (nodes.size() != 1) {
            calc();
        }
        return nodes.top();
    }
};