Lecture 6 เรื่อง Tree

ทรี (Tree) เป็นโครงสร้างข้อมูลที่ความสัมพันธ์ระหว่าง โหนดจะมีความสัมพันธ์ลดหลั่นกันเป็นลำดับชั้น (Hierarchical Relationship)
นิยามของทรี
1. นิยามทรีด้วยนิยามของกราฟ
ทรี คือ กราฟที่ต่อเนื่องโดยไม่มีวงจรปิด (loop) ในโครงสร้าง โหนดสองโหนดใด ๆ ในทรีต้องมีทางติดต่อกันทางเดียวเท่านั้น และทรีที่มี N โหนด ต้องมีกิ่งทั้งหมด N-1 เส้น
2. นิยามทรีด้วยรูปแบบรีเคอร์ซีฟ
ทรีประกอบด้วยสมาชิกที่เรียกว่า โหนด โดยที่ ถ้าว่าง ไม่มีโหนดใด ๆ เรียกว่า นัลทรี (Null Tree) และถ้ามีโหนดหนึ่งเป็นโหนดราก ส่วนที่เหลือจะแบ่งเป็นทรีย่อย (Sub Tree)T1, T2, T3,…,Tk โดยที่ k>=0 และทรีย่อยต้องมีคุณสมบัติเป็นทรี
นิยามที่เกี่ยวข้องกับทรี
1. ฟอร์เรสต์ (Forest) หมายถึง กลุ่มของทรีที่เกิดจากการเอาโหนดรากของทรีออกหรือ เซตของทรีที่แยกจากกัน (Disjoint Trees)
2. ทรีที่มีแบบแผน (Ordered Tree) หมายถึง ทรีที่โหนดต่าง ๆ ในทรีนั้นมีความสัมพันธ์ที่แน่นอน
3. ทรีคล้าย (Similar Tree) คือ ทรีที่มีโครงสร้างเหมือนกัน หรือทรีที่มีรูปร่างของทรีเหมือนกัน
โดยไม่คำนึงถึงข้อมูลที่อยู่ในแต่ละโหนด
4. ทรีเหมือน (Equivalent Tree) คือ ทรีที่เหมือนกันโดยสมบูรณ์ โดยต้องเป็นทรีที่คล้ายกันและแต่ละ
โหนดในตำแหน่งเดียวกันมีข้อมูลเหมือนกัน
5. กำลัง (Degree) หมายถึง จำนวนทรีย่อยของโหนด นั้น ๆ
6. ระดับของโหนด (Level of Node) คือ ระยะทางในแนวดิ่งของโหนดนั้น ๆ ที่อยู่ห่างจากโหนดราก เมื่อกำหนดให้ โหนดรากของทรีนั้นอยู่ระดับ 1และกิ่งแต่ละกิ่งมีความเท่ากันหมด คือ ยาวเท่ากับ 1 หน่วย ซึ่งระดับของโหนดจะเท่ากับจำนวนกิ่งที่น้อยที่สุดจากโหนดรากไปยังโหนดใด ๆ บวกด้วย 1 และจำนวนเส้นทางตามแนวดิ่งของโหนดใด ๆ ซึ่งห่างจากโหนดราก เรียกว่า ความสูง (Height) หรือความลึก (Depth)
การแทนที่ทรีในหน่วยความจำหลัก
การแทนที่โครงสร้างข้อมูลแบบทรีในความจำหลักจะมีพอยเตอร์เชื่อมโยงจากโหนดแม่ไปยังโหนดลูก แต่ละโหนดต้องมีลิงค์ฟิลด์เพื่อเก็บที่อยู่ของโหนดลูกต่าง ๆ นั่นคือ จำนวน ลิงค์ฟิลด์ของแต่ละโหนดขึ้นอยู่กับจำนวนของโหนดลูก การแทนที่ทรี ซึ่งแต่ละโหนดมีจำนวนลิงค์ฟิลด์ไม่เท่ากัน ทำให้ยากต่อการปฏิบัติการ วิธีการแทนที่ที่ง่ายที่สุด คือ ทำให้แต่ละโหนดมี จำนวนลิงค์ฟิลด์เท่ากัน โดยอาจใช้วิธีการต่อไปนี้
1. โหนดแต่ละโหนดเก็บพอยเตอร์ชี้ไปยังโหนดลูกทุกโหนด การแทนที่ทรีด้วยวิธีนี้ จะให้จำนวนฟิลด์ใน
แต่ละโหนดเท่ากันโดยกำหนดให้มีขนาดเท่ากับจำนวนโหนดลูกของโหนดที่มีลูกมากที่สุด โหนดใดไม่มีโหลดลูกก็ให้ค่าพอยเตอร์ในลิงค์ฟิลด์นั้นมีค่าเป็น Null และให้ลิงค์ฟิลด์แรกเก็บค่าพอยเตอร์ชี้ไปยังโหนด ลูกลำดับที่หนึ่ง ลิงค์ฟิลด์ที่สองเก็บค่าพอยเตอร์ชี้ไปยังโหนดลูกลำดับที่สอง และลิงค์ฟิลด์อื่นเก็บ
ค่าพายเตอร์ของโหนดลูกลำดับ ถัดไปเรื่อย ๆ
การแทนทรีด้วยโหนดขนาดเท่ากันค่อนข้างใช้เนื้อที่จำนวนมาก เนื่องจากแต่ละโหนดมีจำนวนโหนดลูกไม่เท่ากันหรือบางโหนดไม่มีโหนดลูกเลยถ้าเป็นทรีที่แต่ละโหนดมีจำนวนโหนดลูกที่แตกต่างกันมาก จะเป็นการสิ้นเปลืองเนื้อที่ในหน่วยความจำโดยเปล่าประโยชน์
2. แทนทรีด้วยไบนารีทรี
เป็นวิธีแก้ปัญหาเพื่อลดการ สิ้นเปลืองเนื้อที่ในหน่วยความจำก็คือกำหนดลิงค์ฟิลด์ให้มีจำนวนน้อยที่สุดเท่าที่จำเป็นเท่านั้นโดยกำหนดให้แต่ละโหนดมีจำนวนลิงค์ฟิลด์สองลิงค์ฟิลด์
-ลิงค์ฟิลด์แรกเก็บที่อยู่ของโหนดลูกคนโต
-ลิงค์ฟิลด์ที่สองเก็บที่อยู่ของโหนดพี่น้องที่เป็นโหนดถัดไปโหนดใดไม่มีโหนดลูกหรือไม่มีโหนดพี่น้องให้ค่าพอยน์เตอร์ในลิงค์ฟิลด์มีค่าเป็น Null
การแปลงทรีทั่วไปให้เป็นไบนารีทรี
ขั้นตอนการแปลงทรีทั่วๆ ไปให้เป็นไบนารีทรี มีลำดับขั้นตอนการแปลง ดังต่อไปนี้
1. ให้โหนดแม่ชี้ไปยังโหนดลูกคนโต แล้วลบ
ความสัมพันธ์ ระหว่างโหนดแม่และโหนดลูกอื่น ๆ
2. ให้เชื่อมความสัมพันธ์ระหว่างโหนดพี่น้อง
3. จับให้ทรีย่อยทางขวาเอียงลงมา 45 องศา
การท่องไปในไบนารีทรี
ปฏิบัติการที่สำคัญในไบนารีทรี คือ การท่องไปในไบนารีทรี (Traversing Binary Tree) เพื่อเข้าไปเยือนทุก ๆ โหนดในทรี ซึ่งวิธีการท่องเข้าไปต้องเป็นไปอย่างมีระบบแบบแผน สามารถเยือนโหนดทุก ๆ โหนด ๆ ละหนึ่งครั้งวิธีการท่องไปนั้นมีด้วยกันหลายแบบแล้วแต่ว่าต้องการลำดับขั้นตอนการเยือนอย่างไร โหนดที่ถูกเยือนอาจเป็นโหนดแม่ (แทนด้วย N) ทรีย่อยทางซ้าย (แทนด้วย L)หรือทรีย่อยทางขวา (แทนด้วย R)
มีวิธีการท่องเข้าไปในทรี 6 วิธี คือ
NLR LNR LRN NRL RNL และ RLN
วิธีการท่องเข้าไปไบนารีทรีที่นิยมใช้กันมากเป็นการท่องจากซ้ายไปขวา 3 แบบแรกเท่านั้นคือ NLR LNR และ LRN
1. การท่องไปแบบพรีออร์เดอร์ (Preorder Traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี
NLR
2.การท่องไปแบบอินออร์เดอร์(Inorder Traversal)เป็นการเดินเข้าไปเยือนโหนดต่าง ๆ ในทรีด้วยวิธี LNR
3. การท่องไปแบบโพสออร์เดอร์ (Postorder Traversal) เป็นการเดินเข้าไปเยือนโหนดต่าง ๆในทรีด้วยวิธี LRN
เอ็กซ์เพรสชันทรี (Expression Tree)
เป็นการนำเอาโครงสร้างทรีไปใช้เก็บนิพจน์ทางคณิตศาสตร์โดยเป็นไบนารีทรี ซึ่งแต่ละโหนดเก็บตัวดำเนินการ (Operator) และและตัวถูกดำเนินการ (Operand) ของนิพจน์คณิตศาสตร์นั้น ๆ ไว้ หรือ อาจจะเก็บค่านิพจน์ทางตรรกะ (Logical Expression) นิพจน์เหล่านี้เมื่อแทนในทรีต้องคำนึงลำดับขั้นตอนในการคำนวณตามความสำคัญของเครื่องหมายด้วยโดยมีความสำคัญตามลำดับดังนี้
- ฟังก์ชัน
- วงเล็บ
- ยกกำลัง
- เครื่องหมายหน้าเลขจำนวน (unary)
- คูณ หรือ หาร
- บวก หรือ ลบ
- ถ้ามีเครื่องหมายที่ระดับเดียวกันให้ทำจากซ้ายไปขวา
ไบนารีเซิร์ชทรี
ไบนารีเซิร์ชทรี (Binary Search Tree) เป็นไบนารีทรีที่มีคุณสมบัติที่ว่าทุก ๆ โหนดในทรี ค่าของ
โหนดรากมีค่ามากกว่าค่าของทุกโหนดในทรีย่อยทางซ้าย และมีค่าน้อยกว่าหรือเท่ากับค่าของทุกโหนดในทรีย่อยทางขวาและในแต่ละทรีย่อยก็มี คุณสมบัติเช่นเดียวกัน ปฏิบัติการในไบนารีเซิร์ชทรี ปฏิบัติการ
เพิ่มโหนดเข้าหรือดึงโหนดออกจากไบนารีเซิร์ชทรีค่อนข้างยุ่งยากกว่าปฏิบัติการในโครงสร้างอื่น ๆ เนื่องจากหลังปฏิบัติการเสร็จเรียบร้อยแล้วต้องคำนึงถึงความเป็นไบนารีเซิร์ชทรีของทรีนั้นด้วยซึ่งมีปฏิบัติการดังต่อไปนี้
(1) การเพิ่มโหนดในไบนารีเซิร์ชทรี
(2) การดึงโหนดในไบนารีเซิร์ชทรี
วิธีดึงโหนดออกอาจแยกพิจารณาได้ 3 กรณีดังต่อไปนี้
ก. กรณีโหนดที่จะดึงออกเป็นโหนดใบการดึงโหนดใบออกในกรณีนี้ทำได้ง่ายที่สุดโดยการดึงโหนดนั้นออกได้ทันที เนื่องจากไม่กระทบกับโหนดอื่นมากนัก วิธีการก็คือให้ค่าในลิงค์ฟิลด์ของโหนดแม่ซึ่งเก็บที่อยู่
ของโหนดที่ต้องการดึงออกให้มีค่าเป็น Null
ข. กรณีโหนดที่ดึงออกมีเฉพาะทรีย่อยทางซ้ายหรือทรีย่อยทางขวาเพียงด้านใดด้านหนึ่ง วิธีการดึง
โหนดนี้ออกสามารถใช้วิธีการเดียวกับการดึงโหนดออกจากลิงค์ลิสต์ โดยให้โหนดแม่ของโหนดที่จะดึงออกชี้ไปยังโหนดลูกของโหนดนั้นแทน
ค. กรณีโหนดที่ดึงออกมีทั้งทรีย่อยทางซ้ายและทรีย่อยทางขวาต้องเลือกโหนดมาแทนโหนดที่ถูกดึงออก โดยอาจจะเลือกมาจากทรีย่อยทางซ้ายหรือทรีย่อยทางขวาก็ได้
- ถ้าโหนดที่มาแทนที่เป็นโหนดที่เลือกจากทรีย่อยทางซ้ายต้องเลือกโหนดที่มีค่ามากที่สุดในทรีย่อยทางซ้ายนั้น
- ถ้าโหนดที่จะมาแทนที่เป็นโหนดที่เลือกมาจากทรีย่อยทางขวา ต้องเลือกโหนดที่มีค่าน้อยที่สุดในทรีย่อยทางขวานั้น

DTS 08-26-08-2552

Lecture 5 เรื่อง Queue

คิว Queue เป็นโครงสร้างข้อมูลแบบเชิงเส้น หรือ ลิเนียร์ลิสต์ การเพิมข้อมูลจะทำที่ปลายข้างหนึ่ง ที่เรียกว่าส่วนท้าย หรือ เรียร์ (Rear) และนำข้อมูลออกทางปลายอีกข้างหนึ่งเรียกว่า ส่วนหน้า หรือ ฟรอนต์ (Front) ลักษณะการทำงานของคิว จะเป็นแบบ FIFO
การทำงานของคิว ถ้าใส่สมาชิกตัวใหม่ลงในคิวเรียกว่า Enqueue
enqueue หรือ queue,newElement ซึ่งหมายถึง การใส่ข้อมูล newElement ลงในเรียร์ของคิว
การนำสมาชิกออกจากคิว เรียกว่า Dequeue รูปแบบคือ queue,element ซึ่งหมายถึง การนำออกจากส่วนหน้าของคิว และให้ข้อมูลนั้นกับ element
ถ้านำข้อมูลตอนต้นออกจากคิวมาแสดงเรียกว่า Queue Front แต่ไม่มีการเอาข้อมูลออกจากคิว
ส่วนการนำข้อมูลที่อยู่ตอนท้ายของคิวมาแสดง เรียกว่า Queue Rearv แต่ไม่ทำการเพิ่มข้อมูลเข้าไปในคิว

การแทนที่ข้อมูลของคิว ทำได้ 2 วิธีคือ
1.การแทนที่ข้อมูลของคิวแบบลิงค์ลิสต์
2.การแทนที่ข้อมูลของคิวแบบอะเรย์

การแทนที่ข้อมูลของแสตกแบบลิงค์ลิสต์ประกอบด้วย 2 ส่วนคือ
1.Head Node
2.Data Node

การดำเนินการเกี่ยวกับคิว

1. Create Queue จัดสรรหน่วยความจำให้แก่ Head Node และให้ค่า pointer ทั้ง 2 ตัวมีค่าเป็น null และจำนวนสมาชิกจะเป็น 0
2. Enqueue คือ การเพิ่มข้อมูลเข้าไปในคิว
3. Dequeue คือ การนำข้อมูลออกจากคิว
4. Queue Front เป็นการนำข้อมูลที่อยู่ส่วนต้นของคิวมาแสดง
5. Queue Rear เป็นการนำข้อมูลที่อยู่ส่วนท้ายของคิวมาแสดง
6. Empty Queue เป็นการตรวจสอบว่าคิวว่างหรือไม่
7. Full Queue เป็นการตรวจสอบว่าคิวเต็มหรือไม่
8. Queue Count เป็นการนับจำนวนสมาชิกที่อยู่ในคิว

การนำข้อมูลเข้าสู่คิว เราจะไม่สามารถนำข้อมูลเข้าในขณะที่คิวเต็ม หรือไม่มีที่ว่างได้ ถ้าเราพยายาม
นำข้อมูลเข้าจะทำให้เกิดความผิดพลาดที่เรียกว่า overflow
ส่วนการนำข้อมูลออกจากคิว จะไม่สามารถนำออกจากคิวที่ว่างได้ ถ้าพยายาม จะทำให้เกิดความผิดพลาดที่เรียกว่า underflow

ในการนำเข้าข้อมูลในกรณีที่คิวเต็ม แต่สภาพความเป็นจริงแล้ว front ไม่ได้อยู่ในช่องแรกของคิว จะไม่สามารถนำที่ว่างในส่วนหน้ามาใช้ได้อีก

วิธีการแก้ปัญหาดังกล่าว จะใช้คิวที่เป็นแบบคิววงกลม (Circular Queue) ซึ่งคิวช่องสุดท้ายนั้นต่อกับคิวช่องแรกสุด

คิวแบบวงกลมจะเต็มก็ต่อเมื่อมีการเพิ่มข้อมูลเข้าไปในคิวเรื่อย ๆ จนกระทั่ง rear มีค่าน้อยกว่า front อยู่หนึ่งค่าคือ rear = front - 1

การประยุกต์ใช้คิว
คิวจะถูกประยุกต์ใช้มากในการจำลองระบบงาน
ธุรกิจ เช่น การให้บริการลูกค้า ต้องวิเคราะห์จำนวนลูกค้าในคิวที่เหมาะสม ว่าควรเป็นจำนวนเท่าใด เพื่อให้ลูกค้าเสียเวลาน้อยที่สุด ในด้านคอมพิวเตอร์ ได้นำคิวเข้ามาใช้ คือ ในระบบปฏิบัติการ (Operation System) ในเรื่องของคิวของงานที่เข้ามาทำงาน (ขอใช้ทรัพยากระบบของ CPU) จะจัดให้งานที่เข้ามาได้ทำงานตามลำดับความสำคัญ


DTS 07-05-08-2552

สรุปการเรียน Lecture 5 เรื่อง Stack

สแตก (Stack) เป็นโครงสร้างข้อมูลที่ข้อมูลแบบลิเนียร์ลิสต์ ที่มีคุณสมบัติที่ว่า การเพิ่มหรือลบข้อมูล
ในสแตก จะกระทำที่ ปลายข้างเดียวกัน ซึ่งเรียกว่า Top ของสแตก (TopOf Stack) และ ลักษณะที่สำคัญของสแตกคือ ข้อมูลที่ใส่หลังสุดจะถูกนำออกมา จากสแตกเป็นลำดับแรกสุด เรียกคุณสมบัตินี้ว่า
LIFO (Last In First Out)
การทำงานของสแตกจะกระทำที่ปลายข้างหนึ่งของ สแตกเท่านั้น การทำงานของสแตกจะประกอบด้วย
กระบวนการ 3 กระบวนการที่สำคัญ คือ
1.Push คือ การนำข้อมูลใส่ลงไปในสแตก
2. Pop คือ การนำข้อมูลออกจากส่วนบนสุดของสแตก
3. Stack Top เป็นการคัดลอกข้อมูลที่อยู่บนสุดของสแตก แต่ไม่ได้นำเอาข้อมูลนั้นออกจากสแตก

การแทนที่ข้อมูลของสแตกสามารถทำได้ 2 วิธี คือ
1. การแทนที่ข้อมูลของสแตกแบบลิงค์ลิสต์
2. การแทนที่ข้อมูลของสแตกแบบอะเรย์

การดำเนินการเกี่ยวกับสแตก
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 เป็นการนับจำนวนสมาชิกในสแตก

การประยุกต์ใช้สแตก
จะใช้ในงานด้านปฏิบัติการของเครื่องคอมพิวเตอร์ที่ขั้นตอนการทำงานต้องการเก็บข่าวสารอันดับแรกสุดไว้ใช้หลังสุด เช่น การทำงานของโปรแกรมแปลภาษานำไปใช้ในเรื่องของการเรียกใช้โปรแกรมย่อย การคำนวณนิพจน์ทางคณิตศาสตร์ และรีเคอร์ชั่น (Recursion)
การทำงานของโปรแกรมหลักที่เรียกใช้โปรแกรมย่อยและในแต่ละโปรแกรมย่อยก็มีการเรียกใช้โปรแกรมย่อย
ต่อไปอีก สแตกจะสามารถเข้ามาช่วยในการทำงาน คือแต่ละจุดของโปรแกรมที่เรียกใช้โปรแกรมย่อยจะเก็บ
เลขที่ของคำสั่งถัดไปที่เครื่องต้องกลับมาทำงานไว้ในสแตก หลังจากเสร็จสิ้นการทำงานในโปรแกรมย่อยแล้วจะทำการ pop ค่าเลขที่คำสั่งออกมาจากสแตก เพื่อกลับไปทำงานที่คำสั่งต่อจากคำสั่งที่เรียกใช้โปรแกรมย่อย

การคำนวณนิพจน์ทางคณิตศาสตร์ในการเขียนนิพจน์ทางคณิตศาสตร์เพื่อการคำนวณ จะต้องคำนึงถึงลำดับความสำคัญของเครื่องหมายสำหรับการคำนวณด้วยโดยทั่วไปนิพจน์ทางคณิตศาสตร์ สามารถเขียนได้ 3 รูปแบบ คือ
1. นิพจน์ Infix นิพจน์รูปแบบนี้ operatorจะอยู่ตรงกลางระหว่างตัวถูกดำเนินการ 2 ตัว
2. นิพจน์ Postfix นิพจน์รูปแบบนี้ จะต้องเขียนตัวถูกดำเนินการตัวที่ 1 และ 2 ก่อน แล้วตามด้วย operator
3. นิพจน์ Prefix นิพจน์รูปแบบนี้ จะต้องเขียน operatorก่อนแล้วตามด้วยตัวถูกดำเนินการตัวที่ 1 และ 2

ขั้นตอนการแปลงจากนิพจน์ Infix เป็นนิพจน์ Postfix
1. อ่านอักขระในนิพจน์ Infix เข้ามาทีละตัว
2. ถ้าเป็นตัวถูกดำเนินการจะถูกย้ายไปเป็นตัวอักษรในนิพจน์ Postfix
3. ถ้าเป็นตัวดำเนินการ จะนำค่าลำดับความสำคัญของตัว ดำเนินการที่อ่านเข้ามาเทียบกับ
ค่าลำดับความสำคัญของตัวดำเนินการที่อยู่บนสุดของสแตก
- ถ้ามีความสำคัญมากกว่า จะถูก push ลงในสแตก
- ถ้ามีความสำคัญน้อยกว่าหรือเท่ากัน จะต้อง pop ตัวดำเนินการที่อยู่ในสแตกขณะนั้นไปเรียงต่อกับตัวอักษรในนิพจน์ Postfix
4. ตัวดำเนินการที่เป็นวงเล็บปิด “)” จะไม่ push ลงในสแตกแต่มีผลให้ตัวดำเนินการอื่น ๆ ถูก pop ออกจากสแตกนำไป เรียงต่อกันในนิพจน์ Postfix จนกว่าจะเจอ “(” จะ pop วงเล็บเปิดออกจากสแตกแต่ไม่นำไปเรียงต่อ
5. เมื่อทำการอ่านตัวอักษรในนิพจน์ Infixหมดแล้ว ให้ทำการ Pop ตัวดำเนินการทุกตัวในสแตกนำมาเรียงต่อในนิพจน์Postfix

ในการคำนวณค่า Postfix ที่แปลงมาแล้ว ตัวแปลภาษาจะทำการคำนวณโดยใช้โครงสร้างสแตก
ช่วยอีกเช่นกัน ขั้นตอนในการคำนวณ
1. อ่านตัวอักษรในนิพจน์ Postfix จากซานไปขวาทีละตัวอักษร
2. ถ้าเป็นตัวถูกดำเนินการ ให้ทำการ push ตัวถูกดำเนินการนั้นลงในสแตก แล้วกลับไปอ่านอักษรตัว
ใหม่เข้ามา
3. ถ้าเป็นตัวดำเนินการ ให้ทำการ pop ค่าจากสแตก 2 ค่าโดย ตัวแรกเป็นตัวถูกดำเนินการตัวที่ 2 และ
ตัวที่ 1 ตามลำดับ
4. ทำการคำนวณ ตัวถูกดำเนินการตัวที่ 1ด้วยตัวถูก ดำเนินการตัวที่ 2 โดยใช้ตัวดำเนินการในข้อ 3
5. ทำการ push ผลลัพธ์ที่ได้จากการคำนวณในข้อ 4 ลงสแตก
6. ถ้าตัวอักษรในนิพจน์ Postfix ยังอ่านไม่หมดให้กลับไปทำข้อ 1 ใหม่


DTS 06-29-07-2552