โปรแกรม Python สร้าง Expression Tree จาก Expression ที่กำหนด

Expression Trees คือต้นไม้ที่ Leaf Nodes มีค่าที่จะนำไปคำนวณ และ Internal Nodes มี Operator ที่จะนำไปดำเนินการกับ Leaf Node

ตัวอย่าง: 4 + ((7 + 9) * 2) จะมี Expression Tree แบบนี้:

แนวทางแก้ปัญหา

เพื่อสร้าง Expression Tree สำหรับ Expression ที่กำหนด เรามักใช้ Stack Data Structure เริ่มต้นเรา Iterate ผ่าน Postfix Expression ที่กำหนดและทำตามขั้นตอน:

• หากได้ Operand ใน Expression ให้ Push เข้า Stack จะกลายเป็น Root ของ Expression Tree
• หาก Operator ได้ค่า 2 ค่าใน Expression ให้เพิ่มใน Expression Tree เป็น Child และ Push เข้า Current Node
• ทำซ้ำ Step-1 และ Step-2 จนครบ Expression ที่กำหนด

ตัวอย่าง

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 class for expression tree
class node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

# Expression tree class
class exp_tree:
    def __init__(self, postfix_exp):
        self.exp = postfix_exp
        self.root = None
        self.createTree(self.exp)
    
    def isOperator(self, char):
        optr = ["+", "-", "*", "/", "^"]
        if char in optr:
            return True
        return False
    
    def createTree(self, exp):
        s = stack()
        # Store operator nodes whose any child is NULL
        self.root = node(exp[-1])
        # Last character of postfix expression is always an operator
        s.push(self.root)
        # Travel on rest of the postfix expression
        for i in "".join(reversed(exp[:-1])):
            curr_node = s.top()
            if not curr_node.right:
                # If right node of current node is NULL
                temp = node(i)
                curr_node.right = temp
                if self.isOperator(i):
                    s.push(temp)
            else: # If left node of current node is NULL
                temp = node(i)
                curr_node.left = temp
                # If no child node of current node is NULL
                s.pop() # Pop current from stack
                if self.isOperator(i):
                    s.push(temp)
    
    def inorder(self, head):
        # Inorder traversal of expression tree
        # Inorder traversal => left, root, right
        if head.left:
            self.inorder(head.left)
        print(head.data, end=" ")
        if head.right:
            self.inorder(head.right)
    
    def infixExp(self):
        # Inorder traversal of expression tree gives infix expression
        self.inorder(self.root)
        print()

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

การรันโค้ดข้างต้นจะได้ผลลัพธ์:

ผลลัพธ์

(a + b - e * f * g)

คำอธิบาย:

การสร้าง Tree จาก Expression ที่กำหนดจะสร้าง Output ที่ Operand จะกลายเป็น Root ของ Node และตัวเลขที่เหลือจะกลายเป็น Child Nodes ของ Expression Tree