ต้นไม้นิพจน์ (Expression Tree)

นึกภาพก่อน

นิพจน์ 5 + y * 4 ต้องคูณก่อนบวก ลำดับการคำนวณซ่อนอยู่ในกฎของเครื่องหมาย ถ้าวาดเป็นต้นไม้ ลำดับจะเห็นทันที: การคำนวณที่ต้องทำก่อนอยู่ลึกกว่า

text

ต้นไม้นิพจน์ แทนนิพจน์ด้วยต้นไม้:

ใบ คือตัวถูกดำเนินการ (operand): ตัวเลขหรือตัวแปร
ปมภายใน คือตัวดำเนินการ (operator): +, -, *, /, ^

เมื่อนิพจน์อยู่ในรูปต้นไม้ การประมวลผลทำได้ง่ายและเร็ว: คำนวณลูกซ้าย คำนวณลูกขวา แล้วนำมาดำเนินการที่ปม

สามรูปแบบของนิพจน์

การแวะผ่านต้นไม้นิพจน์แต่ละแบบให้นิพจน์คนละรูป:

การแวะผ่าน	รูปแบบนิพจน์	ตัวดำเนินการอยู่
Preorder (ก่อนลำดับ)	prefix	หน้าตัวถูกดำเนินการ
Inorder (ตามลำดับ)	infix	ระหว่างตัวถูกดำเนินการ
Postorder (หลังลำดับ)	postfix	หลังตัวถูกดำเนินการ

ตัวอย่างจากสไลด์ นิพจน์ 3 * x ^ 2 + 4:

text

รูปแบบ	ผลลัพธ์
Prefix	`+ * 3 ^ x 2 4`
Infix	`3 * x ^ 2 + 4`
Postfix	`3 x 2 ^ * 4 +`

Postfix และ prefix ไม่ต้องใช้วงเล็บเลย ลำดับการคำนวณถูกกำหนดด้วยตำแหน่ง

คำนวณค่าจากต้นไม้

ตัวอย่างในสไลด์: (3*2)+(7-(3*1))

text

          +
        /   \
       *     -
      / \   / \
     3   2 7   *
              / \
             3   1

คำนวณจากล่างขึ้นบน: 3*2 = 6, 3*1 = 3, 7-3 = 4, 6+4 = 10

ลองแวะผ่านต้นไม้นี้ทั้งสามแบบได้ใน simulation ของบทเรียน Binary Tree (ตัวอย่าง "นิพจน์")

สร้างต้นไม้นิพจน์จาก postfix

ใช้ stack เก็บ ปม (ต้นไม้ย่อย) ที่ยังรอประกอบ อ่าน postfix จากซ้ายไปขวา:

พบ operand → สร้างปมใบ แล้ว push ลงกองซ้อน
พบ operator → pop สองครั้งออกมาเป็นลูกของปมใหม่ แล้ว push ปมใหม่ลงกองซ้อน
อ่านหมดแล้ว ปมเดียวที่เหลือในกองซ้อนคือรากของต้นไม้

ลำดับของลูก: ตัวที่ pop ออกมา ก่อน เป็น ลูกขวา ตัวที่ pop ทีหลังเป็นลูกซ้าย (เพราะ operand ตัวขวาถูก push ทีหลังจึงอยู่บนสุด)

ตัวอย่างไล่ทีละขั้น

จากสไลด์: infix 5 + y * 4 มี postfix เป็น 5 y 4 * +

อ่าน	ทำอะไร	กองซ้อน (ล่าง → บน)
`5`	push ปม 5	`5`
`y`	push ปม y	`5`, `y`
`4`	push ปม 4	`5`, `y`, `4`
`*`	pop ได้ 4 (ลูกขวา) และ y (ลูกซ้าย) สร้างปม `*` แล้ว push	`5`, `(y * 4)`
`+`	pop ได้ `(y * 4)` (ลูกขวา) และ 5 (ลูกซ้าย) สร้างปม `+` แล้ว push	`(5 + (y * 4))`

เหลือปมเดียวคือราก + ได้ต้นไม้เดียวกับรูปแรกของบทนี้ และ Inorder ของมันคือ 5 + y * 4

จุดที่มักพลาด

1. สลับลูกซ้ายกับลูกขวาตอน pop

ตัวที่ pop ก่อนคือลูก ขวา สำหรับ + และ * ผลเท่ากัน แต่สำหรับ -, / และ ^ ผลผิดทันที (7 3 - ต้องเป็น 7 − 3 ไม่ใช่ 3 − 7)

2. push operator ลงกองซ้อนก่อนประกอบ

operator ไม่ถูก push เดี่ยว ๆ ต้อง pop สองตัวมาประกอบเป็นปมก่อนแล้วจึง push ปมที่ประกอบแล้ว

3. คิดว่าใบเป็น operator

ใบเป็น operand เสมอ operator ต้องมีลูกสองตัว

4. จับคู่การแวะผ่านกับรูปแบบผิด

Pre → prefix, In → infix, Post → postfix (ชื่อตรงกัน)

5. คิดว่า infix จากการแวะผ่านใส่วงเล็บให้

Inorder แบบธรรมดาไม่ใส่วงเล็บ ต้นไม้ของ (5 + y) * 4 กับ 5 + y * 4 ต่างกัน แต่ Inorder ออกมาเป็น 5 + y * 4 เหมือนกัน โครงสร้างของต้นไม้ต่างหากที่เก็บลำดับการคำนวณ

ที่มา: BinaryTREE_8.pdf หน้า 8–13 และ 28–35