โครงสร้างข้อมูล - การแยกนิพจน์
วิธีการเขียนนิพจน์เลขคณิตเรียกว่า 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 โปรดคลิกที่นี่