1628. Design an Expression Tree With Evaluate Function

T : buildTree: O(n),

S: O(n)

/**
 * This is the interface for the expression tree Node.
 * You should not remove it, and you can define some classes to implement it.
 */

abstract class Node {
    public abstract int evaluate();
    // define your fields here
};

class NumberNode extends Node {
    int value;
    NumberNode(int value) {
        this.value = value;
    }
    
    @Override
    public int evaluate() {
        return value;
    }
}

class OperatorNode extends Node {
    Node left;
    Node right;
    BiFunction<Integer, Integer, Integer> operators;
    
    OperatorNode(Node left, Node right, BiFunction<Integer, Integer, Integer> operators) {
        this.left = left;
        this.right = right;
        this.operators = operators;
    }
    
    @Override
    public int evaluate() {
        return operators.apply(left.evaluate(), right.evaluate());
    }
    // if left or right node is OperatorNode -> so when call evaluate(), 
    // it will apply(left, right) agian, so this has the same effect as DFS
    
}

/**
 * This is the TreeBuilder class.
 * You can treat it as the driver code that takes the postinfix input 
 * and returns the expression tree represnting it as a Node.
 */

class TreeBuilder {
    Deque<Node> stack = new ArrayDeque<>();
    
    Node buildTree(String[] postfix) {
        
        // design a map, with BiFunction operation
        // this design able to support additional operators without making changes to your existing evaluate implementation
        Map<String, BiFunction<Integer, Integer, Integer>> operators = Map.of(
            "+", (a,b) -> (a+b),
            "-", (a,b) -> (a-b),
            "*", (a,b) -> (a*b),
            "/", (a,b) -> (a/b)
        );
        
        for (String val : postfix) {
            if (operators.containsKey(val)) {
                Node right = stack.pop();
                Node left = stack.pop();
                stack.push(new OperatorNode(left, right, operators.get(val)));
            } else {
                stack.push(new NumberNode(Integer.parseInt(val)));
            }
        }
        return stack.pop();
    }
};


/**
 * Your TreeBuilder object will be instantiated and called as such:
 * TreeBuilder obj = new TreeBuilder();
 * Node expTree = obj.buildTree(postfix);
 * int ans = expTree.evaluate();
 
 + -> build tree 
 4
 3
 
 +
 /\
 3 4
 */