โครงสร้างข้อมูล - การแยกนิพจน์

วิธีการเขียนนิพจน์เลขคณิตเรียกว่า a notation. นิพจน์ทางคณิตศาสตร์สามารถเขียนได้ในสามรูปแบบที่แตกต่างกัน แต่เทียบเท่ากันกล่าวคือโดยไม่ต้องเปลี่ยนสาระสำคัญหรือผลลัพธ์ของนิพจน์ สัญกรณ์เหล่านี้คือ -

• Infix สัญกรณ์
• คำนำหน้า (โปแลนด์) สัญกรณ์
• สัญกรณ์ Postfix (Reverse-Polish)

สัญกรณ์เหล่านี้ถูกตั้งชื่อตามวิธีใช้ตัวดำเนินการในนิพจน์ เราจะเรียนรู้สิ่งเดียวกันที่นี่ในบทนี้

Infix สัญกรณ์

เราเขียนนิพจน์ใน infix สัญกรณ์เช่น a - b + c ที่ใช้ตัวดำเนินการ in- ระหว่างตัวถูกดำเนินการ เป็นเรื่องง่ายที่มนุษย์เราจะอ่านเขียนและพูดในสัญกรณ์ infix ได้ แต่สิ่งเดียวกันนี้ไม่สามารถใช้ได้ดีกับอุปกรณ์คอมพิวเตอร์ อัลกอริทึมในการประมวลผลสัญกรณ์ infix อาจเป็นเรื่องยากและมีค่าใช้จ่ายสูงในแง่ของการใช้เวลาและพื้นที่

สัญกรณ์นำหน้า

ในสัญกรณ์นี้ตัวดำเนินการคือ prefixed ไปยังตัวถูกดำเนินการกล่าวคือตัวดำเนินการถูกเขียนไว้ข้างหน้าตัวถูกดำเนินการ ตัวอย่างเช่น,+ab. สิ่งนี้เทียบเท่ากับสัญกรณ์ infixa + b. สัญกรณ์นำหน้าเรียกอีกอย่างว่าPolish Notation.

สัญกรณ์ Postfix

รูปแบบสัญกรณ์นี้เรียกว่า Reversed Polish Notation. ในรูปแบบสัญกรณ์นี้ตัวดำเนินการคือpostfixed ไปยังตัวถูกดำเนินการคือตัวดำเนินการถูกเขียนไว้หลังตัวถูกดำเนินการ ตัวอย่างเช่น,ab+. สิ่งนี้เทียบเท่ากับสัญกรณ์ infixa + b.

ตารางต่อไปนี้พยายามแสดงความแตกต่างของสัญกรณ์ทั้งสามโดยย่อ -

ซีเนียร์	Infix สัญกรณ์	สัญกรณ์นำหน้า	สัญกรณ์ Postfix
1	a + b	+ ab	ab +
2	(a + b) ∗ c	∗ + abc	ab + c ∗
3	ก ∗ (b + c)	∗ a + bc	abc + ∗
4	a / b + c / d	+ / ab / cd	ab / cd / +
5	(a + b) ∗ (c + d)	∗ + ab + cd	ab + cd + ∗
6	((a + b) ∗ c) - ง	- ∗ + abcd	ab + c ∗ d -

การแยกนิพจน์

ดังที่เราได้กล่าวไปแล้วมันไม่ใช่วิธีที่มีประสิทธิภาพมากในการออกแบบอัลกอริทึมหรือโปรแกรมเพื่อแยกวิเคราะห์สัญกรณ์ infix แต่ระบบจะแปลงสัญกรณ์ infix เหล่านี้เป็น postfix หรือ prefix ก่อนแล้วจึงคำนวณ

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

ลำดับความสำคัญ

เมื่อตัวถูกดำเนินการอยู่ระหว่างตัวดำเนินการสองตัวที่แตกต่างกันซึ่งตัวดำเนินการใดจะใช้ตัวถูกดำเนินการก่อนจะถูกตัดสินโดยลำดับความสำคัญของตัวดำเนินการมากกว่าตัวอื่น ตัวอย่างเช่น -

เนื่องจากการดำเนินการคูณมีความสำคัญเหนือกว่าการบวก b * c จะได้รับการประเมินก่อน มีการจัดเตรียมตารางลำดับความสำคัญของตัวดำเนินการในภายหลัง

ความสัมพันธ์

Associativity อธิบายกฎที่ตัวดำเนินการที่มีลำดับความสำคัญเดียวกันปรากฏในนิพจน์ ตัวอย่างเช่นในนิพจน์ a + b - c ทั้ง + และ - มีลำดับความสำคัญเหมือนกันดังนั้นส่วนใดของนิพจน์จะได้รับการประเมินก่อนจะถูกกำหนดโดยการเชื่อมโยงของตัวดำเนินการเหล่านั้น ที่นี่ทั้ง + และ - จะเหลือเพียงการเชื่อมโยงดังนั้นนิพจน์จะได้รับการประเมินเป็น(a + b) − c.

ลำดับความสำคัญและการเชื่อมโยงกำหนดลำดับของการประเมินนิพจน์ ต่อไปนี้เป็นลำดับความสำคัญของตัวดำเนินการและตารางการเชื่อมโยง (สูงสุดไปต่ำสุด) -

ซีเนียร์	ตัวดำเนินการ	ลำดับความสำคัญ	ความสัมพันธ์
1	เลขชี้กำลัง ^	สูงสุด	Associative ขวา
2	การคูณ (∗) & หาร (/)	สูงสุดเป็นอันดับสอง	Associative ซ้าย
3	การบวก (+) และการลบ (-)	ต่ำสุด	Associative ซ้าย

ตารางด้านบนแสดงพฤติกรรมเริ่มต้นของตัวดำเนินการ ในช่วงเวลาใดก็ได้ในการประเมินนิพจน์ลำดับสามารถเปลี่ยนแปลงได้โดยใช้วงเล็บ ตัวอย่างเช่น -

ใน a + b*cส่วนการแสดงออก b*cจะได้รับการประเมินก่อนโดยมีการคูณเป็นลำดับความสำคัญมากกว่าการบวก เราใช้วงเล็บสำหรับa + b ที่จะประเมินก่อนเช่น (a + b)*c.

Postfix Evaluation Algorithm

ตอนนี้เราจะมาดูอัลกอริทึมเกี่ยวกับวิธีประเมินสัญกรณ์ postfix -

Step 1 − scan the expression from left to right 
Step 2 − if it is an operand push it to stack 
Step 3 − if it is an operator pull operand from stack and perform operation 
Step 4 − store the output of step 3, back to stack 
Step 5 − scan the expression until all operands are consumed 
Step 6 − pop the stack and perform operation

หากต้องการดูการดำเนินงานในการเขียนโปรแกรมภาษา C โปรดคลิกที่นี่