การแปลงนิพจน์ Infix ให้เป็น Postfix
ผู้เขียนโปรแกรมสั่งให้เครื่องคำนวณต้องเขียนนิพจน์ที่ต้องการไปในตัวโปรแกรม ซึ่งนิพจน์เหล่านี้เรียกว่า นิพจน์ Infix คือนิพจน์ที่มีโอเปอร์เรเตอร์ (Operator) อยู่ระหว่างโอเปอร์แรนด์ (Operand) ทั้งสอง เช่น A+B เครื่องหมาย + เป็นโอเปอร์เรเตอร์ระหว่างโอเปอร์แรนด์ A และ B ซึ่งเห็นว่าเป็นนิพจน์ที่มนุษย์คุ้นเคย ข้อเสียของนิพจน์ infix ทีททำให้คอมไพเลอร์ยุ่งยาก คือลำดับความสำคัญของโอเปอร์เรเตอร์ (Precedence) ที่ต่างกัน เช่นเครื่องหมายยกกำลัง (ใช้ ^ ในการเขียนโปรแกรม) มีความสำคัญมากกว่าเครื่องหมายคูณ และหาร และเครื่องหมายคูณและหารมีความสำคัญมากกว่าเครื่องหมายบวกและลบ
Operator คือเครื่องหมายกระทำ + - * / ^
Operand คือตัวแปรต่าง ๆ A,B,C,D,E เช่น A+B*C,(A*B)-C
ลำดับความสำคัญ Operator
เครื่องหมายคูณกับหาร *,/
เครื่องหมายบวกกับลบ +,-
เครื่องหมายวงเล็บ () กระทำก่อนเช่น A+(B*C)
เครื่องหมายระดับเดียวกันไม่มีวงเล็บให้ทำจากซ้ายไปขวา เช่น A+B+C
เมื่อการประมวลนิพจน์ infix เป็นไปด้วยความยากที่การคำนวณไม่เป็นไปตามลำดับของเครื่องหมายโอเปอร์เรเตอร์ที่มีก่อนหลัง คอมไพเลอร์จึงแปลงนิพจน์ infix ให้เป็น postfix เสียก่อน
นิพจน์ Postfix ก็คือนิพจน์ที่มีโอเปอเรเตอร์อยู่หลังโอเปอร์แรนด์ทั้งสองของมัน เช่น
AB+ หมายถึง A+B
AB- หมายถึง A-B
AB* หมายถึง A*B
แปลงนิพจน์ Infix ให้เป็นนิพจน์ Postfix
เนื่องจากนิพจน์ infix มีลำดับความสำคัญของเครื่องหมายโอเปอร์เรเตอร์ซึ่งหมายความว่าโอเปอร์เรเตอร์ที่มาก่อนอาจจะไม่ใช่โอเปอร์เรเตอร์ที่ถูกประมวลผลก่อน ดังนั้น สแตกซึ่งมีคุณสมบัติเป็น LIFO List จึงมีส่วนช่วยในการแปลงนิพจน์ infix ให้เป็นนิพจน์ postfix ในการนี้มีสิ่งที่เกี่ยวข้อง 3 อย่างคือหนึ่งข้อมูลเข้ามาซึ่งเป็นนิพจน์ infix สองข้อมูลออกหรือผลลัพธ์คือนิพจน์ Postfix โดยอัลกอริทึมมีดังนี้
ถ้าข้อมูลเข้า (input character) เป็นโอเปอร์แรนด์ให้พิมพ์ออกเป็นผลลัพธ์ (postfix string)
ถ้าข้อมูลเข้าเป็นโอเปอร์เรเตอร์ ทำดังนี้
1.1 ถ้าสแตกยังว่างอยู่ในpush โอเปอร์เรเตอร์ลงสแตก
1.2 ถ้าสแตกไม่ว่างให้เปรียบเทียบ โอเปอร์เรเตอร์ที่เข้ามากับโอเปอร์เรเตอร์ที่ท๊อปของสแตก
2.2.1ถ้าโอเปอร์เรเตอร์ที่เข้ามามี precedence น้อยกว่าหรือเท่ากับโอเปอร์เรเตอร์ที่ท๊อปของสแตก ให้ pop สแตกไปเป็นผลลัพธ์และเปรียบเทียบกับโอเปอร์เรเตอร์ที่ท๊อปของสแตกต่อไป หยุดเมื่อโอเปอร์เรเตอร์ทีเป็นข้อมูลเข้ามี precedence มากกว่าโอเปอร์เรเตอร์ ที่ท๊อปของสแตก หลังจากนั้นให้ push ข้อมูลลงสแตก
2.2.2 ถ้าโอเปอร์เรเตอร์เข้ามีค่ามากกว่า โอเปอร์เรเตอร์ที่ท๊อปของสแตก ให้ push ลงสแตก
3. ถ้าข้อมูลเข้าเป็นวงเล็บเปิด ให้ push ลงสแตก
4.ถ้าข้อมูลเข้าเป็นวงเล็บปิดให้ pop สแตกจนกว่าจะถึงวงเล็บเปิดและนำผลที่ pop ออกไปเป็นผลลัพธ์ โดยทิ้งวงเล็บปิดและเปิดไป
5. ถ้าข้อมูล หมด ให้ pop สแตกไปไว้เป็นผลลัพธ์จนสแตกว่าง
ตัวอย่างโจทย์การเปลี่ยน infix --> postfix
ที่ได้จาก อ.ปรมัตถ์ปัญปรัชญ์
ที่ได้จาก อ.ปรมัตถ์ปัญปรัชญ์
