এই নিবন্ধে, আমরা প্রিফিক্স এক্সপ্রেশনের মূল্যায়ন নিয়ে আলোচনা করব।
প্রিফিক্স এক্সপ্রেশন
এই স্বরলিপিতে, অপারেটর প্রিফিক্সড অপারেন্ডে, অর্থাৎ অপারেটর অপারেন্ডের আগে লেখা হয়। উদাহরণস্বরূপ, +ab . এটি তার ইনফিক্স স্বরলিপি a + b এর সমতুল্য . উপসর্গ স্বরলিপি পোলিশ স্বরলিপি নামেও পরিচিত .
আরো পড়ার জন্য।
উদাহরণ:
* + 6 9 - 3 1
প্রিফিক্স এক্সপ্রেশনগুলি ইনফিক্স এক্সপ্রেশনের চেয়ে দ্রুত মূল্যায়ন করা হয়। এছাড়াও, প্রিফিক্স এক্সপ্রেশনে কোন বন্ধনী নেই যা এটিকে দ্রুত মূল্যায়ন করে।
প্রিফিক্স এক্সপ্রেশন মূল্যায়ন করার জন্য অ্যালগরিদম:
প্রিফিক্স এক্সপ্রেশনের মূল্যায়নের জন্য স্ট্যাক ডেটা স্ট্রাকচার প্রয়োজন। আমরা অপারেটরদের স্ট্যাকের মধ্যে পুশ করব এবং তারপর এক্সপ্রেশন সমাধান করব।
আমরা একে একে অভিব্যক্তির প্রতিটি উপাদান পরিদর্শন করব। যদি বর্তমান উপাদানটি একটি অপারেন্ড হয় তবে আমরা এটিকে স্ট্যাকের দিকে ঠেলে দেব। এবং যদি এটি একটি অপারেটর হয়, আমরা দুটি অপারেন্ড পপ করব, অপারেশনটি সঞ্চালন করব, অপারেটর অপারেটর অপারেন্ড এবং তারপর ফলাফলটিকে স্ট্যাকের দিকে পুশ করব৷
অ্যালগরিদম −
ধাপ 1: অভিব্যক্তির শেষ উপাদান থেকে শুরু করুন।
ধাপ 2: বর্তমান উপাদান পরীক্ষা করুন।
ধাপ 2.1: যদি এটি একটি অপারেন্ড হয়, তাহলে এটিকে স্ট্যাকের দিকে ঠেলে দিন।
ধাপ 2.2: এটি একটি অপারেটর হলে, স্ট্যাক থেকে দুটি অপারেন্ড পপ করুন। অপারেশনটি সম্পাদন করুন এবং উপাদানগুলিকে স্ট্যাকের দিকে ঠেলে দিন৷
ধাপ 3: এটি করুন যতক্ষণ না এক্সপ্রেশনের সমস্ত উপাদানগুলি অতিক্রম করা হয় এবং স্ট্যাকের শীর্ষে ফিরে আসে যা অপারেশনের ফলাফল হবে৷
একটি প্রিফিক্স এক্সপ্রেশন সমাধান করতে আমাদের অ্যালগরিদমের কাজ দেখা যাক,
প্রিফিক্স এক্সপ্রেশন :
* + 6 9 - 3 1
পুনরাবৃত্তি:1
উপাদান স্ক্যান করা হয়েছে => 1
অপারেশন => পুশ টু স্ট্যাক
স্ট্যাক => 1
পুনরাবৃত্তি:2
উপাদান স্ক্যান করা হয়েছে => 3
অপারেশন => পুশ টু স্ট্যাক
স্ট্যাক => ৩ , ১
পুনরাবৃত্তি:3
উপাদান স্ক্যান করা হয়েছে => -
অপারেশন => স্ট্যাক থেকে পপ টু, অপারেশন সঞ্চালন এবং ফলাফল পিছনে ধাক্কা।
3 - 1 =2
স্ট্যাক => 2
পুনরাবৃত্তি:4
উপাদান স্ক্যান করা হয়েছে => 9
অপারেশন => পুশ টু স্ট্যাক
স্ট্যাক => 9 , 2
পুনরাবৃত্তি :5
উপাদান স্ক্যান করা হয়েছে => 6
অপারেশন => পুশ টু স্ট্যাক
স্ট্যাক => 6, 9, 2
পুনরাবৃত্তি:6
উপাদান স্ক্যান করা হয়েছে => +
অপারেশন => স্ট্যাক থেকে পপ টু, অপারেশন সঞ্চালন এবং ফলাফল পিছনে ধাক্কা।
6 + 9 =15
স্ট্যাক => 15 , 2
পুনরাবৃত্তি:7
উপাদান স্ক্যান করা হয়েছে => *
অপারেশন => স্ট্যাক থেকে পপ টু, অপারেশন সঞ্চালন এবং ফলাফল পিছনে ধাক্কা।
15 * 2 =30
স্ট্যাক => ৩০
সমাপ্তি => স্ট্যাকের শীর্ষে ফিরুন, ফলাফল =30।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম,
উদাহরণ
#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
