Chương trình Python xây dựng Expression Tree từ biểu thức cho trước

Expression Tree: node lá là toán hạng, node nội bộ là toán tử. Ví dụ 4 + ((7 + 9) * 2) có cây biểu thức như hình.

Cách giải

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

• Gặp operand -> push stack, thành root.
• Gặp operator -> pop 2 node, tạo node cha, push lại.
• Lặp đến hết biểu thức.

Ví dụ

class Stack:
    def __init__(self):
        self.arr = []
    def push(self, data):
        self.arr.append(data)
    def pop(self):
        try:
            return self.arr.pop(-1)
        except:
            pass
    def top(self):
        try:
            return self.arr[-1]
        except:
            pass
    def size(self):
        return len(self.arr)

# Node expression tree
class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Expression tree class
class ExpTree:
    def __init__(self, postfix_exp):
        self.exp = postfix_exp
        self.root = None
        self.createTree(self.exp)
    
    def isOperator(self, char):
        return char in ["+", "-", "*", "/", "^"]
    
    def createTree(self, exp):
        s = Stack()
        self.root = Node(exp[-1])  # Ký tự cuối postfix luôn là operator
        s.push(self.root)
        for i in "".join(reversed(exp[:-1])):
            curr_node = s.top()
            if not curr_node.right:
                temp = Node(i)
                curr_node.right = temp
                if self.isOperator(i):
                    s.push(temp)
            else:
                temp = Node(i)
                curr_node.left = temp
                s.pop()
                if self.isOperator(i):
                    s.push(temp)
    
    def inorder(self, head):
        if head.left:
            self.inorder(head.left)
        print(head.data, end=" ")
        if head.right:
            self.inorder(head.right)
    
    def infixExp(self):
        self.inorder(self.root)
        print()

if __name__ == "__main__":
    postfixExp = "ab+ef*g*-"
    et = ExpTree(postfixExp)
    et.infixExp()

Kết quả

(a + b - e * f * g)

Giải thích: Xây cây từ biểu thức hậu tố, duyệt inorder ra biểu thức trung tố.