গাণিতিক এক্সপ্রেশন সমাধানের জন্য প্রিফিক্স বা পোস্টফিক্স ফর্ম প্রয়োজন। ইনফিক্সকে পোস্টফিক্সে রূপান্তর করার পর সঠিক উত্তর পেতে পোস্টফিক্স মূল্যায়ন অ্যালগরিদম দরকার।
এখানও স্ট্যাক ডেটা স্ট্রাকচার ব্যবহার করে পোস্টফিক্স এক্সপ্রেশন সমাধান করতে হবে।
পোস্টফিক্স এক্সপ্রেশন থেকে যখন অপারেন্ড পাওয়া যায়, সেগুলো স্টকে পুশ করা হয়। যখন অপারেটর পাওয়া যায়, স্ট্যাক থেকে দুটি আইটেম পপ করে সঠিক ক্রমে অপারেশন করা হয়। তারপর ফলাফলটি ভবিষ্যতের জন্য স্টকে পুশ করা হয়। পুরো এক্সপ্রেশন শেষ হলে চূড়ান্ত ফলাফলও স্ট্যাকের টপে থাকে।
ইনপুট এবং আউটপুট
ইনপুট: পোস্টফিক্স এক্সপ্রেশন: 53+62/*35*+ আউটপুট: ফলাফল: ৩৯
অ্যালগরিদম
postfixEvaluation(postfix)
ইনপুট: মূল্যায়নের জন্য পোস্টফিক্স এক্সপ্রেশন।
আউটপুট: পোস্টফিক্স ফর্ম মূল্যায়ন করার পর উত্তর।
শুরু
পোস্টফিক্স এক্সপ্রেশনের প্রতিটি ক্যারেক্টার ch জন্য, করুন
যদি ch অপারেটর ⨀ হয়, তবে
a := স্ট্যাক থেকে প্রথম উপাদান পপ করুন
b := স্ট্যাক থেকে দ্বিতীয় উপাদান পপ করুন
res := b ⨀ a
res স্টকে পুশ করুন
অন্যথায় যদি ch অপারেন্ড হয়, তবে
ch স্টকে যোগ করুন
끝난
স্ট্যাক টপের উপাদান ফেরত দিন
শেষ
উদাহরণ (C++)
#include <iostream>
#include <cmath>
#include <stack>
using namespace std;
float scanNum(char ch) {
int value = ch;
return float(value - '0');
}
int isOperator(char ch) {
if(ch == '+' || ch == '-' || ch == '*' || ch == '/' || ch == '^')
return 1;
return -1;
}
int isOperand(char ch) {
if(ch >= '0' && ch <= '9')
return 1;
return -1;
}
float operation(int a, int b, char op) {
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);
else return INT_MIN;
}
float postfixEval(string postfix) {
int a, b;
stack stk;
string::iterator it;
for(it = postfix.begin(); it != postfix.end(); it++) {
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();
}
int main() {
string post = "53+62/*35*+";
cout << "The result is: " << postfixEval(post);
}
আউটপুট
The result is: 39
