Question

Formatted question description: https://leetcode.ca/all/1597.html

 1597. Build Binary Expression Tree From Infix Expression

 A binary expression tree is a kind of binary tree used to represent arithmetic expressions.
 Each node of a binary expression tree has either zero or two children.

 Leaf nodes (nodes with 0 children) correspond to operands (numbers),
 and internal nodes (nodes with 2 children) correspond to the operators
 '+' (addition), '-' (subtraction), '*' (multiplication), and '/' (division).

 For each internal node with operator o, the infix expression that it represents is (A o B),
 where A is the expression the left subtree represents and B is the expression the right subtree represents.

 You are given a string s, an infix expression containing operands, the operators described above, and parentheses '(' and ')'.

 Return the binary expression tree, which its in-order traversal reproduce s.

 Please note that order of operations applies in s. That is, expressions in parentheses are evaluated first,
 and multiplication and division happen before addition and subtraction.


 Example 1:

 Input: s = "2-3/(5*2)+1"
 Output: [+,-,1,2,/,null,null,null,null,3,*,null,null,5,2]


 Example 2:

 Input: s = "3*4-2*5"
 Output: [-,*,*,3,4,2,5]


 Example 3:

 Input: s = "1+2+3+4+5"
 Output: [+,+,5,+,4,null,null,+,3,null,null,1,2]


 Constraints:
     1 <= s.length <= 105
     s consists of digits and the characters '+', '-', '*', '/', '(', and ')'.
     Operands in s are exactly 1 digit.
     It is guaranteed that s is a valid expression.

Algorithm

First, specify the priority of each operator. Here, the left parenthesis is also regarded as an operator. Its priority is 1, the priority of addition and subtraction is 2, and the priority of multiplication and division is 3. Maintain a symbol stack so that the operator priority from the bottom of the stack to the top of the stack is strictly increased, and then open a Node stack to store the Node. Then start traversing s:

  1. Encounter a left parenthesis, enter the symbol stack;
  2. When a number is encountered, the new exit node enters the Node stack;
  3. When a right parenthesis is encountered, as long as the top of the symbol stack is not a left parenthesis, pop two Nodes from the Node stack as the right and left children respectively (note that here is the right and left children, not the left and right children, the first pop is the right child, and then pop is the left child), pop an operator from the symbol stack as the root of the tree, connect the left and right children, then push back to the Node stack; finally, pop the left parenthesis out of the stack;
  4. When an operator is encountered, as long as the priority of the operator at the top of the symbol stack is greater than or equal to the new algorithm, pop two Nodes from the Node stack as the right and left children respectively, and pop an operator from the symbol stack As the root of the tree, after connecting the left and right children, push back to the Node stack.

Finally, if it is found that the size of the Node stack is not 1, the above pop operation is performed twice to connect the tree root until the size of the Node stack is 1.

The last Node left in the stack is what you want.

Code

Java

public class Build_Binary_Expression_Tree_From_Infix_Expression {

    public class Solution {

        Map<Character, Integer> prio = new HashMap<>();

        public Node expTree(String s) {

            prio.put('(', 1);
            prio.put('+', 2);
            prio.put('-', 2);
            prio.put('*', 3);
            prio.put('/', 3);

            Deque<Character> ops = new ArrayDeque<>();
            Deque<Node> stack = new ArrayDeque<>();

            for (int i = 0; i < s.length(); i++) {
                char ch = s.charAt(i);
                if (ch == '(') {
                    ops.push(ch);
                } else if (Character.isDigit(ch)) {
                    stack.push(new Node(ch));
                } else if (ch == ')') {
                    while (ops.peek() != '(') {
                        combine(ops, stack);
                    }
                    // pop left '('
                    ops.pop();
                } else {
                    while (!ops.isEmpty() && prio.get(ops.peek()) >= prio.get(ch)) { // @note: must be >=, for test case "1+2+3+4+5"
                        combine(ops, stack);
                    }

                    ops.push(ch);
                }
            }

            while (stack.size() > 1) {
                combine(ops, stack);
            }

            return stack.peek();
        }

        private void combine(Deque<Character> ops, Deque<Node> stack) {
            Node root = new Node(ops.pop());
            // right first, then left
            root.right = stack.pop();
            root.left = stack.pop();

            stack.push(root);
        }
    }

    class Node {
        char val;
        Node left, right;

        public Node(char val) {
            this.val = val;
        }
    }
}

All Problems

All Solutions