Trong bài toán này, chúng ta được cho một biểu thức dưới dạng hậu tố (postfix) và nhiệm vụ là in ra dạng trung tố (infix) của biểu thức đó.
Biểu thức trung tố là biểu thức mà toán tử nằm giữa hai toán hạng, ví dụ: toán hạng toán tử toán hạng.
Biểu thức hậu tố là biểu thức mà toán tử nằm sau các toán hạng, ví dụ: toán hạng toán hạng toán tử.
Biểu thức hậu tố dễ dàng được máy tính xử lý nhưng khó đọc đối với con người. Do đó, việc chuyển đổi này là cần thiết. Thông thường, việc đọc và chỉnh sửa bởi người dùng cuối được thực hiện trên ký pháp trung tố vì chúng được phân tách bằng dấu ngoặc, dễ hiểu hơn.
Hãy xem ví dụ sau để hiểu rõ bài toán:
Đầu vào – xyz/*
Đầu ra – (x * (y/z))
Để giải bài toán này, ta sử dụng cấu trúc dữ liệu ngăn xếp (stack). Duyệt biểu thức hậu tố từng ký tự và xử lý các trường hợp sau:
Trường hợp 1 – Nếu gặp toán hạng, đẩy vào ngăn xếp.
Trường hợp 2 – Nếu gặp toán tử, lấy ra hai toán hạng từ ngăn xếp, tạo biểu thức trung tố từ ba thành phần đó và đẩy biểu thức kết quả trở lại ngăn xếp như một toán hạng.
Cuối cùng, khi ngăn xếp chỉ còn một phần tử và duyệt xong, lấy phần tử đỉnh ngăn xếp – đó chính là biểu thức trung tố kết quả.
Ví dụ minh họa
Chương trình triển khai giải pháp:
#include <bits/stdc++.h> using namespace std; bool isOperand(char x) { return (x >= 'a' && x <= 'z') || (x >= 'A' && x <= 'Z'); } string infixConversion(string postfix) { stack<string> infix; for (int i=0; postfix[i]!='\0'; i++) { if (isOperand(postfix[i])) { string op(1, postfix[i]); infix.push(op); } else { string op1 = infix.top(); infix.pop(); string op2 = infix.top(); infix.pop(); infix.push("("+op2+postfix[i]+op1+")"); } } return infix.top(); } int main() { string postfix = "xyae+/%"; cout<<"Biểu thức trung tố của hậu tố '"<<postfix<<"' là: "; cout<<infixConversion(postfix); return 0; }Kết quả
Biểu thức trung tố của hậu tố 'xyae+/%' là: (x%(y/(a+e)))