การประเมินนิพจน์คำนำหน้า (Prefix) ใน C++

นิพจน์คำนำหน้า (Prefix Expression) คืออะไร?

ในการเขียนแบบนี้ ตัวดำเนินการจะถูกวาง หน้า ตัวถูกดำเนินการ เช่น +ab ซึ่งเทียบเท่ากับแบบ Infix คือ a + b นิพจน์คำนำหน้ายังเรียกอีกอย่างว่า Polish Notation

ตัวอย่าง

* + 6 9 - 3 1

นิพจน์คำนำหน้าสามารถประเมินค่าได้เร็วกว่านิพจน์แบบ Infix และไม่มีวงเล็บ ทำให้การคำนวณเร็วขึ้น

อัลกอริธึมการประเมินนิพจน์คำนำหน้า

การประเมินต้องใช้โครงสร้างข้อมูล Stack เราจะนำตัวดำเนินการเข้า Stack แล้วคำนวณนิพจน์

ขั้นตอนคือ:

เริ่มจากองค์ประกอบสุดท้ายของนิพจน์
ตรวจสอบองค์ประกอบปัจจุบัน:
- ถ้าเป็นตัวถูกดำเนินการ ให้ Push เข้า Stack
- ถ้าเป็นตัวดำเนินการ ให้ Pop ตัวถูกดำเนินการสองตัวออกจาก Stack ดำเนินการ แล้ว Push ผลลัพธ์กลับเข้า Stack
ทำซ้ำจนครบทุกองค์ประกอบ และส่งคืนค่าบนสุดของ Stack ซึ่งเป็นผลลัพธ์

การทำงานของอัลกอริธึม (ตัวอย่าง * + 6 9 - 3 1)

รอบ	องค์ประกอบ	การดำเนินการ	Stack
1	1	Push	1
2	3	Push	3, 1
3	-	Pop 2 ตัว คำนวณ 3-1=2 Push	2
4	9	Push	9, 2
5	6	Push	6, 9, 2
6	+	Pop 2 ตัว คำนวณ 6+9=15 Push	15, 2
7	*	Pop 2 ตัว คำนวณ 15*2=30 Push	30

สิ้นสุด: ส่งคืนค่าบนสุดของ Stack = 30

โปรแกรมตัวอย่าง

#include <bits/stdc++.h>
using namespace std;

double evaluatePrefix(string prefixExp) {
    stack<double> operandStack;
    int size = prefixExp.size() - 1;
    
    for (int i = size; i >= 0; i--) {
        if (isdigit(prefixExp[i])) {
            operandStack.push(prefixExp[i] - '0');
        } else {
            double o1 = operandStack.top(); operandStack.pop();
            double o2 = operandStack.top(); operandStack.pop();
            
            if (prefixExp[i] == '+') operandStack.push(o1 + o2);
            else if (prefixExp[i] == '-') operandStack.push(o1 - o2);
            else if (prefixExp[i] == '*') operandStack.push(o1 * o2);
            else if (prefixExp[i] == '/') operandStack.push(o1 / o2);
            else {
                cout << "Invalid Expression";
                return -1;
            }
        }
    }
    return operandStack.top();
}

int main() {
    string prefixExp = "*+69-31";
    cout << "The result of evaluation of expression " << prefixExp << " is " << evaluatePrefix(prefixExp);
    return 0;
}

ผลลัพธ์

The result of evaluation of expression *+69-31 is 30