ধরুন আমাদের পোস্টফিক্স এক্সপ্রেশন আছে এবং আমাদের মান মূল্যায়ন করতে হবে। পোস্টফিক্স এক্সপ্রেশন রিভার্স পলিশ নোটেশন নামেও পরিচিত। পোস্টফিক্স এক্সপ্রেশন সমাধান করার জন্য এখানে স্ট্যাক ডেটা স্ট্রাকচার ব্যবহার করতে হবে।
তাই যদি অভিব্যক্তিটি "21+3*" হয়, তাহলে উত্তর হবে 9।
আসুন ধাপগুলো দেখি -
- পোস্টফিক্স এক্সপ্রেশনে প্রতিটি অক্ষর ch-এর জন্য
- যদি ch একটি অপারেটর $\odot$ হয়, তাহলে
- a :=স্ট্যাক থেকে প্রথম উপাদান পপ করুন,
- b :=স্ট্যাক থেকে পপ দ্বিতীয় উপাদান
- res :=b $\odot$ a
- স্ট্যাকের মধ্যে পুশ রেস
- অন্যথায় যদি ch একটি অপারেন্ড হয়, তাহলে
- স্ট্যাকের মধ্যে ch যোগ করুন
- স্ট্যাক টপের রিটার্ন এলিমেন্ট
- করুন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include<bits/stdc++.h>
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 = "21+3*";
cout <<postfixEval(post);
} ইনপুট
"21+3*"
আউটপুট
9
