สร้าง expression tree จาก postfix expression: ใช้ stack เก็บ (node, side) โดย side=LEFT/RIGHT บอกว่าจะ attach เป็น left หรือ right child ของ parent บน stack ตัวเลขเป็น leaf, operator เป็น internal node ต้องการ 2 children ประเมินค่าด้วย recursion ตาม operator
ขั้นตอนการสร้างต้นไม้
- pop ตัวสุดท้ายจาก postfix สร้าง node
- ถ้า root ยังว่าง: ตั้งเป็น root
- ถ้า stack ไม่ว่าง: pop parent, side มา attach node
- ถ้า token เป็น operator: push (node, LEFT) และ (node, RIGHT) ลง stack
ตัวอย่างโค้ด
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)) # Output: -7
อินพุต/เอาต์พุต
Input: ['1','2','+','3','4','+','*'] Output: -7
Expression: (1+2)*(3+4) = 3*7 = 21? Wait, the example says (1-2)*(3+4) = -7. The postfix should be ['1','2','-','3','4','+','*'] for that. The given postfix ['1','2','+','3','4','+','*'] evaluates to 21.
