# 1597. Build Binary Expression Tree From Infix Expression

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 class Solution { public: Node* expTree(string s) { stack nodes; // Stores nodes (new Node(val)). stack ops; // Stores operators and parentheses. for (const char c : s) if (isdigit(c)) { nodes.push(new Node(c)); } else if (c == '(') { ops.push(c); } else if (c == ')') { while (ops.top() != '(') nodes.push(buildNode(pop(ops), pop(nodes), pop(nodes))); ops.pop(); // Remove '('. } else if (c == '+' || c == '-' || c == '*' || c == '/') { while (!ops.empty() && compare(ops.top(), c)) nodes.push(buildNode(pop(ops), pop(nodes), pop(nodes))); ops.push(c); } while (!ops.empty()) nodes.push(buildNode(pop(ops), pop(nodes), pop(nodes))); return nodes.top(); } private: Node* buildNode(char op, Node* right, Node* left) { return new Node(op, left, right); } // Returns true if op1 is a operator and priority(op1) >= priority(op2) bool compare(char op1, char op2) { if (op1 == '(' || op1 == ')') return false; return op1 == '*' || op1 == '/' || op2 == '+' || op2 == '-'; } char pop(stack& ops) { const char op = ops.top(); ops.pop(); return op; } Node* pop(stack& nodes) { Node* node = nodes.top(); nodes.pop(); return node; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 class Solution { public Node expTree(String s) { Deque nodes = new ArrayDeque<>(); // Stores nodes (new Node(val)). Deque ops = new ArrayDeque<>(); // Stores operators and parentheses. for (final char c : s.toCharArray()) if (Character.isDigit(c)) { nodes.push(new Node(c)); } else if (c == '(') { ops.push(c); } else if (c == ')') { while (ops.peek() != '(') nodes.push(buildNode(ops.pop(), nodes.pop(), nodes.pop())); ops.pop(); // Remove '('. } else { // c == '+' || c == '-' || c == '*' || c == '/' while (!ops.isEmpty() && compare(ops.peek(), c)) nodes.push(buildNode(ops.pop(), nodes.pop(), nodes.pop())); ops.push(c); } while (!ops.isEmpty()) nodes.push(buildNode(ops.pop(), nodes.pop(), nodes.pop())); return nodes.peek(); } private Node buildNode(char op, Node right, Node left) { return new Node(op, left, right); } // Returns true if op1 is a operator and priority(op1) >= priority(op2) boolean compare(char op1, char op2) { if (op1 == '(' || op1 == ')') return false; return op1 == '*' || op1 == '/' || op2 == '+' || op2 == '-'; } }