แปลงนิพจน์ Infix เป็น นิพจน์ Postfix

อันกอริทึมในการแปลงนิพจน์               อินฟิกซ์ เป็น โพสต์ฟิกซ์

การแปลงนิพจน์ infix เป็น posfix

-          นิพจน์ infix เป็นนิพจน์ที่เครื่องหมายคณิตศาสตร์ (operator) อยู่ระหว่างสัญลักษณ์แทนตัวเลข (operand) เช่น A+B

-          นิพจน์ postfix เป็นนิพจน์ที่เครื่องหมายคณิตศาสตร์ (operator) อยู่หลังสัญลักษณ์หทนตัวเลข (operand) เช่น AB+

-          นิพจน์ postfix บางครั้งเรียนกว่า polish string, reverse polish string

-          ตัวอย่างในการแปลงนิพจน์

A + B – C               เท่ากับ     (A + B) – C แปลงเป็น                           AB+C-

A * B * C                เท่ากับ (A * B) * C  แปลงเป็น                               AB*C*

A * B / Cเท่ากับ (A * B) / C   แปลงเป็น               AB*C/

A / B * Cเท่ากับ (A / B) * C   แปลงเป็น                               AB/C*

 

การประยุกต์ใช้งานของ Stack (ต่อ)

-          นิพจน์ที่เป็น infix เมื่อแปลงเป็นนิพจน์ postfix แล้วจะไม่มีวงเล็บแล้ว

-          กลไกในการแปลนิพจน์ infix เป็นนิพจน์ postfix ต้องใช้โครงสร้างข้อมูลแบบ stack ช่วย โดยต้องนิยามลำดับของเครื่องหมายคณิตศาสตร์ก่อน

เครื่องหมาย

ค่าเมื่ออยู่ในสแตก

ค่าเมื่ออยู่ในอินพุต

^

3

4

*,/

2

2

+,-

1

1

(

0

4

 

อันกอริทึมในการแปลง infix เป็น postfix

1.        อ่านค่าอินพุตถ้าเป็น operand ให้นำไปไว้ที่เอาต์พุต

2.        อ่านค่าอินพุตถ้าเป็น operand ให้ทำดังนี้

2.1     นำ operand ลงสู่สแตกถ้าสแตกว่าง (เรียกสแตกที่เก็บนี้ว่า operand stack เรียกย่อว่า opst)

2.2      ถ้า opst ไม่ว่างให้เปรียบเทียบค่าของ operator ที่อินพุตกับ operator ในสแตกโดยเทียบค่าในตาราง

-          ถ้าค่าของ operator ที่เป็นอินพุตมีค่าน้อยกว่าหรือเท่ากับ ค่าของ operator ที่อยู่ส่วนบนสุดของสแตกก็ให้ pop stack ออกสู่เอาต์พุตจนกว่าค่าของ operator ที่เป็นอินพุตมีค่ามากกว่า ค่าของ operator ที่อยู่ส่วนบนสุดของสกตแหรือจนกว่าสแตกว่าง แล้ว push operator ที่เป็นอินพุต ลงในสแตก

-          ถ้าค่าของ operator ที่เป็นอินพุตมีค่ามากกว่าค่าของ operator ที่อยู่ส่วนบนสุดของสแตกก็ให้ push operator ลงสแตก

 

3.        อ่านค่าอินพุตถ้าเป็นเครื่องหมายวงเล็บเปิด ‘(’ ก็ให้ทำการ pop สแตก 

4.        อ่านค่าอินพุตถ้าเป็นเครื่องหมายวงเล็บเปิด ‘)’ ก็ให้ทำการ pop สแตกออกสู่เอาต์พุตจนกว่าจะ pop สแตกเจอเครื่องหมายวงเล็บเปิดใหม่แล้วทิ้งเครื่องหมายวงเล็บปิด และเปิดคู่เตอมโดยไม่ต้องแสดงเครื่องหมายวงเล็บปิดและเปิดในเอาต์พุต

5.        ถ้าอ่านค่าอินพุตหมดแล้วให้ตรวจในสแตกว่าว่างหรือไม่ถ้าไม่ว่างให้ pop สแตกออกมาสู่เอาต์พุตจนสแตกว่าง

 

ตัวอย่าง จงแปลง A+B/C*D-E เป็นนิพจน์ postfix

 

 

Image Hosting

จงแปลง A+B* (C^D*E/F)-G เป็นนิพจน์ postfix

Image Hosting

จงแปลง A^2-4*(A*C+(E+(F-G)-H)) เป็นนิพจน์ postfix.

Image Hosting