ในปัญหานี้ เราได้รับนิพจน์ Prefix งานของเราคือพิมพ์การแปลง Postfix ของนิพจน์ที่กำหนด
Prefix expression คือนิพจน์ที่มีตัวดำเนินการอยู่ก่อนตัวถูกดำเนินการ
ตัวอย่าง: +AB
Postfix expressions คือนิพจน์ที่มีตัวดำเนินการอยู่หลังตัวถูกดำเนินการในนิพจน์
ตัวอย่าง: AB/
การแปลงจาก prefix เป็น postfix ไม่ควรเกี่ยวข้องกับการแปลงเป็น infix
ลองดูตัวอย่างเพื่อทำความเข้าใจปัญหา:
Input: /+XY+NM Output: XY+NM+/ Explanation: infix -> (X+Y)/(N+M)
ในการแก้ปัญหานี้ เราจะเดินทางผ่าน postfix expression ทั้งหมดในลำดับย้อนกลับ และเราจะใช้โครงสร้างข้อมูล Stack สำหรับการประมวลผลของเรา และทำดังต่อไปนี้สำหรับกรณีขององค์ประกอบที่พบระหว่างการเดินทาง
- Case: ถ้าสัญลักษณ์เป็น operand -> push(element) ใน stack
- Case: ถ้าสัญลักษณ์เป็น operator -> 2*pop(element) จาก stack และ push ลำดับของ operand - operand - operator
โปรแกรมแสดงการนำอัลกอริทึมของเราไปใช้
ตัวอย่างโค้ด
#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;
}
ผลลัพธ์
Prefix expression : *-AB/+CD*XY Postfix expression : AB-CD+XY*/*
