Chuyển đổi tiền tố sang hậu tố trong C++

Trong bài toán này, chúng ta được cho một biểu thức tiền tố. Nhiệm vụ của chúng ta là in chuyển đổi hậu tố của biểu thức cho trước.

Tiền tố là những biểu thức có toán tử trước toán hạng.

Ví dụ: +AB.

Hậu tố là những biểu thức có toán tử sau toán hạng trong biểu thức.

Ví dụ: AB/

Chuyển đổi từ tiền tố sang hậu tố không nên liên quan đến chuyển đổi sang trung tố.

Hãy xem một ví dụ để hiểu bài toán:

Đầu vào: /+XY+NM
Đầu ra: XY+NM+/
Giải thích: trung tố -> (X+Y)/(N+M)

Để giải quyết bài toán này, chúng ta sẽ trước tiên duyệt toàn bộ biểu thức hậu tố theo thứ tự ngược lại. Và chúng ta sẽ sử dụng cấu trúc dữ liệu stack cho việc xử lý. Và làm như sau cho các trường hợp phần tử tìm thấy khi duyệt:

Trường hợp: nếu ký hiệu là toán hạng -> push(phần tử) vào stack.

Trường hợp: nếu ký hiệu là toán tử -> 2*pop(phần tử) từ stack. Sau đó push chuỗi theo thứ tự toán hạng - toán hạng - toán tử.

Chương trình minh họa triển khai thuật toán của chúng ta:

Ví dụ

#include <iostream>
#include <stack>
using namespace std;
bool isOperator(char x) {
    switch (x) {
        case '+':
        case '-':
        case '/':
        case '*':
            return true;
    }
    return false;
}
string convertToPostfix(string prefix) {
    stack<string> expression;
    int length = prefix.size();
    for (int i = length - 1; i >= 0; i--) {
        if (isOperator(prefix[i])) {
            string op1 = expression.top();
            expression.pop();
            string op2 = expression.top();
            expression.pop();
            string temp = op1 + op2 + prefix[i];
            expression.push(temp);
        }
        else
            expression.push(string(1, prefix[i]));
    }
    return expression.top();
}
int main() {
    string prefix = "*-AB/+CD*XY";
    cout<<"Biểu thức tiền tố : "<<prefix<<endl;
    cout<<"Biểu thức hậu tố : "<<convertToPostfix(prefix);
    return 0;
}

Kết quả

Biểu thức tiền tố : *-AB/+CD*XY
Biểu thức hậu tố : AB-CD+XY*/*