อัลกอริทึมสร้าง Expression Tree ในโครงสร้างข้อมูล

Expression Trees

Expression Trees: Leaf Nodes = Operands (ค่าที่จะนำไปคำนวณ) Internal Nodes = Operators (ตัวดำเนินการ)

ตัวอย่าง

4 + ((7 + 9) * 2) มี Expression Tree ดังนี้:

อัลกอริทึมสร้าง Expression Tree

If T is not NULL:
    If T→data is an operand:
        return T.data
    A = solve(T.left)
    B = solve(T.right)
    --> Calculate operator for 'T.data' on A and B, recursively
    return calculate(A, B, T.data)

วิธีสร้าง Expression Tree (ใช้ Stack)

1. Iterate Postfix Expression: ถ้าเป็น Operand → Push Stack (กลายเป็น Root)
2. ถ้าเป็น Operator มี 2 ค่า → เพิ่มเป็น Child ใน Tree Push Node ปัจจุบัน
3. ทำซ้ำจนจบ Expression
4. ตรวจสอบ: Root ต้องเป็น Operands, Child ต้องเป็น Values