(subtraction), '*' (multiplication), and '/' (division).

It's guaranteed that no subtree will yield a value that exceeds 109 in absolute value, and all the operations are valid (i.e., no division by zero).

Follow up: Could you design the expression tree such that it is more modular? For example, is your design able to support additional operators without making changes to your existing evaluate implementation?

Examples

Example 1:

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1600-1699/1628.Design%20an%20Expression%20Tree%20With%20Evaluate%20Function/images/untitled- diagram.png)

Input: s = ["3","4","+","2","*","7","/"]
Output: 2
Explanation: this expression evaluates to the above binary tree with expression ((3+4)*2)/7) = 14/7 = 2.

Example 2:

![](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/1600-1699/1628.Design%20an%20Expression%20Tree%20With%20Evaluate%20Function/images/untitled- diagram2.png)

Input: s = ["4","5","2","7","+","-","*"]
Output: -16
Explanation: this expression evaluates to the above binary tree with expression 4*(5-(2+7)) = 4*(-4) = -16.

Constraints:

1 <= s.length < 100
s.length is odd.
s consists of numbers and the characters '+', '-', '*', and '/'.
If s[i] is a number, its integer representation is no more than 105.
It is guaranteed that s is a valid expression.
The absolute value of the result and intermediate values will not exceed 109.
It is guaranteed that no expression will include division by zero.

Solution

Method 1 – Stack-Based Tree Construction and Polymorphic Evaluation

Intuition

We can build the expression tree from the postfix tokens using a stack. For each token, if it's a number, create a leaf node and push it onto the stack. If it's an operator, pop two nodes from the stack, create an operator node with them as children, and push it back. For evaluation, use polymorphism: each node type implements its own evaluate method. This design is modular and easily extensible for new operators.

Approach

Define a base Node class with an evaluate method.
Implement NumNode for numbers and OpNode for operators, both inheriting from Node.
For each token in the postfix list:
- If it's a number, create a NumNode and push to the stack.
- If it's an operator, pop two nodes, create an OpNode, and push to the stack.
The last node on the stack is the root of the expression tree.
To evaluate, call evaluate() on the root node.

Code

[{"language":"Python","code":"class Node:\n    def evaluate(self) -> int:\n        raise NotImplementedError\nclass NumNode(Node):\n    def __init__(self, val: int):\n        self.val = val\n    def evaluate(self) -> int:\n        return self.val\nclass OpNode(Node):\n    def __init__(self, op: str, left: Node, right: Node):\n        self.op = op\n        self.left = left\n        self.right = right\n    def evaluate(self) -> int:\n        l, r = self.left.evaluate(), self.right.evaluate()\n        if self.op == '+': return l + r\n        if se

Related Tags