সংখ্যা ও অপারেটরের একটি স্ট্রিং দেওয়া আছে। সংখ্যা ও অপারেটরগুলোর গ্রুপিংয়ের সব সম্ভাব্য পদ্ধতিতে ক্যালকুলেট করে সব সম্ভাব্য ফলাফল বের করতে হবে। বৈধ অপারেটর: +, -, *। উদাহরণ: "2*3-4*5" হলে আউটপুট [-34, -14, -10, -10, 10]। কারণ:
(2*(3-(4*5))) = -34((2*3)-(4*5)) = -14((2*(3-4))*5) = -10(2*((3-4)*5)) = -10(((2*3)-4)*5) = 10
সমাধানের ধাপগুলো:
memoনামের একটি ম্যাপ সংজ্ঞায়িত করুন।solve()মেথড বানান যা ইনপুট স্ট্রিং নেবে:retঅ্যারে বানান।- যদি
memo-এ ইনপুট থাকে,memo[input]ফেরত দিন। i = 0থেকেinput.size()-1পর্যন্ত:- যদি
input[i]কোনো সাপোর্টেড অপারেটর হয়:part1 := solve(input.substr(0, i))part2 := solve(input.substr(i+1))j = 0থেকেpart1.size()-1পর্যন্ত:k = 0থেকেpart2.size()-1পর্যন্ত:- যদি
input[i] == '+',part1[j] + part2[k]ret-এ ঢোকান - যদি
input[i] == '*',part1[j] * part2[k]ret-এ ঢোকান - যদি
input[i] == '-',part1[j] - part2[k]ret-এ ঢোকান
- যদি
- যদি
- যদি
retখালি হয়, ইনপুট স্ট্রিংকে ইন্টিজারে কনভার্ট করেret-এ ঢোকান। memo[input] := retফেরত দিন।
উদাহরণ (C++)
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Solution { public: map <string, vector<int>> memo; vector<int> diffWaysToCompute(string input) { vector <int> ret; if(memo.count(input)) return memo[input]; for(int i = 0; i < input.size(); i++){ if(input[i] == '+' || input[i] == '*' || input[i] == '-'){ vector <int> part1 = diffWaysToCompute(input.substr(0, i)); vector <int> part2 = diffWaysToCompute(input.substr(i + 1)); for(int j = 0; j < part1.size(); j++ ){ for(int k = 0; k < part2.size(); k++){ if(input[i] == '+'){ ret.push_back(part1[j] + part2[k]); } else if(input[i] == '*'){ ret.push_back(part1[j] * part2[k]); } else { ret.push_back(part1[j] - part2[k]); } } } } } if(ret.empty()){ ret.push_back(stoi(input)); } return memo[input] = ret; } }; main(){ Solution ob; print_vector(ob.diffWaysToCompute("2*3-4*5")); }ইনপুট
"2*3-4*5"
আউটপুট
[-34, -10, -14, -10, 10, ]
