Evaluate Reverse Polish Notation - คำนวณนิพจน์ Postfix ใน C++

ภาพรวมปัญหา

คำนวณค่าของนิพจน์ Reverse Polish Notation (Postfix) โดยใช้ Stack

ตัวอย่าง: "53+62/*35*+" → 39

อัลกอริทึม

1. อ่านตัวอักษรทีละตัว:
   • ถ้าเป็นตัวเลข (operand) → push เข้า stack
   • ถ้าเป็นตัวดำเนินการ (operator) → pop 2 ตัว (a, b), คำนวณ b ☉ a, push ผลลัพธ์
2. คำตอบอยู่ที่ top ของ stack

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

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

float scanNum(char ch){ return float(ch - '0'); }
int isOperator(char ch){ return (ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='^') ? 1 : -1; }
int isOperand(char ch){ return (ch>='0' && ch<='9') ? 1 : -1; }

float operation(int a, int b, char op){
    if(op=='+') return b+a;
    else if(op=='-') return b-a;
    else if(op=='*') return b*a;
    else if(op=='/') return b/a;
    else if(op=='^') return pow(b,a);
    else return INT_MIN;
}

float postfixEval(string postfix){
    int a, b;
    stack<float> stk;
    for(auto it = postfix.begin(); it != postfix.end(); it++){
        if(isOperator(*it) != -1){
            a = stk.top(); stk.pop();
            b = stk.top(); stk.pop();
            stk.push(operation(a, b, *it));
        } else if(isOperand(*it) > 0){
            stk.push(scanNum(*it));
        }
    }
    return stk.top();
}

int main(){
    string post = "53+62/*35*+";
    cout << "The result is: " << postfixEval(post);
}

Input / Output

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