การแปลงนิพจน์ infix เป็น postfix
ต้องรู้ลำดับการทำงานของตัวดำเนินการก่อน
ลำดับการทำงานของตัวดำเนินการทางคณิตศาสตร์จากสูงไปต่ำ
1. เครื่องหมายวงเล็บ (ไม่ใช่ตัวดำเนินการ)
2. ตัวดำเนินการยกกำลัง (^)
3. ตัวดำเนินการคูณ (*) และหาร (/)
4. ตัวดำเนินการบวก (+) และลบ (-)
โดยตัวดำเนินการที่มีลำดับเดียวกันให้ทำงานจากซ้ายไปขวา
ยกเว้นตัวดำเนินการยกกำลังให้ทำงานจากขวามาซ้าย
ตัวอย่าง
A+B+C หมายถึง (A+B)+C
A^B^C หมายถึง A^(B^C)
******************************
การแปลงนิพจน์ infix เป็น postfix
จะใช้ stack ในการเก็บตัวดำเนินการ
ลำดับการแปลง infix เป็น postfix
1 ถ้าข้อมุลเป็นตัวถูกดำเนินการ (operand) ให้นำไปเป็นผลลัพธ์
2 ถ้าข้อมูลเข้าเป็นตัวดำเนินการ (operator) ให้ปฎิบัติดังนี้
2.1 ถ้าstack ยังว่างให้ทำการ push
ตัวดำเนินการเก็บลงstack
2.2 ถ้าstack ไม่ว่างให้ทำการเปรียบเทียบตัวดำเนินการ
ที่นำเข้ามากับตัวดำเนินการที่ตำแหน่ง Top ของ stack
2.2.1 ถ้าตัวดำเนินการที่นำเข้ามีลำดับความสำคัญมากกว่า
ตัวดำเนินการที่ตำแหน่ง top ของ stack ให้ทำการ
push ตัวเนินการนั้นเก็บลงใน stack
2.2.2 ถ้าตัวดำเนินการที่นำเข้ามา มีลำดับความสำคัญน้อยกว่า
หรือเท่ากับตัวดำเนินการที่ตำแหน่ง top ของ stack
ให้ทำการ pop ตัวดำเนินการที่ตำแหน่ง top ของ stack
นำออกไปต่อท้ายนิพจน์ผลลัพธ์ และทำการเปรียบเทียบ
ตัวดำเนินการที่นำเข้ามากับตัวดำเนินการที่ตำแหน่ง top
ของ stack ต่อไป จนกระทั่งตัวดำเนินการที่นำเข้ามามี
ลำดับความสำคัญมากกว่าตัวดำเนินการที่ตำแหน่ง top ของ
stack จึงหยุดเปรียบเทียบและให้ทำการ pushตัวดำเนินการ
ที่นำเข้ามานั้นเก็บลงใน stack
3. ถ้าข้อมูลเข้าเป็นเครื่องหมายวงเล็บเปิด ให้ทำการ push เครื่องหมาย
วงเล็บเปิดเก็บลงใน stack
4. ถ้าข้อมูลเข้าเป็นเครื่องหมายวงเล็บปิดให้ทำการ pop ข้อมูลออกจาก
stack นำออกไปเป็นผลลัพธ์โดยจะทำการ pop ต่อไปจนกว่าจะพบ
เครื่องหมายวงเล็บเปิด หลังจากนั้นให้ทิ้งเครื่องหมายวงเล็บเปิดและ
เครื่องหมายวงเล็บปิดคู่เดิมไป
5. ถ้าข้อมูลเข้าหมดให้ทำการ pop ข้อมูลออกจาก stack นำออกไปเป็น
ผลลัพธ์โดยทำการ pop ต่อไปจนกระทั่ง stack ว่าง
**********************************************************************
ตัวอย่าง จงแปลงนิพจน์ infix เป็น postfix
แบบฝึกหัด
จงแปลงนิพจน์ infix ต่อไปนี้ให้เป็นนิพจน์ postfix โดยใช้ stack
1 D - B + C
2 (A + B) * C -D * F + C
3 A * B - (C + D ) + E
