C++ প্রোগ্রাম: স্ট্যাক ব্যবহার করে এক্সপ্রেশন ইভ্যালুয়েট করা

গাণিতিক এক্সপ্রেশন সমাধানের জন্য প্রিফিক্স বা পোস্টফিক্স ফর্ম দরকার। ইনফিক্স থেকে পোস্টফিক্সে কনভার্ট করার পর, সঠিক উত্তর পেতে পোস্টফিক্স ইভ্যালুয়েশন অ্যালগরিদম লাগে।

এখানেও স্ট্যাক ডেটা স্ট্রাকচার ব্যবহার করে পোস্টফিক্স এক্সপ্রেশন সমাধান করা হয়।

পোস্টফিক্স এক্সপ্রেশন থেকে, যখন কিছু অপারেন্ড পাওয়া যায়, সেগুলো স্টকে পুশ করা হয়। যখন কোনো অপারেটর পাওয়া যায়, স্ট্যাক থেকে দুটি আইটেম পপ করা হয় এবং সঠিক ক্রমে অপারেশন করা হয়। তারপর ফলাফলটিও ভবিষ্যতে ব্যবহারের জন্য স্টকে পুশ করা হয়। পুরো এক্সপ্রেশন শেষ হলে, চূড়ান্ত ফলাফল স্ট্যাকের টপে থাকে।

ইনপুট: পোস্টফিক্স এক্সপ্রেশন: 53+62/*35*+
আউটপুট: ফলাফলটি হলো: 39

অ্যালগরিদম

postfixEvaluation(postfix)

ইনপুট: ইভ্যালুয়েট করার জন্য পোস্টফিক্স এক্সপ্রেশন।

আউটপুট: পোস্টফিক্স ফর্ম ইভ্যালুয়েট করার পরের উত্তর।

শুরু
  পোস্টফিক্স এক্সপ্রেশনের প্রতিটি ক্যারেক্টার ch এর জন্য, করুন
    if ch একটি অপারেটর, তবে
      a := স্ট্যাক থেকে প্রথম এলিমেন্ট পপ
      b := স্ট্যাক থেকে দ্বিতীয় এলিমেন্ট পপ
      res := b (অপারেটর) a
      res কে স্টকে পুশ করুন
    else if ch একটি অপারেন্ড, তবে
      ch কে স্টকে যোগ করুন
  লুপ শেষ
  স্ট্যাক টপের এলিমেন্ট রিটার্ন করুন
শেষ

উদাহরণ কোড

#include<iostream>
#include<cmath>
#include<stack>
using namespace std;

float scanNum(char ch) {
    int value;
    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); // b^a বের করুন
    else
        return INT_MIN; // 네가তিভ ইনফিনিটি রিটার্ন
}

float postfixEval(string postfix) {
    int a, b;
    stack<float> 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();
}

main() {
    string post = "53+62/*35*+";
    cout << "The result is: " << postfixEval(post);
}

আউটপুট

The result is: 39