সি++-এ প্রিফিক্স এক্সপ্রেশন মূল্যায়ন

এই আর্টিকেলে আমরা প্রিফিক্স এক্সপ্রেশন মূল্যায়ন নিয়ে আলোচনা করব।

প্রিফিক্স এক্সপ্রেশন কী?

এই নোটেশনে অপারেটর অপারেন্ডের আগে লেখা হয়, অর্থাৎ অপারেটর অপারেন্ডের পূর্বে থাকে। উদাহরণস্বরূপ, +ab। এটি এর ইনফিক্স নোটেশন a + b সমতুল্য। প্রিফিক্স নোটেশনের অন্য নাম পোলিশ নোটেশন।

উদাহরণ:

* + 6 9 - 3 1

প্রিফিক্স এক্সপ্রেশন ইনফিক্স এক্সপ্রেশন চেয়ে দ্রুত মূল্যায়ন করা যায়। এছাড়া প্রিফিক্স এক্সপ্রেশনে কোনো ব্র্যাকেট নেই, যা এটিকে দ্রুত মূল্যায়ন করতে সাহায্য করে।

প্রিফিক্স এক্সপ্রেশন মূল্যায়ন অ্যালগরিদম:

প্রিফিক্স এক্সপ্রেশন মূল্যায়ন করতে স্ট্যাক ডেটা স্ট্রাকচার প্রয়োজন। আমরা অপারেটরগুলো স্ট্যাকে পুশ করব এবং এক্সপ্রেশনটি সমাধান করব।

আমরা এক্সপ্রেশনের প্রতিটি উপাদান একে একে ভিজিট করব। যদি বর্তমান উপাদান অপারেন্ড হয়, তবে সেটিকে স্ট্যাকে পুশ করব। আর যদি অপারেটর হয়, তবে স্ট্যাক থেকে দুটি অপারেন্ড পপ করব, অপারেশন সম্পাদন করব (অপারেন্ড অপারেটর অপারেন্ড), এবং ফলাফল আবার স্ট্যাকে পুশ করব।

অ্যালগরিদম ধাপসমূহ:

ধাপ ১: এক্সপ্রেশনের শেষ উপাদান থেকে শুরু করুন।

ধাপ ২: বর্তমান উপাদান চেক করুন।

ধাপ ২.১: যদি অপারেন্ড হয়, স্ট্যাকে পুশ করুন।
ধাপ ২.২: যদি অপারেটর হয়, স্ট্যাক থেকে দুটি অপারেন্ড পপ করুন। অপারেশন সম্পাদন করুন এবং ফলাফল স্ট্যাকে ফিরিয়ে দিন।

ধাপ ৩: এক্সপ্রেশনের সব উপাদান ট্রাভার্স না হওয়া পর্যন্ত এটি চালিয়ে যান এবং স্ট্যাকে টপের মান ফেরত দিন, যা অপারেশনের ফলাফল হবে।

আমাদের অ্যালগরিদমের কাজ দেখি

প্রিফিক্স এক্সপ্রেশন:

* + 6 9 - 3 1

ইটারেশন: ১

স্ক্যান করা উপাদান = ১

অপারেশন = স্ট্যাকে পুশ করুন
স্ট্যাক = ১

ইটারেশন: ২

স্ক্যান করা উপাদান = ৩

অপারেশন = স্ট্যাকে পুশ করুন
স্ট্যাক = ৩, ১

ইটারেশন: ৩

স্ক্যান করা উপাদান = -

অপারেশন = স্ট্যাক থেকে দুটি পপ করুন, অপারেশন করুন এবং ফলাফল পুশ করুন।

৩ - ১ = ২
স্ট্যাক = ২

ইটারেশন: ৪

স্ক্যান করা উপাদান = ৯

অপারেশন = স্ট্যাকে পুশ করুন
স্ট্যাক = ৯, ২

ইটারেশন: ৫

স্ক্যান করা উপাদান = ৬

অপারেশন = স্ট্যাকে পুশ করুন
স্ট্যাক = ৬, ৯, ২

ইটারেশন: ৬

স্ক্যান করা উপাদান = +

অপারেশন = স্ট্যাক থেকে দুটি পপ করুন, অপারেশন করুন এবং ফলাফল পুশ করুন।

৬ + ৯ = ১৫

স্ট্যাক = ১৫, ২

ইটারেশন: ৭

স্ক্যান করা উপাদান = *

অপারেশন = স্ট্যাক থেকে দুটি পপ করুন, অপারেশন করুন এবং ফলাফল পুশ করুন।

১৫ * ২ = ৩০
স্ট্যাক = ৩০

শেষ = স্ট্যাকে টপ ফেরত দিন, ফলাফল = ৩০।

সমাধান minhaj করার প্রোগ্রাম

#include <bits/stdc++.h> 
using namespace std; 

double evaluatePrefix(string prefixExp) { 
    stack<double> operendStack; 
    int size = prefixExp.size() - 1; 
    for (int i = size; i >= 0; i--) { 
        if (isdigit(prefixExp[i])) 
            operendStack.push(prefixExp[i] - '0'); 
        else { 
            double o1 = operendStack.top(); 
            operendStack.pop(); 
            double o2 = operendStack.top(); 
            operendStack.pop(); 
            if (prefixExp[i] == '+') 
                operendStack.push(o1 + o2); 
            else if (prefixExp[i] == '-') 
                operendStack.push(o1 - o2); 
            else if (prefixExp[i] == '*') 
                operendStack.push(o1 * o2); 
            else if (prefixExp[i] == '/') 
                operendStack.push(o1 / o2); 
            else { 
                cout << "Invalid Expression"; 
                return -1; 
            } 
        } 
    } 
    return operendStack.top(); 
} 

int main() { 
    string prefixExp = "*+69-31"; 
    cout << "The result of evaluation of expression " << prefixExp << " is " << evaluatePrefix(prefixExp); 
    return 0; 
}

আউটপুট

The result of evaluation of expression *+69-31 is 30