Trong bài toán này, chúng ta được cung cấp biểu thức ở dạng hậu tố và nhiệm vụ của chúng ta là in dạng tiền tố của biểu thức.
Biểu thức infix là một biểu thức trong đó toán tử ở giữa các toán hạng, như toán hạng toán hạng.
Biểu thức hậu tố là một biểu thức trong đó toán tử đứng sau toán hạng, như toán tử toán hạng.
Hệ thống dễ dàng tính toán các biểu thức postfix nhưng con người không thể đọc được. Vì vậy việc chuyển đổi này là bắt buộc. Nói chung, việc đọc và chỉnh sửa bởi người dùng cuối được thực hiện trên các ký hiệu infix vì chúng được phân tách bằng dấu ngoặc đơn do đó dễ hiểu đối với con người.
Hãy lấy một ví dụ để hiểu vấn đề
Đầu vào - xyz / *
Đầu ra - (x * (y / z))
Để giải quyết vấn đề này, chúng ta sẽ sử dụng cấu trúc dữ liệu ngăn xếp. Và xem qua từng biểu thức postfix rồi kiểm tra trường hợp sau -
Trường hợp 1 - nếu toán hạng được tìm thấy, hãy đẩy nó vào ngăn xếp.
Trường hợp 2 - nếu một toán tử được tìm thấy, hãy bật đến toán hạng, tạo một biểu thức tiền tố của ba và đẩy biểu thức dưới dạng một toán hạng.
Cuối cùng, khi ngăn xếp chỉ còn một phần tử và việc chuyển ngang đã hoàn tất, hãy bật phần trên cùng của ngăn xếp, đó là chuyển đổi infix.
Ví dụ
Chương trình hiển thị việc triển khai giải pháp của chúng tôi.
#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<<"The infix conversion of the postfix expression '"<<postfix<<"' is : ";
cout<<infixConversion(postfix);
return 0;
} Đầu ra
The infix conversion of the postfix expression 'xyae+/%' is : {x%{y/{a+e}}}