อัลกอริทึมในการสร้างแผนผังนิพจน์ในโครงสร้างข้อมูล

ต้นไม้นิพจน์

ต้นไม้นิพจน์คือสิ่งที่โหนดปลายสุดมีค่าที่จะดำเนินการ และโหนดภายในประกอบด้วยตัวดำเนินการที่โหนดปลายสุดจะถูกดำเนินการ

ตัวอย่าง

4 + ((7 + 9) * 2) จะมีต้นไม้นิพจน์ดังนี้

อัลกอริทึมในการสร้างแผนผังนิพจน์

ให้ T เป็นต้นไม้นิพจน์

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)

จะสร้างนิพจน์ทรีได้อย่างไร

ในการสร้าง Expression Tree สำหรับนิพจน์ที่กำหนด โดยทั่วไปเราใช้ Stack Data Structure

เริ่มแรก เราวนซ้ำนิพจน์ postfix ที่กำหนด และทำตามขั้นตอนที่ระบุด้านล่าง -

• หากเราได้ตัวถูกดำเนินการในนิพจน์ที่กำหนด ให้พุชมันในสแต็ก มันจะกลายเป็นรากของนิพจน์ Tree.
• หากโอเปอเรเตอร์ได้รับค่าสองค่าในนิพจน์ ให้เพิ่มในแผนผังนิพจน์เป็นรายการย่อย และพุชลงในโหนดปัจจุบัน
• ทำซ้ำขั้นตอนที่ 1 และขั้นตอนที่ 2 จนกว่าเราจะดำเนินการตามนิพจน์ที่กำหนด
• ตอนนี้ ให้ตรวจสอบว่าทุกโหนดรูทไม่มีอะไรเลยนอกจากตัวถูกดำเนินการ และโหนดย่อยทุกโหนดมีค่าเท่านั้น