Đánh Giá Biểu Thức Hậu Tố (Evaluate Postfix Expression)

Giới thiệu

Biểu thức hậu tố (postfix) đặt toán tử sau toán hạng. Sử dụng ngăn xếp để đánh giá: gặp toán hạng thì push, gặp toán tử thì pop hai toán hạng, thực hiện phép toán, push kết quả.

Đầu vào và Đầu ra

Đầu vào: Biểu thức hậu tố "53+62/*35*+"
Đầu ra: Kết quả = 39.

Thuật toán

postfixEvaluation(postfix)
Begin
    for mỗi ký tự ch trong postfix do
        nếu ch là toán tử thì
            a := pop(); b := pop()
            res := b ⨀ a
            push(res)
        else nếu ch là toán hạng thì
            push(ch)
        done
    return top của stack
End

Ví dụ C++

#include <iostream>
#include <cmath>
#include <stack>
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);
    return INT_MIN;
}

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

int main() {
    string post = "53+62/*35*+";
    cout << "Kết quả: " << postfixEval(post);
    return 0;
}

Kết quả

Kết quả: 39