Google         youtube            psv            สพม.11

การใช้สแตกแก้ปัญหาการแปลงนิพจน์คณิตศาสตร์

คอมไพเลอร์จะ แปลงคำสั่งจากภาษาระดับสูง  (High-level  Language)  ไปเป็นภาษาเครื่อง (Machine Language) ส่วนหนึ่งที่ต้องแปลงคือนิพจน์คณิตศาสตร์ เช่น X = A * B + C ซึ่งมีลักษณะที่เรียกว่า  Infix  Notation  มีเครื่องหมายคำนวณอยู่ระ หว่างโอเปอแร้น (Operand) โดยแปลงไปเป็นนิพจน์แบบPostfix  Notation มี เครื่องหมายคำนวณนำหน้าโอเปอแร้น แต่เนื่องจากนิพจน์แบบ Infix มีการนำเครื่องหมายวงเล็บเข้ามาใช้ทำให้ทิศทาง การคำนวณเปลี่ยนไป   ดังในตารางที่ 4.4 เป็นตัวอย่างของการคำนวณแบบเดียวกัน

ตารางที่ 4.4  ลักษณะนิพจน์แบบ Infix, Postfix, และ Prefix Notation

Infix

Postfix

Prefix

A+(B*C)

(A+B)*C

A+B-C

(A+B)*(C-D)

(A+B)*C-(D-E) ) $ (F+G)ABC*+

AB+C*

AB+C-

AB+CD-*

AB+C*DE—FG+$+A*BC

*+ABC

-+ABC

*+AB-CD

$-*+ABC-DE+FG

การแปลงนิพจน์แบบ Infix เป็นแบบ  Postfix

เมื่อ พิจารณาการแปลงนิพจน์แบบ Infix เป็นแบบ Postfix เป็นขั้นตอนการแปลงโดยเริ่ม ต้นจากสแกนนิพจน์Infix ทีละตัว  หากพบวงเล็บก็จะทำส่วนที่อยู่ในวงเล็บให้ เสร็จก่อนเป็นนิพจน์ย่อย (Subexpression) ซึ่งจะได้เป็นอัลกอริทึมดังใน ตารางที่ 4.5

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

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

a.       รับค่า  (Token) ตัวถัดไปในนิพจน์  Infix (ประกอบด้วย ค่าคงที่ ตัวแปร เครื่องหมายคำนวณ วงเล็บเปิดและปิด

b.       ค่าที่รับเข้ามา ถ้าเป็น

b.1  โอเปอแร้น (ค่าคงที่,ตัวแปร)                                  นำไปแสดงทางจอภาพ

b.2  วงเล็บเปิด                                                               ให้นำใส่ลงในสแตก (Push)

b.3  วง เล็บ ปิด                                                                 ดึง ค่าออกจากสแตก (Pop) และนำไปแสดงทาง                      จอภาพ  ทำจนกว่า จะพบวงเล็บเปิด

b.4  เครื่องหมาย คำนวณ                                                 ถ้าสแตกว่าง  หรือ ค่าที่รับมามี Precedence สูงกว่าค่าบนสแตกให้นำใส่ลงในสแตก (Push) ถ้าหาก ค่าที่รับมามี Precedence น้อยกว่าค่าบนสแตกให้ดึงค่าออกจากสแตก (Pop)

3.  เมื่อทำจนค่าในนิพจน์ Infix หมด ให้ดึงค่าออกจากสแตก (Pop) แสดงทางจอภาพตามลำดับ จนกว่าสแตกว่าง

จาก อัลกอริทึมดังกล่าวเมื่อนำมาใช้กับตัวอย่างนิพจน์ 7*8-(2+3) จะได้เป็นลำดับขั้นตอนดังในรูปที่ 4.4 หรือเขียนเป็นแบบตารางได้ดังในตารางที่ 4.6

ตารางที่ 4.6 การแปลงนิพจน์ 7*8-(2+3) เป็นนิพจน์ Postfix

นิพจน์ Infix

สแตก

นิพจน์ Postfix

7*8-(2+3)

*8-(2+3)

8-(2+3)

-(2+3)

(2+3)

2+3)

+3)

3)

)

*

– (

–         ( +

-7

7 8

7 8 *

7 8 *2

7 8 *2 3

/ 8 *2 3 +

7 8 * 2 3 + –

การหาค่าคำตอบจากการคำนวณนิพจน์ Postfix

จาก การแปลงนิพจน์แบบ Infix เป็นแบบ Postfix ทำให้นิพจน์ที่ได้ไม่มีเครื่อง หมายวงเล็บ  ต่อจากนั้นจะทำการหาค่าคำตอบโดยสแกนนิพจน์ Postfix ทีละตัวจาก ซ้ายไปขวา เมื่อใดที่พบโอเปอแร้นก็นำเก็บลงในสแตก  สุดท้ายคำตอบที่ได้จะอยู่ในสแตก เพียงค่าเดียวซึ่งจะได้เป็นอัลกอริทึมดังในตารางที่ 4.7

ตารางที่ 4.7  อัลกอริทึมการหาค่าคำตอบจากนิพจน์ Postfix

1.     สร้างสแตกที่ว่างเปล่ายังไม่มีการเก็บค่า

2.     ทำงานต่อไปนี้ซ้ำจนกว่าถึงจุดสิ้นสุดของนิพจน์

a.          รับค่า (Token) ตัวถัดไปในนิพจน์ RPN (ประกอยด้วย  ค่าคงที่  ตัวแปร  เครื่องหมายคำนวณ)

b.         ค่าที่รับเข้ามา  ถ้าเป็นโอเปอแร้น ให้นำใส่ลงในสแตก (Push) แต่ถ้าเป็นเครื่องหมายคำนวณให้ทำดังนี้

b.1  ดึงค่าออกจากสแตก (Pop) สองค่า ถ้าไม่ครบให้แจ้งเกิดข้อผิดพลาด

b.2  นำเครื่องหมายคำนวณทำการประมวลผลกับค่าทั้งสอง

b.3  นำผลลัพธ์ที่ได้ใส่กลับลงในสแตก (Push)

3.  เมื่อถึงจุดสิ้นสุดของนิพจน์ ค่าที่เป็นคำตอบจะอยู่บนสแตก ซึ่งมีเพียงค่าเดียวเท่านั้น

จาก อัลกอริทึมดังกล่างเมื่อนำมาใช้กับตัวอย่างนิพจน์ 2 4 *9 5 + -จะเป็นตามลำดับขั้นตอนดังในรูปที่ 4.5 หรือเขียนเป็ฯแบบตารางได้ดังในตารางที่ 4.8

ตารางที่ 4.8 การหาค่าคำตอบจากนิพจน์

นิพจน์ Postfix

ค่าที่ได้

สแตก

2 4 * 9 5 + –

4 + 9 5 + –

* 9 5 + –

9 5 + –

5 + –

+ –

2 * 4 = 8

9 + 5 = 14

8 – 14 = -62

2 4

8

8 9

8 9 5

8 14

-6

-6

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s