การแทนที่ข้อมูลของสแตกแบบอะเรย์
การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสตจะประกอบไปด้วย 2 ส่วน คือ
1. Head Node จะประกอบไปด้วย 2ส่วนคือ top pointer และจำนวนสมาชิกในสแตก
2. Data Node จะประกอบไปด้วยข้อมูล (Data)และพอยเตอร์ ที่ชี้ไปยังข้อมูล
การดำเนินการเกี่ยวกับสแตกการดำเนินการเกี่ยวกับสแตก ได้แก่
1. Create Stack จัดสรรหน่วยความจำให้แก่ Head Nodeและส่งค่าตำแหน่งที่ชี้ไปยัง Head ของสแตกกลับมา
2.Push Stack การเพิ่มข้อมูลลงไปในสแตก
3.Pop stack การนำข้อมูลบนสุดออกจากสแตก
4. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตกโดยไม่มีการลบข้อมูลออกจากสแตก
5.Empty Stack เป็นการตรวจสอบการวางของสแตกเพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลออกจากสแตกที่เรียกว่า Stack Underflow
6. Full Stack เป็นการตรวจสอบว่าสแตกเต็มหรือไม่เพื่อไม่ให้เกิดความผิดพลาดในการนำข้อมูลเข้าสแตกที่เรียกว่า Stack Overflow
7. Stack Count เป็นการนับจำนวนสมาชิกในสแตก8.Destroy Stack เป็นการลบข้อมูลทั้งหมดที่อยู่ใน สแตก
8.Destroy Stack เป็นการลบข้อมูลทั้งหมดที่อยู่ใน สแตก
การใช้ สแตค เพื่อแปลรูปนิพจน์ทางคณิตศาสตร์
รูปแบบนิพจน์ทางคณิตศาสตร์
• นิพจน์ Infix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่ระหว่างตัวดำเนินการ (Operands) เช่น A+B-C
• นิพจน์ Prefix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หน้าตัวดำเนินการ (Operands) เช่น +-AB
• นิพจน์ Postfix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หลังตัวดำเนินการ (Operands) เช่น AC*+
ลำดับการทำงานของตัวดำเนินการทางคณิตศาสตร์ (Operator Priority)
มีการลำดับความสำคัญของตัวดำเนินการจากลำดับสำคัญมากสุดไปน้อยสุด คือ ลำดับที่มีความสำคัญมากที่ต้องทำก่อน ไปจนถึงลำดับที่มีความสำคัญน้อยสุดที่ไว้ทำทีหลัง ดังนี้
เครื่องหมายบวก ( + ) , ลบ ( - )
เครื่องหมายคูณ ( * ) , หาร ( / )
เครื่องหมายวงเล็บเปิด (
เครื่องหมายวงเล็บปิด )
ขั้นตอนการแปลงจากนิพจน์ Infix เป็นนิพจน์ Postfix
1. อ่านอักขระในนิพจน์ Infix เข้ามาทีละตัว
2. ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็นตัวอักษรในนิพจน์ Postfix
3. ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับความสำคัญของตัว ดำเนินการที่อ่านเข้ามาเทียบกับค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดของสแตก
- ถ้ามีความสำคัญมากกว่า จะถูก push ลงในสแตก
- ถ้ามีความสำคัญน้อยกว่าหรือเท่ากัน จะต้อง pop ตัวดำเนินการที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัวอักษรในนิพจน์ Postfix
4. ตัวดำเนินการที่เป็นวงเล็บปิด “)” จะไม่ push ลงในสแตกแต่มีผลให้ตัวดำเนินการอื่น ๆ ถูก pop ออกจากสแตกนำไป เรียงต่อกันในนิพจน์ Postfix จนกว่าจะเจอ “(” จะ popวงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ
5. เมื่อทำการอ่านตัวอักษรในนิพจน์ Infix หมดแล้ว ให้ทำการ Pop ตัวดำเนินการทุกตัวในสแตกนำมาเรียงต่อในนิพจน์Postfix
เช่น
*** เครื่องหมายดำเนินการ (operand) ได้แก่เครื่องหมาย + - * ^ ตัวถูกดำเนินการ ได้แก่ สัญลักษณ์แทนค่าตัวเลข เช่น A B C Dหรือตัวแปรอื่น
สำหรับการดำเนินการด้านการคำนวณนั้น ในระบบคอมพิวเตอร์ไม่สามารถที่จะจัดลำดับของการคำนวณในรูปแบบของ infix ได้ แต่จะแปลงเป็นนิพจน์ของ infix หรือ prefix เสียก่อน โดยลักษณะของการแปลงนิพจน์จะใช้การเปรียบเทียบความสำคัญของตัวดำเนินการ
ลำดับความสำคัญของตัวดำเนินการ
+ -
* /
(
)
ขั้นตอนการแปลง infix เป็น postfix
1.อ่านอักขระใน infix
2.ถ้าเป็น operand ย้ายไปใส่ใน postfix
3.ถ้าเป็น operator จะต้องดูลำดับความสำคัญของตัวดำเนินการด้วยแล้วใส่ลงในสแตกที่เก็บตัวดำเนินการ ถ้ามีค่ามากกว่าให้ push ถ้ามีค่าน้อยกว่าหรือเท่ากันให้ pop ออกแล้วไปเรียงต่อตัวอักษรใน postfix
4.ตัวดำเนินการที่เป็น ) จะไม่ถูก push แต่จะทำให้ตัวดำเนินการตัวอื่นถูก pop ออกมาแล้วไปเรียงต่อใน postfix
5.เมื่ออ่านอักขระใน infix หมด ให้ pop ตัวดำเนินการทุกตัวมาเรียงต่อใน postfix
*** ถ้าเจอเครื่องหมาย + - หลังเครื่องหมาย * / ให้ pop เครื่องหมายในสแตกออก
ถ้าเจอเครื่องหมาย * / หลังเครื่องหมาย + - ให้ push ลงในสแตก
การคำนวณค่า postfix
1.อ่านตัวอักษรจาก postfix ที่ละตัว
2.ถ้าเป็น operand ให้ push ไปเรื่อยๆ
3.ถ้าเป็น operator ให้ pop ตัวอักษรออก 2 ตัว แล้วทำการคำนวณตัวที่ถูก pop ที่หลังจะเป็นตัวตั้งแล้วนำ push ผลลัพธ์ลงไป
สมัครสมาชิก:
ส่งความคิดเห็น (Atom)
ไม่มีความคิดเห็น:
แสดงความคิดเห็น