Đánh giá biểu thức tiền tố (Prefix) trong C++

Trong bài viết này, chúng ta sẽ thảo luận về đánh giá biểu thức tiền tố (Prefix Expression).

Biểu thức tiền tố (Prefix Expression)

Trong ký pháp này, toán tử được viết trước các toán hạng. Ví dụ: +ab. Điều này tương đương với ký pháp trung tố (infix) a + b. Ký pháp tiền tố còn được gọi là Ký pháp Ba Lan (Polish Notation).

Ví dụ:

* + 6 9 - 3 1

Biểu thức tiền tố được đánh giá nhanh hơn biểu thức trung tố. Ngoài ra, không có dấu ngoặc trong biểu thức tiền tố, giúp quá trình tính toán nhanh chóng hơn.

Thuật toán đánh giá biểu thức tiền tố

Việc đánh giá biểu thức tiền tố yêu cầu cấu trúc dữ liệu ngăn xếp (stack). Ta duyệt các phần tử của biểu thức từ phải sang trái (từ cuối về đầu). Nếu phần tử hiện tại là toán hạng, đẩy nó vào ngăn xếp. Nếu là toán tử, lấy ra hai toán hạng từ đỉnh ngăn xếp, thực hiện phép toán (toán hạng 1 toán tử toán hạng 2), sau đó đẩy kết quả trở lại ngăn xếp.

Các bước thuật toán

1. Bước 1: Bắt đầu từ phần tử cuối cùng của biểu thức.
2. Bước 2: Kiểm tra phần tử hiện tại.
   • 2.1: Nếu là toán hạng, đẩy vào ngăn xếp.
   • 2.2: Nếu là toán tử, lấy hai toán hạng từ ngăn xếp, thực hiện phép toán và đẩy kết quả vào ngăn xếp.
3. Bước 3: Lặp lại cho đến khi duyệt hết biểu thức. Phần tử ở đỉnh ngăn xếp chính là kết quả.

Minh họa quá trình chạy thuật toán

Biểu thức tiền tố: * + 6 9 - 3 1

Kết thúc: Trả về đỉnh ngăn xếp, kết quả = 30.

Chương trình minh họa

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

double evaluatePrefix(string prefixExp) {
    stack<double> operandStack;
    int size = prefixExp.size() - 1;

    for (int i = size; i >= 0; i--) {
        if (isdigit(prefixExp[i])) {
            operandStack.push(prefixExp[i] - '0');
        } else {
            double o1 = operandStack.top(); operandStack.pop();
            double o2 = operandStack.top(); operandStack.pop();

            switch (prefixExp[i]) {
                case '+': operandStack.push(o1 + o2); break;
                case '-': operandStack.push(o1 - o2); break;
                case '*': operandStack.push(o1 * o2); break;
                case '/': operandStack.push(o1 / o2); break;
                default:
                    cout << "Biểu thức không hợp lệ";
                    return -1;
            }
        }
    }
    return operandStack.top();
}

int main() {
    string prefixExp = "*+69-31";
    cout << "Kết quả đánh giá biểu thức " << prefixExp << " là " << evaluatePrefix(prefixExp);
    return 0;
}

Đầu ra

Kết quả đánh giá biểu thức *+69-31 là 30