การประยุกต์ใช้สแตก
จะใช้ในงานด้านปฏิบัติการของเครื่องคอมพิวเตอร์ที่ขั้นตอนการทำงานต้องการเก็บข่าวสารอับดันแรกสุดไว้ใช้หลังสุด
การคำนวณนิพจน์ทางคณิตศาสตร์ สามารถเขียนได้ 3รูปแบบ
1.นิพจน์ Infix (Operator จะอยู่ตรงกลางระหว่าง Operand)
2.นิพจน์ Postfix (จะต้องเขียน Operand ตัวที่1 และตัวที่2 ก่อน แล้วตามด้วย Operator)
3.นิพจน์ Prefix(จะต้องเขียน Operator ก่อนแล้วตามด้วย Operand ตัวที่1 และตัวที่2)
ค่าลำดับความสำคัญของตัวดำเนินการ
Operator | ค่าเมื่ออ่านเข้ามา | ค่าในสแตก |
+,- | 1 | 2 |
*,/ | 3 | 4 |
( | 5 | 0 |
) | 0 | - |
ขั้นตอนการแปลงจากนิพจน์Infix เป็นนิพจน์Postfix
1.อ่านอักขระในนิพจน์ Infix เข้ามาทีละตัว
2.ถ้าเป็นOperand จะถูกย้ายไปเป็นตัวอักษรในนิพจน์Postfix
3.ถ้าเป็นOperator จำนำค่าลำดับความสำคัญของOperatorที่อ่านเข้ามาเทียบกับค่าลำดับความสำคัญของOperatorที่อยู่บนสุดของสแตก
- ถ้ามีความสำคัญมากกว่า จะถูกPushลงไปในสแตก
- ถ้ามีความสำคัญน้อยกว่าหรือเท่ากัน จะต้องPop Operator ที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัวอักษรในนิพจน์Postfix
4. Operatorที่เป็น")" จะไม่Push ลงในสแตก แต่มีผลให้Operatorตัวอื่นๆถูกPop ออกจากสแตกนำไปเรียงต่อกันในนิพจน์Postfix จนกว่าจะเจอ "(" จะPop "(" ออกจากสแตกแต่ไม่นำไปเรียงต่อ
5. เมื่อทำการอ่านตัวอักษรในนิพจน์Infix หมดแล้ว ให้ทำการPop Operator ทุกตัวในสแตกนำมาเรียงต่อในนิพจน์Postfix
ขั้นตอนในการคำนวณจากนิพจน์Postfix
1.อ่านตัวอักษรในนิพจน์Postfix จากซ้ายไปขาทีละตัวอักษร
2.ถ้าเป็นOperand ให้ทำการPush Operandนั้นลงในสแตก แล้วกลับไปอ่านอักษรตัวใหม่เข้ามา
3.ถ้าเป็นOperator ให้ทำการPop ค่าออกจากสแตก 2 ค่า โดยตัวแรกเป็นOperand ตัวที่1 และตัวที่2 ตามลำดับ
4.ทำการคำนวณ
5.ทำการPush ผลลัพธ์ที่ได้จากการคำนวณ
6.ถ้าตัวอักษรในนิพจน์Postfix ยังไม่หมดให้กลับไปทำข้อ1ใหม่
ไม่มีความคิดเห็น:
แสดงความคิดเห็น