สมาชิก
แลกเปลี่ยน

อัลกอริทึมการแปลงนิพจน์ Infix เป็น นิพจน์ Postfix

 แปลงนิพจน์ 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

บันทึกนี้เขียนที่ GotoKnow โดย 

· คำสำคัญ: อัลกอริทึมการแปลงนิพจน์ infix เป็น นิพจน์ postfix 
· หมายเลขบันทึก: 183554 · เขียน:  
· ความเห็น:
10
 · อ่าน: แสดง 
· สัญญาอนุญาต: สงวนสิทธิ์ทุกประการ
 แจ้งลบ
 
 แจ้งลบ
บันทึกก่อนนี้
บันทึกใหม่กว่า
ปลาย
IP: xxx.176.162.170
เขียนเมื่อ Sun Apr 19 2009 00:18:13 GMT+0700 (ICT)

งง สอนคนไม่เปงคอมมั้งจิ เอาง่ายๆๆอะ

toey Bc3
IP: xxx.11.38.69
เขียนเมื่อ Mon Aug 10 2009 12:28:41 GMT+0700 (ICT)

เข้าใจคับ อธิบายพอได้จ้า

ควาย
IP: xxx.158.160.26
เขียนเมื่อ Tue Dec 08 2009 14:01:32 GMT+0700 (ICT)

ไม่เห็นจะเข้าใจ

pangkung
เขียนเมื่อ Wed Feb 17 2010 13:55:50 GMT+0700 (ICT)

อ่านเข้าใจง่ายดีค่ะ

ครูพี่หนึ่ง
IP: xxx.173.33.243
เขียนเมื่อ Mon Mar 01 2010 10:03:44 GMT+0700 (ICT)

สแตก(Stack) คือ ให้เราจินตนาการว่ามันคือปิ่นโต ถ้าเราเอาชั้นของปิ่นโตใส่เข้าไปอันที่ใส่เข้าไปก่อนจะถูกยกมาจากปินโตทีหลัง ซึงการเอาชั้นไปใส่ในปิ่นโตคือ Push กับ Pop

Push คือ การเอาข้อมูลเข้าสู่สแตก

Pop คือ การดึงข้อมูลออกจากสแตก

ในที่นี้ให้ทำการมองสแตกเป็นปิ่นโตและมองตัวอักขระ ABC... และ ตัวกระทำการทางคณิตศาสตร์เป็นชั้นของปิ่นโต

โดยตามหลักการและขั้นตอนของเจ้าของ Blog เลยครับ ก็จะสามารถแปลงจาก Infix เป็น Postfixได้

สแตกเป็นแค่ตัวพักนะครับคล้ายกับวางหนังสือลงในกล่องหยิบหนังสือมาใส่ในกล่องเมื่อตรงตามเงื่อนไขและขั้นตอนก็ทำการหยิบหนังสืออกจากกล่องไปเรียงเป็นผลลัพท์

 

ปล.สำหรับคนที่ไม่เป็นคอมฯนะครับ

จันจิรา
IP: xxx.122.23.90
เขียนเมื่อ Sat Mar 06 2010 17:37:33 GMT+0700 (ICT)

ขอบคุณมาก๐ค่ะ

tkzang
IP: xxx.158.205.32
เขียนเมื่อ Mon Apr 05 2010 16:09:41 GMT+0700 (ICT)

ขอบคุงมากคับ แต่ว่าผมยัง งง??นิดหน่อยแต่มะเปงรัยจะตั้งจัยให้มากกว่านี้ครับ......

ยุทธ
IP: xxx.172.3.127
เขียนเมื่อ Wed Jun 30 2010 15:12:45 GMT+0700 (ICT)

อยากเก่งมั่ง เรื่องการเปลี่ยนนิพจน์ครับ อยากได้เคล็ดลับที่ง่ายๆครับ

นัท
IP: xxx.158.243.34
เขียนเมื่อ Thu Dec 16 2010 20:43:27 GMT+0700 (ICT)

เข้าใจดีครับ แต่ผมทำไม่ได้ อิอิ

 

ดล
เขียนเมื่อ Wed Sep 19 2012 19:46:58 GMT+0700 (ICT)

A+B* (CD*E/F)-G อยากดูขั้นตอนการทำอะคับ แต่รูปไม่ขึ้นอะคับ

อนุญาตให้แสดงความเห็นได้เฉพาะสมาชิก
ไม่อนุญาตให้แสดงความเห็น
{{ kv.current_user.preferred_name }} - เพิ่มความเห็นเพิ่มความเห็น
 ใส่รูปหรือไฟล์