ต้นไม้นิพจน์คือสิ่งที่โหนดปลายสุดมีค่าที่จะดำเนินการ และโหนดภายในประกอบด้วยตัวดำเนินการที่โหนดปลายสุดจะถูกดำเนินการ
ตัวอย่าง:4 + ((7 + 9) * 2) จะมีต้นไม้นิพจน์เช่น -
แนวทางการแก้ปัญหานี้
ในการสร้าง Expression Tree สำหรับนิพจน์ที่กำหนด โดยทั่วไปเราใช้ Stack Data Structure เริ่มแรก เราวนซ้ำนิพจน์ postfix ที่กำหนด และทำตามขั้นตอนที่ระบุด้านล่าง -
- หากเราได้ตัวถูกดำเนินการในนิพจน์ที่กำหนด ให้พุชมันในสแต็ก มันจะกลายเป็นรากของนิพจน์ Tree.
- หากโอเปอเรเตอร์ได้รับค่าสองค่าในนิพจน์ ให้เพิ่มในแผนผังนิพจน์เป็นรายการย่อย และพุชลงในโหนดปัจจุบัน
- ทำซ้ำขั้นตอนที่ 1 และขั้นตอนที่ 2 จนกว่าเราจะใช้นิพจน์ที่ระบุไม่ครบ
ตัวอย่าง
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: # if given char is operator return True # then return true return False # else return false def createTree(self, exp): s = stack() # store those operator node whose any child node 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 give 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)
คำอธิบาย:
การสร้างทรีจากนิพจน์ที่กำหนดจะสร้างเอาต์พุตโดยที่ตัวถูกดำเนินการจะกลายเป็นรูทของโหนด และตัวเลขที่เหลือจะกลายเป็นโหนดย่อยของทรีนิพจน์
