একটি প্যারেনথেসিস ছাড়া অ্যারিথমেটিক এক্সপ্রেশন দেওয়া আছে। আমাদের সেটির সকল সম্ভাব্য ফলাফল খুঁজে বের করতে হবে। উদাহরণস্বরূপ, 1+2*3-4 এক্সপ্রেশনটি নিচের तरह ইন্টারপ্রেট করা যেতে পারে:
- 1+(2*(3-4)) = 1 + (2* -1) = -1
- (1+2)*(3-4) = 3 * -1 = -3
- 1+((2*3)-4) = 1 + (6 - 4) = 3
- ((1+2)*3)-4 = (3 * 3) - 4 = 5
- 1+(2*3)-4 = 1 + 6 – 4 = 3
এটি সমাধানের জন্য নিচের ধাপগুলো অনুসরণ করতে হবে:
- শুরুতে res খালি রাখব
- প্রতিটি অপারেটর x এর জন্য:
- x-এর বামপাশের সকল সম্ভাব্য মান রিকার্সিভলি ইভ্যালুয়েট করব, লিস্ট L
- x-এর ডানপাশের সকল সম্ভাব্য মান রিকার্সিভলি ইভ্যালুয়েট করব, লিস্ট R
- L-র সব মানके লুপ চালাব:
- R-র সব মানকে লুপ চালাব:
- বর্তমান অপারেটর x L এবং R-র বর্তমান এলিমেন্টে প্রয়োগ করে ফলাফল res-এ যোগ করব
- R-র সব মানকে লুপ চালাব:
- res রিটার্ন করব আউটপুট হিসেবে
উদাহরণ
#include<iostream> #include<vector> using namespace std; int solve(int a, char op, int b) { if (op=='+') return a+b; if (op=='-') return a-b; if (op == '*') return a*b; } vector<int> getAllResults(string expr, int low, int high) { vector<int> res; if (low == high) { res.push_back(expr[low] - '0'); return res; } if (low == (high-2)) { int num = solve(expr[low]-'0', expr[low+1], expr[low+2]-'0'); res.push_back(num); return res; } for (int i=low+1; i<=high; i+=2) { vector<int> L = evaluateAll(expr, low, i-1); vector R = evaluateAll(expr, i+1, high); for (int s1=0; s1<L.size(); s1++) { for (int s2=0; s2<R.size(); s2++) { int val = solve(L[s1], expr[i], R[s2]); res.push_back(val); } } } return res; } int main() { string expr = "1+2*3-4"; vector<int> ans = getAllResults(expr, 0, expr.length()-1); for (int i=0; i< ans.size(); i++) cout << ans[i] << endl; }আউটপুট
2 1 4 3 5 6 7 8
