สรุป
การดำเนินการเกี่ยวกับสแตก ได้แก่ 1. Create Stack การจัดสรรความจำให้แก่ Head Node และส่งค่าตำแหน่งที่ชี้ไปยัง Head ของสแตกกลับมา 2. Push Stack การเพิ่มข้อมูลลงไปในสแตก 3. Pop Stack การนำข้อมูลบนสุดออกจากสแตก 4. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสแตก5. Empty Stack เป็นการตรวจสอบการว่างของสแตก 6. Full Stack เป็นการตรวจสอบว่าสแตกเต็มหรือไม่ 7. Stack Count เป็นการนับจำนวนสมาชิกใน สแตก 8. Destroy Stack เป็นการลบข้อมูลทั้งหมดที่อยู่ในสแตก
การใช้ สแตกเพื่อแปลรูปนิพจน์ทางคณิตศาสตร์รูปแบบนิพจน์ทางคณิตศาสตร์
• นิพจน์ Infix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่ระหว่างตัวดำเนินการ (Operands)
เช่น A+B-C
• นิพจน์ Prefix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หน้าตัวดำเนินการ (Operands)
เช่น +-AB
• นิพจน์ Postfix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หลังตัวดำเนินการ (Operands)
เช่น AC*+
เราสามารถแปลงนิพจน์ Infix ให้เป็น Postfix ได้โดยอาศัยสแตกที่มีคุณสมบัติการเข้าหลังออกก่อนหรือ LIFO โดยมีอัลกอริทึมในการแปลงนิพจน์ ดังนี้
1. ถ้าข้อมูลเข้า (input) เป็นตัวถูกดำเนินการ (operand) ให้นำออกไปเป็นผลลัพธ์ (output)
2. ถ้าข้อมูลเข้าเป็นตัวดำเนินการ (operator) ให้ดำเนินการดังนี้
2.1 ถ้าสแตกว่าง ให้ push operator ลงในสแตก
2.2 ถ้าสแตกไม่ว่าง ให้เปรียบเทียบ operator ที่เข้ามากับ operator ที่อยู่ในตำแหน่ง TOP ของสแตก
2.3.ถ้า operator ที่เข้ามามีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตกให้ push ลงสแตก
2.4. ถ้า operator ที่เข้ามามีความสำคัญน้อยกว่าหรือเท่ากับ operator ที่อยู่ในตำแหน่ง TOP ของสแตก ให้ pop สแตกออกไปเป็นผลลัพธ์ แล้วทำการเปรียบเทียบ operator ที่เข้ามากับ operator ที่ตำแหน่ง TOP ต่อไป จะหยุดจนกว่า operator ที่เข้ามาจะมีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตก แล้วจึง push operator ที่เข้ามานั้นลงสแตก
3. ถ้าข้อมูลเข้าเป็นวงเล็บเปิด ให้ push ลงสแตก
4. ถ้าข้อมูลเข้าเป็นวงเล็บปิด ให้ pop ข้อมูลออกจากสแตกไปเป็นผลลัพธ์จนกว่าจะถึงวงเล็บ เปิด จากนั้นทิ้งวงเล็บเปิดและปิดทิ้งไป
5. ถ้าข้อมูลเข้าหมด ให้ pop ข้อมูลออกจากสแตกไปเป็นผลลัพธ์จนกว่าสแตกจะว่าง
ไม่มีความคิดเห็น:
แสดงความคิดเห็น