Chương trình C++ đánh giá biểu thức sử dụng Stack

Để giải biểu thức toán học, chúng ta cần dạng tiền tố (prefix) hoặc hậu tố (postfix). Sau khi chuyển đổi trung tố sang hậu tố, chúng ta cần thuật toán đánh giá hậu tố để tìm đáp án đúng.

Ở đây cũng cần sử dụng cấu trúc dữ liệu ngăn xếp (stack) để giải các biểu thức hậu tố.

Từ biểu thức hậu tố, khi tìm thấy một số toán hạng (operand), đẩy chúng vào ngăn xếp. Khi tìm thấy một toán tử (operator), lấy hai mục từ ngăn xếp và thực hiện phép toán theo trình tự đúng. Sau đó kết quả cũng được đẩy vào ngăn xếp để sử dụng trong tương lai. Sau khi hoàn thành toàn bộ biểu thức, kết quả cuối cùng cũng được lưu ở đỉnh ngăn xếp.

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

Thuật toán

postfixEvaluation(postfix)

Đầu vào: Biểu thức hậu tố cần đánh giá.

Đầu ra: Kết quả sau khi đánh giá dạng hậu tố.

Bắt đầu
    Với mỗi ký tự ch trong biểu thức hậu tố, thực hiện
        Nếu ch là toán tử, thì
            a := pop phần tử đầu tiên từ ngăn xếp
            b := pop phần tử thứ hai từ ngăn xếp
            res := b (toán tử) a
            đẩy res vào ngăn xếp
        Ngược lại nếu ch là toán hạng, thì thêm ch vào ngăn xếp
    Kết thúc
    Trả về phần tử đỉnh ngăn xếp
Kết thúc

Mã ví dụ

#include<iostream> 
#include<cmath> 
#include<stack> 
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) { 
    //Thực hiện phép toán 
    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ùng 
} 

float postfixEval(string postfix) { 
    int a, b; 
    stack<float> stk; 
    string::iterator it; 
    for(it = postfix.begin(); it != postfix.end(); it++) { 
        //đọc các phần tử và thực hiện đánh giá hậu tố 
        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(); 
} 

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

Kết quả

Kết quả là: 39