Code Implementation

from abc import ABC, abstractmethod
from typing import List

class Node(ABC):
    @abstractmethod
    def evaluate(self) -> int:
        pass

class TreeNode(Node):
    def __init__(self, val: str, left: 'TreeNode' = None, right: 'TreeNode' = None):
        self.val = val
        self.left = left
        self.right = right

    def evaluate(self) -> int:
        if self.val.isdigit() or (self.val[0] == '-' and self.val[1:].isdigit()):
            return int(self.val)
        left_val = self.left.evaluate()
        right_val = self.right.evaluate()
        if self.val == '+':
            return left_val + right_val
        elif self.val == '-':
            return left_val - right_val
        elif self.val == '*':
            return left_val * right_val
        elif self.val == '/':
            return left_val // right_val

class TreeBuilder(object):
    def buildTree(self, postfix: List[str]) -> 'Node':
        stack = []
        for token in postfix:
            if token in '+-*/':
                right = stack.pop()
                left = stack.pop()
                node = TreeNode(token, left, right)
                stack.append(node)
            else:
                stack.append(TreeNode(token))
        return stack[-1]
      

#include <string>
#include <vector>
#include <stack>
using namespace std;

class Node {
public:
    virtual int evaluate() const = 0;
    virtual ~Node() {}
};

class TreeNode : public Node {
public:
    string val;
    Node* left;
    Node* right;
    TreeNode(string v, Node* l = nullptr, Node* r = nullptr) : val(v), left(l), right(r) {}
    int evaluate() const override {
        if (isdigit(val[0]) || (val[0] == '-' && val.size() > 1)) {
            return stoi(val);
        }
        int lval = left->evaluate();
        int rval = right->evaluate();
        if (val == "+") return lval + rval;
        if (val == "-") return lval - rval;
        if (val == "*") return lval * rval;
        if (val == "/") return lval / rval;
        return 0;
    }
    ~TreeNode() {
        delete left;
        delete right;
    }
};

class TreeBuilder {
public:
    Node* buildTree(vector<string>& postfix) {
        stack<Node*> st;
        for (auto& token : postfix) {
            if (token == "+" || token == "-" || token == "*" || token == "/") {
                Node* right = st.top(); st.pop();
                Node* left = st.top(); st.pop();
                st.push(new TreeNode(token, left, right));
            } else {
                st.push(new TreeNode(token));
            }
        }
        return st.top();
    }
};
      

import java.util.*;

abstract class Node {
    public abstract int evaluate();
}

class TreeNode extends Node {
    String val;
    Node left, right;
    TreeNode(String val) { this.val = val; }
    TreeNode(String val, Node left, Node right) {
        this.val = val; this.left = left; this.right = right;
    }
    public int evaluate() {
        if (Character.isDigit(val.charAt(0)) || (val.charAt(0) == '-' && val.length() > 1)) {
            return Integer.parseInt(val);
        }
        int lval = left.evaluate();
        int rval = right.evaluate();
        switch (val) {
            case "+": return lval + rval;
            case "-": return lval - rval;
            case "*": return lval * rval;
            case "/": return lval / rval;
        }
        return 0;
    }
}

class TreeBuilder {
    Node buildTree(String[] postfix) {
        Stack<Node> stack = new Stack<>();
        for (String token : postfix) {
            if (token.equals("+") || token.equals("-") || token.equals("*") || token.equals("/")) {
                Node right = stack.pop();
                Node left = stack.pop();
                stack.push(new TreeNode(token, left, right));
            } else {
                stack.push(new TreeNode(token));
            }
        }
        return stack.peek();
    }
}
      

class Node {
    evaluate() {}
}

class TreeNode extends Node {
    constructor(val, left = null, right = null) {
        super();
        this.val = val;
        this.left = left;
        this.right = right;
    }
    evaluate() {
        if (!isNaN(Number(this.val))) {
            return Number(this.val);
        }
        const lval = this.left.evaluate();
        const rval = this.right.evaluate();
        switch (this.val) {
            case '+': return lval + rval;
            case '-': return lval - rval;
            case '*': return lval * rval;
            case '/': return Math.trunc(lval / rval);
        }
    }
}

class TreeBuilder {
    buildTree(postfix) {
        const stack = [];
        for (const token of postfix) {
            if (['+', '-', '*', '/'].includes(token)) {
                const right = stack.pop();
                const left = stack.pop();
                stack.push(new TreeNode(token, left, right));
            } else {
                stack.push(new TreeNode(token));
            }
        }
        return stack[stack.length - 1];
    }
}
      

Problem Description

You are given a list of strings called postfix, representing a mathematical expression in Reverse Polish Notation (RPN). Your task is to design an expression tree that can represent this expression and provide an evaluate() function to compute its result.

• Each string in postfix is either an integer or one of the operators: +, -, *, or /.
• You must implement a class (e.g., TreeBuilder) with a method buildTree(postfix) that constructs the expression tree.
• Each node in the tree should have an evaluate() method that returns the result of the subtree rooted at that node.
• The division operator / should truncate toward zero.
• Assume the input is always valid and there is exactly one valid solution.

Thought Process

At first glance, the problem asks us to parse and evaluate an expression in postfix (Reverse Polish Notation) form. In postfix notation, operators come after their operands, which makes it easy to evaluate expressions using a stack.

The brute-force way would be to directly evaluate the RPN using a stack, but the challenge here is to build an expression tree that models the computation, and then evaluate it using the tree's evaluate() method.

The key insight is that each operator in the postfix expression corresponds to an internal node in the tree, and each operand corresponds to a leaf node. By processing the postfix tokens from left to right, we can build the tree bottom-up using a stack, just like evaluating RPN, but instead of pushing numbers, we push tree nodes.

This approach allows us to efficiently build the tree and evaluate it recursively, mirroring the natural structure of arithmetic expressions.

Solution Approach

• Step 1: Define the Node Structure
  • Create an abstract base class Node with an evaluate() method.
  • Implement a concrete class (e.g., TreeNode) that stores the value (val), and pointers to left and right children.
• Step 2: Build the Expression Tree Using a Stack
  • Initialize an empty stack.
  • Iterate over each token in the postfix array:
  • If the token is an operand (number), create a leaf node and push it onto the stack.
  • If the token is an operator, pop two nodes from the stack (right and left), create a new node with the operator as its value and the two nodes as children, then push this node back onto the stack.
  • After processing all tokens, the stack will contain a single node, which is the root of the expression tree.
• Step 3: Evaluate the Expression Tree
  • Implement the evaluate() method for each node.
  • If the node is a leaf (number), return its value.
  • If the node is an operator, recursively evaluate the left and right children, then apply the operator to their results.
  • Ensure division truncates toward zero.

This method ensures each sub-expression is evaluated exactly once, and the tree structure naturally mirrors the order of operations.

Example Walkthrough

Let's walk through the process with the input postfix = ["3", "4", "+", "2", "*", "7", "/"].

1. Read "3": it's a number, push node("3") onto the stack.
2. Read "4": it's a number, push node("4") onto the stack.
3. Read "+": pop "4" and "3", create node("+", left="3", right="4"), push onto the stack.
4. Read "2": it's a number, push node("2") onto the stack.
5. Read "*": pop "2" and "+", create node("*", left="+", right="2"), push onto the stack.
6. Read "7": it's a number, push node("7") onto the stack.
7. Read "/": pop "7" and "*", create node("/", left="*", right="7"), push onto the stack.
8. Now the stack contains one node: the root of the tree representing the whole expression.

Evaluating the tree recursively:

• "/" node evaluates its left ("*") and right ("7")
• "*" node evaluates its left ("+") and right ("2")
• "+" node evaluates "3" + "4" = 7
• "*" node: 7 * 2 = 14
• "/" node: 14 / 7 = 2

Time and Space Complexity

• Brute-force Approach:
  • Directly evaluating RPN using a stack is O(n) time and O(n) space, where n is the number of tokens.
• Optimized (Tree-based) Approach:
  • Building the tree: Each token is processed once, so O(n) time.
  • Each node is stored once, so O(n) space for the tree.
  • Evaluating the tree: Each node is visited once, so O(n) time.
• Total Complexity: Both time and space are O(n).

Summary

The problem is elegantly solved by leveraging the natural fit between postfix expressions and stack-based processing. By building an expression tree from the postfix input, we create a reusable and extensible structure that mirrors the computation. The recursive evaluation of the tree is both intuitive and efficient, with clear separation between parsing and computation. This approach ensures correctness, efficiency, and flexibility for more complex extensions in the future.