1597. Build Binary Expression Tree From Infix Expression

Explanation

The given problem asks to construct a binary tree from an infix expression. An infix expression is an algebraic expression where operators appear in-between two operands.

The task requires determining the hierarchy of operations. Multiplication and division have higher priority than addition and subtraction. This is generally enforced using parentheses, but if they aren't present it's important to follow the order of precedence.

Consider an expression like: "2-3/(5*2)+1". Here, the operations must be organized in the following order:

1. Multiplication: 5*2
2. Division: 3/(5*2)
3. Subtraction: 2-3/(5*2)
4. Addition: 2-3/(5*2)+1

In binary tree representation, operators are internal nodes with 2 children, while operands (numbers) are leaf nodes with no children.

Solution Walkthrough

This problem involves the use of two stack data structures, nodes and ops. The nodes stack stores the operands and the expressions created so far. The ops stack keeps track of the operators appeared in the infix expression.

The solution makes use of algorithm postfixed expression (also known as Reverse Polish Notation - RPN), which is a mathematical notation where every operator follows all of its operands.

For each character in the string:

• If it's a number, create a new node and add it to the nodes stack.
• If it's an operator, then:
  • While the operator at the top of the ops stack has a priority equal or greater than the current operator, pop the operator and two nodes from the stacks and build a new node. Add this new node to the nodes stack.
  • Push the current operator onto the ops stack.
• If it's a '(', just push it onto the ops stack.
• If it's a ')', keep popping operators and building new nodes until we find a '(' in the ops stack. This will construct the binary tree for the expression inside the parentheses.

Once all characters have been processed, keep popping operators from the ops stack, building new nodes, until the ops stack is empty. The nodes stack will now have one item, which is the root of the binary tree.

Lastly, we just return the remaining node in the nodes stack which is the root of our binary expression tree.

Python

1
2
3class Solution:
4    def expTree(self, s: str) -> 'Node':
5        
6        def helper(stack):
7            node = stack.pop()
8            if node.val.isdigit():
9                return node
10            
11            node.right = helper(stack)
12            node.left = helper(stack)
13            return node
14        
15        stack = []
16        prec = {'+': 0, '-': 0, '*': 1, '/': 1}
17        num = ""
18        for c in reversed("("+s+")"):
19            if c.isdigit():
20                num += c
21                stack.append(Node(int(num)))
22                num = ""
23            elif c in prec:
24                while len(stack) > 1 and prec[stack[-2].val] >= prec[c]:
25                    stack.append(Node(stack.pop(), stack.pop(), stack.pop()))
26                stack.append(Node(c))
27            elif c == ")":
28                stack.append(Node(c))
29            elif c == "(" and len(stack) > 1:
30                while stack[-2].val != ")":
31                    stack.append(Node(stack.pop(), stack.pop(), stack.pop()))
32                stack.pop()
33        return helper(stack)

Java

1
2java
3class Solution {
4    public Node expTree(String s) {
5        Stack<Node> nodes = new Stack<>();
6        Stack<Character> ops = new Stack<>();
7        for(char c : s.toCharArray())
8            if(Character.isDigit(c)) nodes.push(new Node(String.valueOf(c)));
9            else if(c == '(') ops.push(c);
10            else if(c == ')') {
11                while(ops.peek() != '(') {
12                    nodes.push(build(ops.pop(), nodes.pop(), nodes.pop()));
13                }
14                ops.pop(); 
15            } else {
16                while(!ops.isEmpty() && ops.peek() != '(' && precedence(ops.peek()) >= precedence(c)) {
17                    nodes.push(build(ops.pop(), nodes.pop(), nodes.pop()));
18                }
19                ops.push(c);
20            }
21        while(!ops.isEmpty()) nodes.push(build(ops.pop(), nodes.pop(), nodes.pop()));
22        return nodes.pop();
23    }
24    
25    public static int precedence(char c){
26        if(c == '+' || c == '-')
27                return 1;
28            else if(c == '*' || c == '/')
29                return 2;
30            else
31                return 0;
32    }
33
34    public static Node build(char c, Node node1, Node node2) {
35        return new Node(String.valueOf(c), node2, node1);
36    }
37}

C++

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

JavaScript ES6

1
2js
3function expTree(s) {
4  var ops = [], nodes = [];
5  for (const c of s) {
6    if ('0' <= c && c <= '9') nodes.push(new Node(c));
7    else if (c == '(') ops.push(c);
8    else if (c == ')') while (ops[ops.length - 1] != '(') nodes.push(build());
9    else {
10      while (ops.length && opsStillGoes()) nodes.push(build());
11      ops.push(c);
12    }
13  }
14  while (ops.length) nodes.push(build());
15  return nodes[0];
16
17  function opsStillGoes() {
18    var c = ops[ops.length - 1], c2 = ops[ops.length - 2];
19    if (c == '(' || c2 == '(' || (c == '+' || c == '-') && (c2 == '*' || c2 == '/')) return false;
20    return true;
21  }
22  function build() {
23    var c = ops.pop(), r = nodes.pop(), l = nodes.pop();
24    if (c == '(') return r;
25    return new Node(c, l, r);
26  }
27}

Here, the build function checks if there are nodes available for creation of subtree by popping ops and checking the operator. If '(', it means an expression within parenthesis has been calculated and placed in nodes, so avoid creating unnecessary Node and instead return the precalculated Node. If any other operator, it pops two latest Nodes from nodes to create a new Node with left - operator - right hierarchy and return this to be pushed back to nodes.

C#

1
2csharp
3public class Solution {
4    public Node ExpTree(string s) {
5        Stack < char > ops = new Stack < char > ();
6        Stack < Node > nodes = new Stack < Node > ();
7
8        foreach(char c in s.ToCharArray()) {
9            if (c >= '0' && c <= '9') nodes.Push(new Node(c.ToString()));
10            else if (c == '(') ops.Push(c);
11            else if (c != ')') {
12                while (ops.Count > 0 && ops.Peek() != '(' && Precedence(ops.Peek()) >= Precedence(c)) nodes.Push(BuildNode(ops.Pop(), nodes.Pop(), nodes.Pop()));
13                ops.Push(c);
14            } else {
15                while (ops.Peek() != '(') nodes.Push(BuildNode(ops.Pop(), nodes.Pop(), nodes.Pop()));
16                ops.Pop();
17            }
18        }
19
20        while (ops.Count > 0) nodes.Push(BuildNode(ops.Pop(), nodes.Pop(), nodes.Pop()));
21
22        return nodes.Peek();
23    }
24
25    public Node BuildNode(char op, Node right, Node left) {
26        return new Node(op.ToString(), left, right);
27    }
28
29    public int Precedence(char op) {
30        if (op == '+' || op == '-') return 1;
31        else if (op == '*' || op == '/') return 2;
32        else return 0;
33    }
34}

In this C# solution, we iterate through s with foreach loop and break down discriminative components: numbers, operators and parentheses. Operators are kept in ops stack and node characters are kept in nodes stack. We use the function Precedence to determine 'weight' of the operators so as to resolve which operator to evaluate first. After the major calculations inside the respective stacks, now we are left with rest of the nodes in the nodes stack. The rest of the all nodes are removed from the stack and with their corresponding operator from the ops stack, new nodes are created and pushed back to the nodes stack. In the end the final expression tree should be left in the nodes stack which is returned to complete the requirement of the problem.

Note

Please ensure a thorough understanding of infix expressions, reversed polish notation, and tree data structures is key to solving this problem.It should also be noted that the stack data structure plays a crucial role in constructing a binary tree from infix expressions. Stacks are simple yet powerful data structures that follow the LIFO (last-in-first-out) principle. This allows us to temporarily hold operators and operands in a sequence, and retrieve them as soon as their respective counterparts are available.

Let's take a look at an example in order to better understand how stacks are used in the solution.

Consider the infix expression: "(3+4)*2". Here's how the solution works:

• Following the algorithm, push ( onto ops stack.
• 3 is a digit, create a new node and push it onto nodes stack.
• + is an operator, push it onto ops stack.
• Then, 4 is a digit, create a new node and push it onto nodes stack.
• ) indicates matching open parenthesis '(', so pop two nodes and an operator from the stacks, build a new node, and push it onto nodes stack.
• * is an operator, push it onto ops stack.
• Finally, 2 is a digit, create a new node and push it onto nodes stack.

At the end of the expressions, ops stack is not empty, so pop two nodes from nodes stack, and one operator from ops stack, build a new node and push it back onto nodes stack. Now, nodes stack contains the root of binary expression tree.

In conclusion, handling infix expressions to construct a binary tree involves carefully working with stack data structures, dealing with the operator precedence and handling parenthesis in the expression. Each operation in the expression becomes a node in the binary tree, with the operand or sub-expressions as their child nodes, thus forming an entire binary tree structure that represents the original expression. With practice and comprehension of these basic data structures and algorithms, such problems can be dealt with effectively.

Remember, problem solving in computer science typically involves breaking down a complex problem into smaller, manageable problems, and then solving each of these smaller problems. So, keep practicing and happy coding!

Solution Implementation