Park-Kachen

04 สิงหาคม 2552

DTS06-29-07-2552


สรุปสิ่งที่ได้จากการเรียน เรื่อง Stack (ต่อ)

Operation ของสแตค
* การเพิ่มข้อมูลลงในสแตค (pushing stack)
*การดึงข้อมูลออกจากสแตค (popping stack)

การเพิ่มข้อมูลลงในสแตคการเพิ่มข้อมูลลงในสแตค คือ การนำเข้ามูลเข้าสู่สแตคโดยทับข้อมูลที่อยู่บนสุดของสแตค ข้อมูลจะสามารถนำเข้าได้เรื่อยๆ จนกว่าสแตคจะเต็ม สมมติว่าสแตคจองเนื้อที่ไว้ N ตัว ถ้าหากค่า TOP เป็น 0 แสดงว่าสแตคว่าง หากค่า TOP = N แสดงว่าสแตคเต็มไม่สามารถเพิ่มข้อมูลลงในสแตคได้อีก


จากรูปแสดง การ Push ข้อมูล ABC ลงในสแตคที่มีการจองเนื้อที่ไว้ N ตัว โดยมี TOP ชี้ข้อมูลตัวที่เข้ามาล่าสุด โดยค่าของ TOP จะเพิ่มขึ้นทุกครั้งเมื่อมีข้อมูลเข้ามาในสแตค


การดึงข้อมูลออกจากสแตคก่อนที่จะดึงข้อมูลออกจากสแตคต้องตรวจสอบก่อนว่าสแตคมีข้อมูลอยู่หรือไม่ หรือว่าเป็นสแตคว่าง (Empty Stack)
การใช้ สแตค เพื่อแปลรูปนิพจน์ทางคณิตศาสตร์

รูปแบบนิพจน์ทางคณิตศาสตร์
• นิพจน์ Infix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่ระหว่างตัวดำเนินการ (Operands) เช่น A+B-C• นิพจน์ Prefix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หน้าตัวดำเนินการ (Operands) เช่น +-AB

• นิพจน์ Postfix คือ นิพจน์ที่เครื่องหมายดำเนินการ (Operator) อยู่หลังตัวดำเนินการ (Operands) เช่น AC*+

ลำดับการทำงานของตัวดำเนินการทางคณิตศาสตร์ (Operator Priority)

มีการลำดับความสำคัญของตัวดำเนินการจากลำดับสำคัญมากสุดไปน้อยสุด คือ ลำดับที่มีความสำคัญมากที่ต้องทำก่อน ไปจนถึงลำดับที่มีความสำคัญน้อยสุดที่ไว้ทำทีหลัง ดังนี้

1.ทำในเครื่องหมายวงเล็บ
2.เครื่องหมายยกกำลัง ( ^ )
3.เครื่องหมายคูณ ( * ) , หาร ( / )
4.เครื่องหมายบวก ( + ) , ลบ ( - )

ตัวอย่างนิพจน์ทางคณิตศาสตร์และลำดับการคำนวณ

อัลกอริทึมการแปลงนิพจน์ Infix เป็น นิพจน์ Postfix
เราสามารถแปลงนิพจน์ Infix ให้เป็น Postfix ได้โดยอาศัยสแตคที่มีคุณสมบัติการเข้าหลังออกก่อนหรือ LIFO โดยมีอัลกอริทึมในการแปลงนิพจน์ ดังนี้
1. ถ้าข้อมูลเข้า (input) เป็นตัวถูกดำเนินการ (operand) ให้นำออกไปเป็นผลลัพธ์ (output)
2. ถ้าข้อมูลเข้าเป็นตัวดำเนินการ (operator) ให้ดำเนินการดังนี้
2.1 ถ้าสแตคว่าง ให้ push operator ลงในสแตค
2.2 ถ้าสแตคไม่ว่าง ให้เปรียบเทียบ operator ที่เข้ามากับ operator ที่อยู่ในตำแหน่ง TOP ของสแตค
2.2.1 ถ้า operator ที่เข้ามามีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตคให้ push ลงสแตค2.2.2 ถ้า operator ที่เข้ามามีความสำคัญน้อยกว่าหรือเท่ากับ operator ที่อยู่ในตำแหน่ง TOP ของสแตค ให้ pop สแตคออกไปเป็นผลลัพธ์ แล้วทำการเปรียบเทียบ operator ที่เข้ามากับ operator ที่ตำแหน่ง TOP ต่อไป จะหยุดจนกว่า operator ที่เข้ามาจะมีความสำคัญมากกว่า operator ที่ตำแหน่ง TOP ของสแตค แล้วจึง push operator ที่เข้ามานั้นลงสแตค
3. ถ้าข้อมูลเข้าเป็นวงเล็บเปิด ให้ push ลงสแตค
4. ถ้าข้อมูลเข้าเป็นวงเล็บปิด ให้ pop ข้อมูลออกจากสแตคไปเป็นผลลัพธ์จนกว่าจะถึงวงเล็บ เปิด จากนั้นทิ้งวงเล็บเปิดและปิดทิ้งไป
5. ถ้าข้อมูลเข้าหมด ให้ pop ข้อมูลออกจากสแตคไปเป็นผลลัพธ์จนกว่าสแตคจะว่าง

ตัวอย่างการแปลงนิพจน์ Infix เป็นนิพจน์ Postfix




posted by Park-Kachen at 07:43

0 Comments:

แสดงความคิดเห็น

<< Home