DTS 06 29/7/52

การแปลงนิพจน์ 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. อ่านอักขระในนิพจน์ Infix เข้ามาทีละตัว
2. ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็นตัวอักษรในนิพจน์ Postfix
3. ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับความสำคัญของตัว ดำเนินการที่อ่านเข้ามาเทียบกับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดของสแตก
- ถ้ามีความสำคัญมากกว่า จะถูก push ลงในสแตก
- ถ้ามีความสำคัญน้อยกว่าหรือเท่ากัน จะต้อง pop ตัว
ดำเนินการที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัวอักษรในนิพจน์ Postfix
4. ตัวดำเนินการที่เป็นวงเล็บปิด “)” จะไม่ push ลงในสแตกแต่มีผลให้ตัวดำเนินการอื่น ๆ ถูก pop ออกจากสแตก นำไป เรียงต่อกันในนิพจน์ Postfix จนกว่าจะเจอ “(” จะ pop วงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ
5. เมื่อทำการอ่านตัวอักษรในนิพจน์ Infixหมดแล้ว ให้ทำการ Pop ตัวดำเนินการทุกตัวในสแตกนำมาเรียงต่อในนิพจน์ Postfix