DTS - 06
เนื่องจากนิพจน์ infix มีลำดับความสำคัญของเครื่องหมายโอเปอร์เรเตอร์ซึ่งหมายความว่าโอเปอร์เรเตอร์ที่มาก่อนอาจจะไม่ใช่โอเปอร์เรเตอร์ที่ถูกประมวลผลก่อน ดังนั้น สแตกซึ่งมีคุณสมบัติเป็น LIFO List จึงมีส่วนช่วยในการแปลงนิพจน์ infix ให้เป็นนิพจน์ postfix ในการนี้มีสิ่งที่เกี่ยวข้อง 3 อย่างคือหนึ่งข้อมูลเข้ามาซึ่งเป็นนิพจน์ infix สองข้อมูลออกหรือผลลัพธ์คือนิพจน์ Postfix โดยอัลกอริทึมมีดังนี้ถ้าข้อมูลเข้า (input character) เป็นโอเปอร์แรนด์ให้พิมพ์ออกเป็นผลลัพธ์ (postfix string)ถ้าข้อมูลเข้าเป็นโอเปอร์เรเตอร์ ทำดังนี้1ถ้าสแตกยังว่างอยู่ในpush โอเปอร์เรเตอร์ลงสแตก ถ้าสแตกไม่ว่างให้เปรียบเทียบ โอเปอร์เรเตอร์ที่เข้ามากับโอเปอร์เรเตอร์ที่ท๊อปของสแตก2.ถ้าโอเปอร์เรเตอร์ที่เข้ามามี precedence น้อยกว่าหรือเท่ากับโอเปอร์เรเตอร์ที่ท๊อปของสแตก ให้ pop สแตกไปเป็นผลลัพธ์และเปรียบเทียบกับโอเปอร์เรเตอร์ที่ท๊อปของสแตกต่อไป หยุดเมื่อโอเปอร์เรเตอร์ทีเป็นข้อมูลเข้ามี precedence มากกว่าโอเปอร์เรเตอร์ ที่ท๊อปของสแตก หลังจากนั้นให้ push ข้อมูลลงสแตก ถ้าโอเปอร์เรเตอร์เข้ามีค่ามากกว่า โอเปอร์เรเตอร์ที่ท๊อปของสแตก ให้ push ลงสแตก3. ถ้าข้อมูลเข้าเป็นวงเล็บเปิด ให้ push ลงสแตก4.ถ้าข้อมูลเข้าเป็นวงเล็บปิดให้ pop สแตกจนกว่าจะถึงวงเล็บเปิดและนำผลที่ pop ออกไปเป็นผลลัพธ์ โดยทิ้งวงเล็บปิดและเปิดไป5. ถ้าข้อมูล หมด ให้ pop สแตกไปไว้เป็นผลลัพธ์จนสแตกว่าง
ไม่มีความคิดเห็น:
แสดงความคิดเห็น