Evaluate Postfix Expression (คำนวณนิพจน์ Postfix)

Postfix Expression (Reverse Polish Notation) คือรูปแบบนิพจน์ที่ตัวดำเนินการ (operator) อยู่ **หลัง** โอเปอรันด์ (operand) ทำให้คอมพิวเตอร์คำนวณได้ง่ายโดยใช้ Stack

ตัวอย่าง Input และ Output

Input: Postfix expression: "53+62/*35*+"
Output: The result is: 39

ขั้นตอน:
5 3 + → 8
6 2 / → 3
8 3 * → 24
3 5 * → 15
24 15 + → 39

อัลกอริทึม Stack-based Evaluation

ฟังก์ชัน postfixEvaluation(postfix)

ขั้นตอน:

1. สร้าง Stack ว่าง
2. อ่านตัวอักษรทีละตัวจากซ้ายไปขวา:
   • ถ้าเป็น **Operand** (ตัวเลข) → Push เข้า Stack
   • ถ้าเป็น **Operator** (+, -, *, /, ^):
     • Pop 2 ตัว: a = pop() (ตัวแรก), b = pop() (ตัวสอง)
     • คำนวณ res = b ⨀ a (สำคัญ: b ก่อน a)
     • Push res กลับเข้า Stack
3. จบการอ่าน → Top of Stack = คำตอบ

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

#include <iostream>
#include <cmath>
#include <stack>
#include <string>
using namespace std;

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

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

bool 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 = "53+62/*35*+";
    cout << "The result is: " << postfixEval(post);
    return 0;
}

Output

The result is: 39

ความซับซ้อน

• Time: O(n) - อ่านนิพจน์ 1 ครั้ง
• Space: O(n) - Stack (สูงสุด n/2)

การขยาย: รองรับหลายหลักและ Space

ใช้ stringstream หรือ parse ตัวเลขหลายหลัก โดยแยกด้วย space: "5 3 + 6 2 / * 3 5 * +"