এই সমস্যায়, আমাদের একটি প্রিফিক্স এক্সপ্রেশন দেওয়া হয়। আমাদের কাজ হল প্রদত্ত অভিব্যক্তির পোস্টফিক্স রূপান্তর প্রিন্ট করা।
উপসর্গ এক্সপ্রেশন হল সেই এক্সপ্রেশন যার অপারেন্ডের আগে অপারেটর থাকে।
উদাহরণ:+AB.
পোস্টফিক্স এক্সপ্রেশন হল সেই সব এক্সপ্রেশন যার এক্সপ্রেশনে অপারেন্ডের পরে অপারেটর থাকে।
উদাহরণ:AB/
উপসর্গ থেকে পোস্টফিক্সে রূপান্তরের সাথে ইনফিক্সে রূপান্তর জড়িত হওয়া উচিত নয়।
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,
Input: /+XY+NM Output: XY+NM+/ Explanation: infix -> (X+Y)/(N+M)
এই সমস্যাটি সমাধান করার জন্য, আমরা প্রথমে একটি বিপরীত ক্রমে পুরো পোস্টফিক্স এক্সপ্রেশনটি অতিক্রম করব। এবং আমরা আমাদের প্রক্রিয়াকরণের জন্য স্ট্যাক ডেটা স্ট্রাকচার ব্যবহার করব। এবং ট্রাভার্সাল পাওয়া উপাদানগুলির ক্ষেত্রে নিম্নলিখিতগুলি করুন
কেস:যদি প্রতীকটি অপারেন্ড হয় -> স্ট্যাকের মধ্যে পুশ(উপাদান)।
কেস:যদি প্রতীক অপারেটর হয় -> স্ট্যাক থেকে 2*পপ(এলিমেন্ট)। এবং তারপরে অপারেন্ড - অপারেন্ড - অপারেটরের পুশ সিকোয়েন্স।
আমাদের অ্যালগরিদমের বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম
উদাহরণ
#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*/*
