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

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

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

Ví dụ:+ AB.

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

Ví dụ:AB /

Việc chuyển đổi tiền tố thành hậu tố không được liên quan đến việc chuyển đổi thành tiền tố.

Hãy lấy một ví dụ để hiểu vấn đề,

Input: /+XY+NM
Output: XY+NM+/
Explanation: infix -> (X+Y)/(N+M)

Để giải quyết vấn đề này, trước tiên chúng ta sẽ duyệt qua toàn bộ biểu thức postfix theo một thứ tự ngược lại. Và chúng tôi sẽ sử dụng cấu trúc dữ liệu ngăn xếp để xử lý. Và thực hiện như sau đối với các trường hợp phần tử được tìm thấy có tính chất chuyển tải

Trường hợp:nếu biểu tượng là toán hạng -> push (phần tử) trong ngăn xếp.

Trường hợp:nếu biểu tượng là toán tử -> 2 * pop (phần tử) từ ngăn xếp. Và sau đó đẩy chuỗi toán hạng - toán hạng - toán tử.

Chương trình hiển thị việc triển khai thuật toán của chúng tôi

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<<"Prefix expression : "<<prefix<<endl;
   cout<<"Postfix expression : "<<convertToPostfix(prefix);
   return 0;
}

Đầu ra

Prefix expression : *-AB/+CD*XY
Postfix expression : AB-CD+XY*/*