Build Binary Expression Tree From Infix Expression

hard tree stack expression parsing

Problem

Given a valid infix arithmetic expression s using single-digit operands, the operators + - * /, and parentheses, build its binary expression tree. Internal nodes hold operators, leaves hold operands, and an in-order traversal (with parentheses) reproduces the expression. Return the root.

Inputs = "2-3/(5*2)+1"

Outputroot of the tree for ((2 - (3 / (5 * 2))) + 1)

Precedence and parentheses determine the shape; evaluating the tree gives 2 - 0.3 + 1 = 2.7.

infix expression (single-digit operands)

def expTree(s):
    prec = {'+': 1, '-': 1, '*': 2, '/': 2}
    ops, nodes = [], []
    def combine():
        op = ops.pop()
        right = nodes.pop()
        left = nodes.pop()
        nodes.append(Node(op, left, right))
    for c in s:
        if c == '(':
            ops.append(c)
        elif c == ')':
            while ops[-1] != '(':
                combine()
            ops.pop()
        elif c in prec:
            while ops and ops[-1] != '(' and prec[ops[-1]] >= prec[c]:
                combine()
            ops.append(c)
        else:
            nodes.append(Node(c))
    while ops:
        combine()
    return nodes[0]

function expTree(s) {
  const prec = { '+': 1, '-': 1, '*': 2, '/': 2 };
  const ops = [], nodes = [];
  function combine() {
    const op = ops.pop();
    const right = nodes.pop();
    const left = nodes.pop();
    nodes.push(new Node(op, left, right));
  }
  for (const c of s) {
    if (c === '(') {
      ops.push(c);
    } else if (c === ')') {
      while (ops[ops.length - 1] !== '(') combine();
      ops.pop();
    } else if (prec[c]) {
      while (ops.length && ops[ops.length - 1] !== '(' && prec[ops[ops.length - 1]] >= prec[c]) combine();
      ops.push(c);
    } else {
      nodes.push(new Node(c));
    }
  }
  while (ops.length) combine();
  return nodes[0];
}

import java.util.*;
class Solution {
    public Node expTree(String s) {
        Map<Character,Integer> prec = Map.of('+',1,'-',1,'*',2,'/',2);
        Deque<Character> ops = new ArrayDeque<>();
        Deque<Node> nodes = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                ops.push(c);
            } else if (c == ')') {
                while (ops.peek() != '(') combine(ops, nodes);
                ops.pop();
            } else if (prec.containsKey(c)) {
                while (!ops.isEmpty() && ops.peek() != '(' && prec.get(ops.peek()) >= prec.get(c))
                    combine(ops, nodes);
                ops.push(c);
            } else {
                nodes.push(new Node(c));
            }
        }
        while (!ops.isEmpty()) combine(ops, nodes);
        return nodes.peek();
    }
    void combine(Deque<Character> ops, Deque<Node> nodes) {
        char op = ops.pop();
        Node right = nodes.pop(), left = nodes.pop();
        nodes.push(new Node(op, left, right));
    }
}

class Solution {
public:
    void combine(stack<char>& ops, stack<Node*>& nodes) {
        char op = ops.top(); ops.pop();
        Node* right = nodes.top(); nodes.pop();
        Node* left = nodes.top(); nodes.pop();
        nodes.push(new Node(op, left, right));
    }
    Node* expTree(string s) {
        unordered_map<char,int> prec = {{'+',1},{'-',1},{'*',2},{'/',2}};
        stack<char> ops; stack<Node*> nodes;
        for (char c : s) {
            if (c == '(') ops.push(c);
            else if (c == ')') {
                while (ops.top() != '(') combine(ops, nodes);
                ops.pop();
            } else if (prec.count(c)) {
                while (!ops.empty() && ops.top() != '(' && prec[ops.top()] >= prec[c])
                    combine(ops, nodes);
                ops.push(c);
            } else nodes.push(new Node(c));
        }
        while (!ops.empty()) combine(ops, nodes);
        return nodes.top();
    }
};

Explanation

This is the classic shunting-yard algorithm, but instead of emitting postfix tokens we build tree nodes directly. We scan left to right keeping two stacks: nodes for operand/subexpression nodes, and ops for operators and open parentheses.

An operand becomes a leaf node and is pushed onto nodes. To combine, we pop one operator and the top two nodes, making them the operator's right and left children (right is popped first), then push the new subtree back.

When we read an operator, we first combine while the operator on top of ops has greater-or-equal precedence (so *// bind before +/-, and equal precedence associates left-to-right), then push the new operator. An open paren is pushed as a barrier; a close paren combines everything back to the matching ( and discards both parens.

After the scan, any leftover operators are combined. The single node remaining in nodes is the root of the expression tree.

Example: 2-3/(5*2)+1 builds 5*2 first (inside parens), then 3/(…), then 2-(…), and finally (…)+1, giving the tree for ((2 - (3 / (5 * 2))) + 1).

Time: O(n) Space: O(n)