Thuật toán xây dựng Cây biểu thức (Expression Tree) trong cấu trúc dữ liệu

Expression Trees (Cây biểu thức)

Cây biểu thức: nút lá chứa toán hạng, nút nội chứa toán tử áp dụng cho lá.

Ví dụ

4 + ((7 + 9) * 2) có expression tree:

Thuật toán xây dựng Expression Tree

Gọi T là 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, and call recursively,
        return calculate(A, B, T.data)

Cách xây dựng Expression Tree

Thường dùng Stack. Duyệt biểu thức hậu tố (postfix):

• Nếu gặp toán hạng: push vào stack. Trở thành gốc cây con.
• Nếu gặp toán tử: pop 2 giá trị từ stack, làm con trái/phải của nút toán tử, push nút mới vào stack.
• Lặp cho đến hết biểu thức.
• Kiểm tra: gốc chứa toán hạng, nút con chứa giá trị.