ต้นไม้นิพจน์ทวิภาค

ต้นไม้พิจน์ หรือ binary expression tree เป็นต้นไม้แบบไบนารี (Binary Tree) ที่มีการสร้างขึ้นจากตัวกระทำ(operand) และ เครื่องหมาย(operators) ทางคณิตศาสตร์ของนิพจน์ โดยการวางตัวกระทำที่ leaf node และวางเครื่องหมายไว้ที่ root node

การสร้าง Expression Tree

จะมีการนำ Postfix Expression มาใช้ในการทำ Expression tree

1. เริ่มจากการอ่านนิพจน์ทางคณิตศาสตร์ (Expression) ทีละตัว

2. ถ้าตัวที่ได้เป็น Operand (ตัวถูกดำเนินการ) ให้สร้างโหนดของ tree หนึ่งโหนดแล้ว push ข้อมูลลงบน Stack

3. หากตัวที่อ่านได้เป็น Operator (ตัวดำเนินการ) ให้ทำการ pop ข้อมูลออกจาก Stack 2 ครั้ง เนื่องจาก Operator ใช้เป็น Binary Operator (Operator 1 ตัว ต้องการ Operand 2 ตัว) ซึ่งจะได้ trees T₁ และ T₂ (T₁ นำออกก่อน) แล้วให้นำมาสร้างเป็น tree ใหม่ที่มีราก (root) เป็นตัว operator และมี left และ right children เป็น T₂ และ T₁ ตามลำดับ จากนั้นให้ใส่ tree ใหม่นี้กลับลง stack

ตัวอย่างของ Expression Tree

เป็นตัวอย่างต้นไม้นิพจน์ของ (a+(b*c)) + ((d+e)*f)

Code ของ Expression Tree

class ExpressionTree:
	def __init__(self , value):
		self.value = value
		self.left = None
		self.right = None

def isOperator(char):
	if (char == '+' or char == '-' or char == '*'
		or char == '/' or char == '^'):
		return True
	else:
		return False

def buildTree(postfix):
	stack = []

	for char in postfix :
		if not isOperator(char):
			t = ExpressionTree(char)
			stack.append(t)
		else:
			t = ExpressionTree(char)
			t1 = stack.pop()
			t2 = stack.pop()

			t.right = t1
			t.left = t2

			stack.append(t)
	t = stack.pop()
	return t
	

def inorder(t):
	alist = []
	if t is not None:
		alist.append(t.value)
		alist = inorder(t.left) + alist + inorder(t.right)
	return alist

แหล่งอ้างอิง

geeksforgeeks Expression Tree ค้นหาเมื่อ 30 มีนาคม 2561

nattee ต้นไม้นิพจน์ ค้นหาเมื่อ 30 มีนาคม 2561