Design an Expression Tree With Evaluate Function
Problem
Given the postfix tokens of an arithmetic expression (operands and the operators + - * /), build a binary expression tree and expose an evaluate() method that returns the numeric result.
In an expression tree every leaf is a number and every internal node is an operator whose two children are its operands. Evaluating means recursively computing each child and combining them with the node's operator.
postfix = ["3", "4", "+", "2", "*"]14class Node:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def evaluate(self):
if self.left is None and self.right is None:
return int(self.val)
a = self.left.evaluate()
b = self.right.evaluate()
if self.val == '+': return a + b
if self.val == '-': return a - b
if self.val == '*': return a * b
return int(a / b)
def build_tree(postfix):
stack = []
for tok in postfix:
if tok in '+-*/':
right = stack.pop()
left = stack.pop()
stack.append(Node(tok, left, right))
else:
stack.append(Node(tok))
return stack.pop()class Node {
constructor(val, left = null, right = null) {
this.val = val; this.left = left; this.right = right;
}
evaluate() {
if (!this.left && !this.right) return parseInt(this.val, 10);
const a = this.left.evaluate();
const b = this.right.evaluate();
if (this.val === '+') return a + b;
if (this.val === '-') return a - b;
if (this.val === '*') return a * b;
return Math.trunc(a / b);
}
}
function buildTree(postfix) {
const stack = [];
for (const tok of postfix) {
if ('+-*/'.includes(tok)) {
const right = stack.pop();
const left = stack.pop();
stack.push(new Node(tok, left, right));
} else {
stack.push(new Node(tok));
}
}
return stack.pop();
}class Node {
String val; Node left, right;
Node(String val) { this.val = val; }
Node(String val, Node l, Node r) { this.val = val; left = l; right = r; }
int evaluate() {
if (left == null && right == null) return Integer.parseInt(val);
int a = left.evaluate(), b = right.evaluate();
switch (val) {
case "+": return a + b;
case "-": return a - b;
case "*": return a * b;
default: return a / b;
}
}
}
class Builder {
Node buildTree(String[] postfix) {
Deque<Node> stack = new ArrayDeque<>();
for (String tok : postfix) {
if (tok.length() == 1 && "+-*/".contains(tok)) {
Node r = stack.pop(), l = stack.pop();
stack.push(new Node(tok, l, r));
} else stack.push(new Node(tok));
}
return stack.pop();
}
}struct Node {
string val; Node *left = nullptr, *right = nullptr;
Node(string v) : val(v) {}
Node(string v, Node* l, Node* r) : val(v), left(l), right(r) {}
int evaluate() {
if (!left && !right) return stoi(val);
int a = left->evaluate(), b = right->evaluate();
if (val == "+") return a + b;
if (val == "-") return a - b;
if (val == "*") return a * b;
return a / b;
}
};
Node* buildTree(vector<string>& postfix) {
stack<Node*> st;
for (auto& tok : postfix) {
if (tok.size() == 1 && string("+-*/").find(tok) != string::npos) {
Node* r = st.top(); st.pop();
Node* l = st.top(); st.pop();
st.push(new Node(tok, l, r));
} else st.push(new Node(tok));
}
return st.top();
}Explanation
Postfix (reverse Polish) notation is built for a stack. We scan tokens left to right. A number becomes a leaf node that we push onto the stack of partial subtrees.
When we hit an operator, the two most recent subtrees on the stack are its operands. We pop the right operand first (it was pushed last), then the left, make the operator their parent, and push that new subtree back. When the scan ends, the single remaining node is the whole expression tree's root.
evaluate() is a textbook post-order recursion. A leaf returns its number directly. An operator node evaluates its left and right children, then applies its operator to those two results.
Because evaluation happens bottom-up, every operand is a fully computed value by the time its parent needs it, so a single recursive pass produces the answer.
Example on ["3","4","+","2","*"]: push 3, push 4, hit '+' → pop 4 and 3, push (+ 3 4); push 2; hit '*' → pop 2 and (+), push (* (+ 3 4) 2). Evaluate: 3 + 4 = 7, then 7 * 2 = 14.