การแปลงนิพจน์ Postfix เป็น Infix ใน C++

ในปัญหานี้ เราได้รับนิพจน์ในรูปแบบ Postfix และต้องแปลงเป็นรูปแบบ Infix

ความแตกต่างระหว่าง Infix และ Postfix

Infix Expression คือ นิพจน์ที่ตัวดำเนินการอยู่ระหว่างตัวถูกดำเนินการ เช่น operand operator operand (เช่น A + B)

Postfix Expression คือ นิพจน์ที่ตัวดำเนินการอยู่หลังตัวถูกดำเนินการ เช่น operand operand operator (เช่น AB+)

นิพจน์ Postfix คอมพิวเตอร์คำนวณได้ง่าย แต่มนุษย์อ่านยาก ในขณะที่ Infix ใช้วงเล็บคั่น ทำให้มนุษย์อ่านและแก้ไขได้ง่ายกว่า

ตัวอย่าง

Input − xyz/*

Output − (x * (y/z))

อัลกอริทึมการแปลง

ใช้โครงสร้างข้อมูล Stack (กอง) และอ่านนิพจน์ Postfix ทีละตัวอักษร:

• กรณีที่ 1: พบตัวถูกดำเนินการ (operand) → push เข้า stack
• กรณีที่ 2: พบตัวดำเนินการ (operator) → pop ตัวถูกดำเนินการ 2 ตัวออกจาก stack สร้างนิพจน์ Infix แล้ว push กลับเข้า stack

เมื่อจบการอ่าน และ stack เหลือเพียง 1 องค์ประกอบ ให้ pop ออกมา จะได้นิพจน์ Infix ที่ต้องการ

ตัวอย่างโค้ด C++

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