การแปลงสูตรคณิตเป็น Postfix ผ่านแนวคิด Stack

จากเดิมสูตร (9+3)/2-4 เครื่องหมายดำเนินการ (operators) เช่น +, -, *, / จะอยู่ในรูปของ Infix notation หมายถึง อยู่ระหว่างกลางของ  ตัวถูกดำเนินการ (operands) ทั้งสองตัว Postfix Notation, Reverse Polish Notation หรือ Polish Postfix เป็นอีกหนึ่งวิธีในการมองสูตรคณิตศาสตร์ โดยการย้ายเครื่องหมายดำเนินการของตัวถูกดำเนินการทั้งสองตัวไปไว้ข้างหลัง เช่น

5+6 ย้ายไปเป็น 56+

10*2+2 ย้ายไปเป็น 10 2*2+

Postfix Notation ช่วยให้การคำนวนสมการด้วยคอมพิวเตอร์ง่ายขึ้น และซับซ้อนน้อยลงสำหรับคอมพิวเตอร์

หลักการของ Stack

Stack เป็นแนวคิดหนึ่งของการเก็บข้อมูลแบบ Array ที่ ข้อมูลที่เข้าก่อนจะถูกนำออกทีหลังสุด ส่วนข้อมูลที่เข้าทีหลังสุดจะออกก่อน (LIFO: Last In First Out) ต่างการแนวคิดของ Queue ข้อมูลที่มาก่อนจะออกก่อน (FIFO: first in first out) ตามคิว

ดังนั้นจะปรับใช้จากหลักการของ Stack มาเก็บข้อมูลที่ใส่ตามลำดับ และหยิบใช้งานได้แค่ข้อมูลแถวสุดท้าย

โดยมีขั้นตอน และกฏดังนี้

1. เริ่มไล่ดูตัวอักษรในสูตรทีละตัว หากเป็นตัวถูกดำเนินการ จะนำไปใส่ใน Postfix แต่หากเป็นตัวดำเนินการจะนำไปใส่ใน Stack
2. ตัวดำเนินการใหม่ที่จะถูกเพิ่มเข้าไปใน Stack ต้องเช็คว่าตัวล่าสุดมี ลำดับความสำคัญ (Priority) มากกว่าหรือไม่ หากมากกว่าต้องนำตัวที่อยู่ใน Stack ย้ายไปอยู่ใน Postfix ก่อน ถึงจะนำตัวที่ ลำดับความสำคัญน้อยกว่าใส่ลงไปใน Stack ได้
3. เมื่อเจอตัวดำเนินการเป็น ( หรือ ) จะถูกใส่ลงใน Stack ทันที
4. เมื่อวงเล็บเปิดและปิดลง โดยมีตัวดำเนินการอยู่ด้านใน จะย้ายเฉพาะตัวดำเนินการดังกล่าวไปที่ Postfix และลบวงเล็บทั้งสองตัวออกจาก Stack
5. เมื่อตัวดำเนินการใน Stack เหลือตัวเดียว ให้นำใส่ใน Postfix

ตัวอย่าง: ((10*2)/4)+(18/2) คำตอบคือ 14

จากตารางผลลัพท์คือ 10 2 * 4 / 18 2 / + เราสามารถคำนวนทางคณิตศาสตร์ได้ ด้วยการไล่ตัวอักษรจากซ้ายไปขวา หากเจอตัวดำเนินการให้นำ ตัวถูกดำเนินการ สองตัวก่อนหน้า มาดำเนินการกันตามตัวดำเนินการที่เจอ ตัวอย่างการคำนวนจากผลลัพท์

10 2 * 4 / 18 2 / +
20 4 / 18 2 / +
5 18 2 / +
5 9 +
14

คำตอบเท่ากับ 14

อ้างอิง: youtube.com/@YaarPadhaDe