การแปลง Prefix เป็น Infix ใน C++

ในปัญหานี้ เราได้รับนิพจน์ Prefix งานของเราคือพิมพ์การแปลง Infix ของนิพจน์ที่กำหนด

Prefix expression คือนิพจน์ที่มีตัวดำเนินการอยู่ก่อนตัวถูกดำเนินการ

ตัวอย่าง: +AB

Infix expressions คือนิพจน์ที่มีตัวดำเนินการอยู่ระหว่างตัวถูกดำเนินการ

ตัวอย่าง: A+B

Infix expression เป็นข้อมูลสำหรับการเข้าใจของมนุษย์ แต่คอมพิวเตอร์คำนวณบน prefix หรือ postfix expressions (โดยทั่วไปคือ postfix)

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

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

ในการแก้ปัญหานี้ เราจะใช้โครงสร้างข้อมูล Stack เราจะเดินทางผ่านนิพจน์ prefix ในลำดับย้อนกลับของนิพจน์ และสำหรับแต่ละองค์ประกอบของนิพจน์ตรวจสอบกรณีเหล่านี้

• ถ้าองค์ประกอบเป็น operand -> push(element) ใน stack
• ถ้าองค์ประกอบเป็น operator -> 2X pop(top of stack) และ push ตามลำดับเป็น string = operand - operator - operand
• สุดท้าย หลังจากการเดินทาง ยอดของ stack จะมี string ซึ่งเป็นการแปลง infix พิมพ์มันออกมา

โปรแกรมแสดงการนำวิธีแก้ปัญหาของเราไปใช้

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

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

ผลลัพธ์

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