อัลกอริทึมการแปลงนิพจน์ Infix เป็น นิพจน์ Postfix (ต่อจาก สแตค )


 เราสามารถแปลงนิพจน์ Infix ให้เป็น Postfix ได้โดยอาศัยสแตคที่มีคุณสมบัติการเข้าหลังออกก่อนหรือ LIFO โดยมีอัลกอริทึมในการแปลงนิพจน์ ดังนี้

1. ถ้าข้อมูลเข้า (input) เป็นตัวถูกดำเนินการ (operand) ให้นำออกไปเป็นผลลัพธ์ (output)

2. ถ้าข้อมูลเข้าเป็นตัวดำเนินการ (operator) ให้ดำเนินการดังนี้
2.1 ถ้าสแตคว่าง ให้ push operator ลงในสแตค
2.2 ถ้าสแตคไม่ว่าง ให้เปรียบเทียบ operator ที่เข้ามากับ operator ที่อยู่ในตำแหน่ง TOP ของสแตค
2.2.1 ถ้า operator ที่เข้ามามีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตคให้ push ลงสแตค
2.2.2 ถ้า operator ที่เข้ามามีความสำคัญน้อยกว่าหรือเท่ากับ operator ที่อยู่ในตำแหน่ง TOP ของสแตค ให้ pop สแตคออกไปเป็นผลลัพธ์ แล้วทำการเปรียบเทียบ operator ที่เข้ามากับ operator ที่ตำแหน่ง TOP ต่อไป จะหยุดจนกว่า operator ที่เข้ามาจะมีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตค แล้วจึง push operator ที่เข้ามานั้นลงสแตค

3. ถ้าข้อมูลเข้าเป็นวงเล็บเปิด ให้ push ลงสแตค

4. ถ้าข้อมูลเข้าเป็นวงเล็บปิด ให้ pop ข้อมูลออกจากสแตคไปเป็นผลลัพธ์จนกว่าจะถึงวงเล็บ เปิด จากนั้นทิ้งวงเล็บเปิดและปิดทิ้งไป

5. ถ้าข้อมูลเข้าหมด ให้ pop ข้อมูลออกจากสแตคไปเป็นผลลัพธ์จนกว่าสแตคจะว่าง


Operand
คือตัวแปรต่าง ๆ A,B,C,D,E เช่น A+B*C,(A*B)-C

ลำดับความสำคัญ Operator
  1. เครื่องหมายยกกำลัง ^
  2. เครื่องหมายคูณกับหาร *,/
  3. เครื่องหมายบวกกับลบ +,-
  4. เครื่องหมายวงเล็บ () กระทำก่อนเช่น A+(B*C)
  5. เครื่องหมายระดับเดียวกันไม่มีวงเล็บให้ทำจากซ้ายไปขวา เช่น A+B+C
เมื่อการประมวลนิพจน์ infix เป็นไปด้วยความยากที่การคำนวณไม่เป็นไปตามลำดับของเครื่องหมายโอเปอร์เรเตอร์ที่มีก่อนหลัง คอมไพเลอร์จึงแปลงนิพจน์ infix ให้เป็น postfix เสียก่อน

นิพจน์ Postfix ก็คือนิพจน์ที่มีโอเปอเรเตอร์อยู่หลังโอเปอร์แรนด์ทั้งสองของมัน เช่น

AB+ หมายถึง A+B

AB- หมายถึง A-B

AB* หมายถึง A*B


ตัวอย่างการแปลงนิพจน์ Infix เป็นนิพจน์ Postfix
นิพจน์ A + B * C

นิพจน์ (A * B) + (C / D)

นิพจน์ A / B + (C – D)

นิพจน์ (A + B) * ( C ^ D – E ) * F

0 ความคิดเห็น:

แสดงความคิดเห็น