Postfix เป็น Infix ใน C++

ในปัญหานี้ เราได้รับนิพจน์ในรูปแบบ postfix และหน้าที่ของเราคือพิมพ์รูปแบบ infix ของนิพจน์

นิพจน์อินฟิกซ์ เป็นนิพจน์ที่ตัวดำเนินการอยู่ตรงกลางของตัวถูกดำเนินการ เช่น ตัวดำเนินการตัวถูกดำเนินการ

นิพจน์หลังการแก้ไข เป็นนิพจน์ที่ตัวดำเนินการอยู่หลังตัวถูกดำเนินการ เช่น ตัวดำเนินการตัวถูกดำเนินการ

ระบบคำนวณนิพจน์ Postfix ได้ง่าย แต่ไม่สามารถอ่านได้โดยมนุษย์ จึงต้องแปลงนี้ โดยทั่วไปแล้ว การอ่านและแก้ไขโดยผู้ใช้ปลายทางจะทำโดยใช้เครื่องหมาย infix เนื่องจากวงเล็บแยกจากกัน ทำให้มนุษย์เข้าใจได้ง่าย

มาดูตัวอย่างทำความเข้าใจปัญหากัน

ป้อนข้อมูล − xyz/*

ผลลัพธ์ − (x * (y/z))

เพื่อแก้ปัญหานี้ เราจะใช้โครงสร้างข้อมูลสแต็ก และสำรวจนิพจน์ postfix ทีละตัวแล้วตรวจสอบกรณีต่อไปนี้ −

กรณีที่ 1 − หากพบตัวถูกดำเนินการ ให้ดันมันเข้าไปในสแต็ก

กรณีที่ 2 − หากพบตัวดำเนินการ ให้ป๊อปไปที่ตัวถูกดำเนินการ สร้างนิพจน์ infix ของทั้งสามและกดนิพจน์เป็นตัวถูกดำเนินการ

ในท้ายที่สุดเมื่อสแต็กเหลือเพียงองค์ประกอบเดียวและการสำรวจเสร็จสิ้น ให้ป๊อปอัพที่ด้านบนของสแต็ก มันคือการแปลง infix

ตัวอย่าง

โปรแกรมแสดงการใช้งานโซลูชันของเรา

#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;
}

ผลลัพธ์

The infix conversion of the postfix expression 'xyae+/%' is : {x%{y/{a+e}}}