Skip to content

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<Node*> nodes;
    stack<char> ops;  // [operators | 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<char>& ops) {
    const char op = ops.top();
    ops.pop();
    return op;
  }

  Node* pop(stack<Node*>& 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<Node> nodes = new ArrayDeque<>();
    Deque<Character> ops = new ArrayDeque<>(); // [operators | 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 == '-';
  }
}