Cho thứ tự hậu tố (post-order) của cây biểu thức. Xây dựng cây và tính giá trị biểu thức. Trả về root và giá trị.
Ví dụ: ['1','2','+','3','4','+','*'] → (1-2)*(3+4) = -7
Thuật toán
- Hàm evaluate(root):
- Nếu node là số: return int(val)
- left = evaluate(left), right = evaluate(right)
- Áp dụng phép toán +, -, *, / (chia nguyên)
- Hàm buildTree(postfix):
- Dùng stack lưu (node, side) với LEFT=0, RIGHT=1
- Pop postfix, tạo node. Nếu stack không rỗng: gán làm con trái/phải của parent
- Nếu token không phải số: push (node, LEFT) và (node, RIGHT) vào stack
Code Python
LEFT, RIGHT = 0, 1
class Node:
def __init__(self, val, left=None, right=None):
self.val = val
self.left = left
self.right = right
def evaluate(root):
if root.val.isnumeric():
return int(root.val)
left_val = evaluate(root.left)
right_val = evaluate(root.right)
if root.val == '+': return left_val + right_val
if root.val == '-': return left_val - right_val
if root.val == '*': return left_val * right_val
if root.val == '/': return left_val // right_val
def buildTree(postfix):
root = None
stack = []
while postfix:
curr = postfix.pop()
curr_node = Node(curr)
if not root:
root = curr_node
if stack:
parent, side = stack.pop()
if side == LEFT:
parent.left = curr_node
else:
parent.right = curr_node
if not curr.isnumeric():
stack.append((curr_node, LEFT))
stack.append((curr_node, RIGHT))
return root
root = buildTree(['1','2','+','3','4','+','*'])
print(evaluate(root))
Input
['1','2','+','3','4','+','*']
Output
-7