ধরুন আমাদের বিপরীত পলিশ নোটেশন আছে এবং আমাদের মানটি মূল্যায়ন করতে হবে। বিপরীত পলিশ স্বরলিপি পোস্টফিক্স এক্সপ্রেশন হিসাবেও পরিচিত। পোস্টফিক্স এক্সপ্রেশন সমাধান করার জন্য এখানে স্ট্যাক ডেটা স্ট্রাকচার ব্যবহার করতে হবে।
পোস্টফিক্স এক্সপ্রেশন থেকে, যখন কিছু অপারেন্ড পাওয়া যায়, সেগুলিকে স্ট্যাকের মধ্যে পুশ করে। যখন কিছু অপারেটর পাওয়া যায়, স্ট্যাক থেকে দুটি আইটেম পপ করা হয় এবং তারপর অপারেশনটি সঠিক ক্রমানুসারে সঞ্চালিত হয়। এর পরে, ফলাফলটি ভবিষ্যতে ব্যবহারের জন্য স্ট্যাকের মধ্যেও পুশ করা হয়। সম্পূর্ণ অভিব্যক্তিটি সম্পূর্ণ করার পরে, চূড়ান্ত ফলাফলটি স্ট্যাক শীর্ষে সংরক্ষণ করা হয়। তাই যদি অভিব্যক্তিটি "53+62/*35*+" হয়, তাহলে উত্তর হবে 39
আসুন ধাপগুলো দেখি -
- পোস্টফিক্স এক্সপ্রেশনে প্রতিটি অক্ষর ch-এর জন্য
- যদি ch একটি অপারেটর হয় ☉, তাহলে
- a :=স্ট্যাক থেকে প্রথম উপাদান পপ করুন,
- b :=স্ট্যাক থেকে পপ দ্বিতীয় উপাদান
- res :=b ☉ a
- স্ট্যাকের মধ্যে পুশ রেস
- অন্যথায় যদি ch একটি অপারেন্ড হয়, তাহলে
- স্ট্যাকের মধ্যে ch যোগ করুন
- স্ট্যাক টপের রিটার্ন এলিমেন্ট
- করুন
উদাহরণ(C++)
আসুন আরও ভালোভাবে বোঝার জন্য নিচের বাস্তবায়ন দেখি −
#include<iostream>
#include<cmath>
#include<stack>
#include<climits>
using namespace std;
float scanNum(char ch){
int value;
value = ch;
return float(value-'0');//return float from character
}
int isOperator(char ch){
if(ch == '+'|| ch == '-'|| ch == '*'|| ch == '/' || ch == '^')
return 1;//character is an operator
return -1;//not an operator
}
int isOperand(char ch){
if(ch >= '0' && ch <= '9')
return 1;//character is an operand
return -1;//not an operand
}
float operation(int a, int b, char op){
//Perform operation
if(op == '+')
return b+a;
else if(op == '-')
return b-a;
else if(op == '*')
return b*a;
else if(op == '/')
return b/a;
else if(op == '^')
return pow(b,a); //find b^a
else
return INT_MIN; //return negative infinity
}
float postfixEval(string postfix){
int a, b;
stack<float> stk;
string::iterator it;
for(it=postfix.begin(); it!=postfix.end(); it++){
//read elements and perform postfix evaluation
if(isOperator(*it) != -1){
a = stk.top();
stk.pop();
b = stk.top();
stk.pop();
stk.push(operation(a, b, *it));
}
else if(isOperand(*it) > 0){
stk.push(scanNum(*it));
}
}
return stk.top();
}
main(){
string post = "53+62/*35*+";
cout << "The result is: "<<postfixEval(post);
} ইনপুট
"53+62/*35*+"
আউটপুট
The result is: 39
