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

โดยปกติเวลาเราอ่านเขียนสัญลักษณ์ทางคณิตศาสตร์

เรามักจะใช้  operator เชื่อมระหว่าง operand สองตัว ดังนี้

operand1  operator  operand2

เช่น

1 + 2

เราเรียกรูปแบบการเขียนสัญลักษณ์แบบนี้ว่า infix notation  (ให้operator อยู่ด้านใน )

ยังมีรูปแบบการเขียนสัญลักษณ์ทางคณิตศาสตร์อีกแบบที่เรียกว่า postfix notation (ให้ operator แสดงด้านหลัง) โดยเราสามารถเขียน 1+2 เป็น postfix ได้ ดังนี้

12+

ถ้ามี operand เพียง 2 ตัวกับ operator เพียงหนึ่ง ก็คงเปรียบเสมือน ชายกับหญิง ที่ต่างรักเดียวใจเดียว จะเขียนแบบ infix หรือ postfix ก็คงเข้าใจไม่ยาก แต่ชีวิตจริงมันยิ่งกว่านิยาย การเขียนสมการคณิตศาสตร์ มันซับซ้อน มีตัวละครหลายตัว มีตัวอิจฉาบ้าง ผู้ช่วยพระเอกนางเอกบ้าง ตัวตลก พ่อผู้ร้าย .. เยอะแยะเต็มไปหมด ลองดูสัญลักษณ์  postfix ดังต่อไปนี้ ท่านผู้อ่านคิดว่า มันมาจากสัญลักษณ์ infix ว่าอย่างไร

AB*C/HE*+D-

งงล่ะสิครับ ถ้าผมบอกว่ามันมาจากสัญลักษณ์ infix ตัวนี้

(((A*B)/C)+(H*E))-D

ท่านผู้อ่านคงจะปวดหัวเหมือนผมใช่ไหมล่ะครับ ว่ามันมีที่มายังไง ในที่นี้ผมมีอัลกอริทึมที่จะช่วยท่านได้อย่างแน่นอน

วิธีการแปลง postfix ให้เป็น infix นั้นง่ายนิดเดียวถ้าทำความเข้าใจอัลกอริทึ่มต่อไปนี้ (ท่านผู้อ่านต้องมีความรู้เรื่อง stack มาก่อนนะครับ)


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

อ่านสายอักขระของ postfix ทีละตัว จนกว่าจะสิ้นสุดโดยอักขระแต่ละตัวที่อ่านออกมาได้นั้นให้ดำเนินการดังนี้

1.ถ้าเจอ operand ให้ push ลง stack

2.ถ้าเจอ operator ให้ pop ค่าที่อยู่ใน stack สองตัวบน ออกมาแล้ว แทรก operator ระหว่างค่าทั้งสองเป็นสายอักขระใหม่

2.1 ถ้าสิ้นสุดสายอักขระที่อ่านแล้วให้ push สายอักขระตัวใหม่ลงไปใน stack

2.2 ถ้าไม่สิ้นสุดสายอักขระเริ่มให้ใส่วงเล็บครอบสายอักขระตัวใหม่นั้น แล้ว push สายอักขระดังกล่าวลงไปใน stack

เมื่อสิ้นสุดการอ่านสายอักขระทั้งหมดแล้วให้ค่าที่อยู่ตำแหน่งบนสุดของ stack คือสายอักขระ infix
ตัวอย่างที่ 1
(อธิบายแบบละเอียด)

AB+C-

1. อ่าน A เป็น Operand ให้ push ลง Stack

{ A  }
2. อ่าน B เป็น Operand ให้ push ลง Stack
{A,B}
3. อ่าน + เป็น Operator ให้ pop ค่า A กับ B ออกมาแล้วแทรก เครื่องหมาย + ลงไประหว่าง A กับ B ได้เป็น  A+B

{   }

3.1 ไม่สิ้นสุดสายอักขระใส่วงเล็บครอบ A+B แล้ว push ลงไปใน stack

{ (A+B) }

4.อ่าน C เป็น Operand ให้ push ลงใน Stack

{ (A+B), C }
5. อ่าน – เป็น Operator ให้ pop ค่า  (A+B) กับ C ออกมาแล้วแทรกเครื่องหมาย – ลงไป ได้เป็น  (A+B)-C
{      }

5.1 สิ้นสุดสายอักขระ push ค่า (A+B)-C ลงไปใน stack

{ (A+B)-C }

คำตอบค่า infix ที่ได้คือค่าที่อยู่ใน stack

(A+B)-C

ตัวอย่างที่ 2
(อธิบายด้วยการสร้างรูปลำดับการสร้าง stack)
AB*C/HE*+D-

1.  A  -> { A }
2.  B -> { A, B }
3.  * -> { (A*B) }
4.  C -> { (A*B), C }
5.  /  -> { ((A*B)/C ) }
6.  H -> { ((A*B)/C), H }
7. E   ->  { ((A*B)/C), H, E }
8.  *  ->   { ((A*B)/C), (H*E) }
9.  +  -> { (((A*B)/C)+(H*E)) }
10. D -> { (((A*B)/C)+(H*E)) , D }
11.  –   ->{ (((A*B)/C)+(H*E)) – D }

คำตอบคือ

(((A*B)/C)+(H*E))-D

เห็นไหมล่ะครับว่ามันง่ายแสนง่ายสักเพียงใด ถ้าท่านผู้อ่านเข้าใจอัลกอริทึมตามที่ผมนำเสนอมานี้ รับรองว่าท่านจะสามารถแปลง postfix เป็น infix ได้อย่างแน่นอน เปรียบเสมือนละครไทยถึงจะเนื้อเรื่องจะดำเนินไปหวือหวาอย่างไร สุดท้ายพระเอกกับนางเองจะมากอดกันอยู่บนท้องทุ่งแล้วพูดว่า  “ผมรักคุณครับ”   -> “ค่ะ ดิฉันก็รักคุณ”  นั่นแหละครับ อิอิ

Advertisements

One thought on “อัลกอริทึมการแปลง postfix เป็น infix

Add yours

ใส่ความเห็น

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 / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s

Up ↑

%d bloggers like this: