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