Computer >> Máy Tính >  >> Lập trình >> C ++

Chuyển đổi tiền tố thành tiền 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 ta là in chuyển đổi infix của biểu thức đã cho.

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 tiền 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 tiền tố là thông tin để con người hiểu được, nhưng máy tính thực hiện tính toán trên các biểu thức tiền tố hoặc hậu tố (thường là hậu tố).

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

Input: prefix : /+LM/NX
Output: infix : (L+M) / (N/X)

Để giải quyết vấn đề này, chúng tôi sẽ sử dụng cấu trúc dữ liệu ngăn xếp. 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à đối với mỗi phần tử của biểu thức, hãy kiểm tra các trường hợp này.

Nếu phần tử là toán hạng -> push (phần tử) trong ngăn xếp.

Nếu phần tử là toán tử -> 2Xpop (topofstack) và đẩy theo thứ tự dưới dạng chuỗi =toán hạng - toán tử - toán hạng.

Cuối cùng, sau khi duyệt, trên cùng của ngăn xếp sẽ chứa một chuỗi là chuyển đổi infix, hãy in nó.

Chương trình cho thấy việc triển khai giải pháp của chúng tôi

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

Đầu ra

Prefix expression : *-AB/+CD*XY
Infix expression : {{A-B}*{{C+D}/{X*Y}}}