# 1628. Design an Expression Tree With Evaluate Function
###### tags: `Leetcode` `Medium` `Design` `Tree`
Link: https://leetcode.com/problems/design-an-expression-tree-with-evaluate-function/description/
## Code

/**
 * 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();
    Node left;
    Node right;
    int val;
    String op = "";
};

class TreeNode extends Node {
    TreeNode(int val){
        this.val = val;
    }
    TreeNode(String op){
        this.op = op;
    }
    public int evaluate(){
        if(this.op.isEmpty()) return this.val;
        if(this.op.equals("+")) return left.evaluate()+right.evaluate();
        if(this.op.equals("-")) return left.evaluate()-right.evaluate();
        if(this.op.equals("*")) return left.evaluate()*right.evaluate();
        else return left.evaluate()/right.evaluate();
    }
}

/**
 * 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 {
    Node buildTree(String[] postfix) {
        Stack<TreeNode> stack = new Stack<>();
        for(String s:postfix){
            if(isOperator(s)){
                TreeNode right = stack.pop();
                TreeNode left = stack.pop();
                TreeNode op = new TreeNode(s);
                op.left = left;
                op.right = right;
                stack.push(op);
            }
            else stack.push(new TreeNode(Integer.parseInt(s)));
        }
        return stack.pop();
    }
    boolean isOperator(String s){
        return s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/");
    }
};


/**
 * Your TreeBuilder object will be instantiated and called as such:
 * TreeBuilder obj = new TreeBuilder();
 * Node expTree = obj.buildTree(postfix);
 * int ans = expTree.evaluate();
 */