โปรแกรมคำนวณนิพจน์ Postfix (Reverse Polish Notation) ใน C++

ภาพรวมปัญหา

ให้นิพจน์ Postfix (ตัวดำเนินการอยู่หลังตัวถูกดำเนินการ) ต้องการคำนวณค่า เช่น "21+3*" = (2+1)×3 = 9

หลักการทำงาน (Stack-based)

1. อ่านตัวอักษรทีละตัวจากซ้ายไปขวา
2. ถ้าเป็นตัวเลข (operand) → push เข้า stack
3. ถ้าเป็นตัวดำเนินการ (operator) → pop 2 ตัว (a=top, b=next), คำนวณ b op a, push ผลลัพธ์
4. จบการอ่าน → ค่าที่เหลือใน stack คือคำตอบ

ตัวอย่าง

Input: "21+3*"

ขั้นตอน:

• Push 2, Push 1
• See '+': pop 1, pop 2 → 2+1=3, push 3
• Push 3
• See '*': pop 3, pop 3 → 3×3=9, push 9
• Result: 9

โค้ดตัวอย่าง

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

float scanNum(char ch) {
    return float(ch - '0');
}

int isOperator(char ch) {
    return (ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^');
}

int isOperand(char ch) {
    return (ch >= '0' && ch <= '9');
}

float operation(float a, float b, char op) {
    switch (op) {
        case '+': return b + a;
        case '-': return b - a;
        case '*': return b * a;
        case '/': return b / a;
        case '^': return pow(b, a);
        default: return INT_MIN;
    }
}

float postfixEval(string postfix) {
    stack stk;
    for (char ch : postfix) {
        if (isOperator(ch)) {
            float a = stk.top(); stk.pop();
            float b = stk.top(); stk.pop();
            stk.push(operation(a, b, ch));
        } else if (isOperand(ch)) {
            stk.push(scanNum(ch));
        }
    }
    return stk.top();
}

int main() {
    string post = "21+3*";
    cout << postfixEval(post);
    return 0;
}

ผลลัพธ์

9

ขยายความสามารถ

• รองรับตัวเลขหลายหลัก: ใช้ space หรือ comma คั่น แล้ว parse ด้วย stringstream
• รองรับตัวแปร: ใช้ map เก็บค่าตัวแปร
• รองรับฟังก์ชัน: sin, cos, log ฯลฯ

โค้ดรองรับหลายหลัก (Sketch)

float postfixEval_multi(string postfix) {
    stack stk;
    stringstream ss(postfix);
    string token;
    while (ss >> token) {
        if (isdigit(token[0]) || (token[0]=='-' && token.size()>1)) {
            stk.push(stof(token));
        } else if (token.size() == 1 && isOperator(token[0])) {
            float a = stk.top(); stk.pop();
            float b = stk.top(); stk.pop();
            stk.push(operation(a, b, token[0]));
        }
    }
    return stk.top();
}

ความซับซ้อน

• เวลา: O(N) — N = ความยาวนิพจน์
• พื้นที่: O(N) — stack สูงสุด N/2

การประยุกต์ใช้

Compiler design, Expression evaluation, Calculator apps, Forth/PostScript languages