เรื่อง stack
การใช้สแตกเพื่อแปลงรูปนิพจน์ทางคณิตศาสตร์
- นิพจน์ Infix คือ นิพจน์ที่เครืองหมายดำเนินการ(Operator) อยู่ระหว่างตัวดำเนินการ(Operands) เช่น a+b-c
- นิพจน์ Perfix คือ นิพจน์ที่เครื่องหมายดำเนินการ(Operator) อยู่หน้าตัวดำเนินการ(Operands) เช่น +-ab
- นิพจน์ Postfix คือ นิพจน์ที่เครื่องหมายดำเนินการ(Operator) อยู่หลังตัวดำเนินการ(Operands) เช่น ab*/
ขั้นตอนการแปลงจากนิพจน์ Infix เป็นนิพจน์ Postfix
1.อ่านอักขระในนิพจน์ Infix เข้ามาทีละตัว
2.ถ้าเป็นตัวถูกดำเนินการจะย้ายไปเป็นตัวอักษรในนิพจน์ Postfix
3.ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับความสำคัญของตัวดำเนินารที่อ่านเข้ามาเทียบกับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดของสแตก
-ถ้ามีความสำคัญมากจะถูก push ลงในสแตก
-ถ้ามีความสำคัญน้อยกว่าหรือเท่ากัน จะต้อง pop ตัวดำเนินการที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัวอักษรในนิพจน์ Postfix
4.ตัวดำเนินการที่เป็น ")" จะไม่ push ลงในสแตกแต่มีผลให้ตัวดำเนินการอื่นๆถูก pop ออกจากสแตก นำไปเรียงต่อกันในนิพจน์ Prostfix จนกว่าจะเจอ ")" จะ pop วงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ
5.เมื่อทำการอ่านตัวอักษรในนิพจน์ Infix หมดแล้ว ให้ทำการ pop ตัวดำเนินการทุกตัวในสแตกนำมาเรียงต่อใน Prostfix
*********************************************************************************
ไม่มีความคิดเห็น:
แสดงความคิดเห็น