C++-এ প্রিফিক্স এক্সপ্রেশন থেকে ইনফিক্স কনভার্সন (Prefix to Infix Conversion)

এই সমস্যাতে, একটি প্রিফিক্স এক্সপ্রেশন দেওয়া থাকে। এর ইনফিক্স রূপান্তর (conversion) প্রিন্ট করতে হবে।

সংজ্ঞা

• প্রিফিক্স: অপারেটর অপারেন্ডের আগে থাকে। উদাহরণ: +AB
• ইনফিক্স: অপারেটর দুটি অপারেন্ডের মাঝপথে থাকে। উদাহরণ: A+B

স্ট্যাক ভিত্তিক অ্যালগরিদম

1. প্রিফিক্স এক্সপ্রেশনটি রিভার্স অর্ডারে ট্রাভার্স করুন
2. যদি অপারেন্ড হয় → স্ট্যাকে পুশ করুন
3. যদি অপারেটর হয় → স্ট্যাকে থেকে ২টি পপ করুন, {op1 + operator + op2} ফরম্যাটে স্ট্রিং বানিয়ে পুশ করুন
4. শেষে স্ট্যাকে টপে ইনফিক্স এক্সপ্রেশন পাবেন

C++ প্রোগ্রাম উদাহরণ

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