Chuyển đổi tiền tố sang trung 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 trung tố của biểu thức cho trước.

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

Ví dụ: +AB.

Biểu thức trung tố là những biểu thức có toán tử giữa các toán hạng.

Ví dụ: A+B

Biểu thức trung tố là thông tin để con người hiểu, nhưng máy tính thực hiện tính toán trên biểu thức tiền tố hoặc hậu tố (thường là hậu tố).

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

Đầu vào: tiền tố : /+LM/NX
Đầu ra: trung tố : (L+M) / (N/X)

Để giải quyết bài toán này, chúng ta sẽ sử dụng cấu trúc dữ liệu stack. Chúng ta sẽ duyệt biểu thức tiền tố theo thứ tự ngược lại của biểu thức. Và với mỗi phần tử của biểu thức, kiểm tra các trường hợp sau:

Nếu phần tử là toán hạng -> push(phần tử) vào stack.

Nếu phần tử là toán tử -> 2 lần pop(đỉnh stack) và push theo thứ tự như một chuỗi = toán hạng - toán tử - toán hạng.

Cuối cùng, sau khi duyệt xong, đỉnh stack sẽ chứa một chuỗi là chuyển đổi trung tố, in ra nó.

Chương trình minh họa triển khai giải pháp của chúng ta:

Ví dụ

#include <iostream>
#include <stack>
using namespace std;
bool isOperator(char element) {
    switch (element) {
        case '+':
        case '-':
        case '/':
        case '*':
            return true;
    }
    return false;
}
string convertToInfix(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+prefix[i]+op2+"}";
            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 trung tố : " <<convertToInfix(prefix);
    return 0;
}

Kết quả

Biểu thức tiền tố : *-AB/+CD*XY
Biểu thức trung tố : {{A-B}*{{C+D}/{X*Y}}}