Chương trình tính giá trị biểu thức hậu tố trong C++

Giả sử có biểu thức hậu tố (postfix) và ta phải tính giá trị. Biểu thức hậu tố còn gọi là ký pháp Ba Lan ngược. Ở đây ta dùng cấu trúc dữ liệu stack để giải bài toán hậu tố.

Vì vậy nếu biểu thức là "21+3*", thì kết quả sẽ là 9.

Các bước như sau:

• với mỗi ký tự ch trong biểu thức hậu tố
  • nếu ch là toán tử ⊙, thì
    • a := pop phần tử đầu từ stack
    • b := pop phần tử thứ hai từ stack
    • res := b ⊙ a
    • push res vào stack
  • ngược lại nếu ch là toán hạng, thì push ch vào stack
• trả về phần tử đỉnh stack

Hãy xem triển khai sau để hiểu rõ hơn:

Ví dụ

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

float scanNum(char ch) {
    int value;
    value = ch;
    return float(value - '0'); // trả về float từ ký tự
}

int isOperator(char ch) {
    if(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^')
        return 1; // ký tự là toán tử
    return -1; // không phải toán tử
}

int isOperand(char ch) {
    if(ch >= '0' && ch <= '9')
        return 1; // ký tự là toán hạng
    return -1; // không phải toán hạng
}

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); // tìm b^a
    else return INT_MIN; // trả về âm vô cực
}

float postfixEval(string postfix) {
    int a, b;
    stack<float> stk;
    string::iterator it;
    for(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 = "21+3*";
    cout << postfixEval(post);
    return 0;
}

Đầu vào

"21+3*"

Đầu ra

9