C++ में कोष्ठक जोड़ने के विभिन्न तरीके

मान लीजिए कि हमारे पास संख्याओं और ऑपरेटरों की एक स्ट्रिंग है, हमें संख्याओं और ऑपरेटरों को समूहबद्ध करने के सभी संभावित तरीकों की गणना करने से सभी संभावित परिणाम प्राप्त करने होंगे। यहां मान्य ऑपरेटर +, - और * हैं। तो अगर इनपुट "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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• मेमो नामक मानचित्र को परिभाषित करें।

• हल () नामक एक विधि को परिभाषित करें। यह इनपुट स्ट्रिंग को इनपुट के रूप में लेगा।

• रिट नामक एक सरणी बनाएं

• यदि मेमो में इनपुट है, तो मेमो [इनपुट]

  लौटाएं

• मैं के लिए 0 से इनपुट स्ट्रिंग के आकार में -

  • अगर इनपुट [i] कोई समर्थित ऑपरेटर है, तो

    • एक सरणी भाग 1:=हल (0 से i - 1 तक इनपुट का विकल्प)

    • एक सरणी भाग 2:=हल करें (मैं से स्ट्रिंग के अंत तक इनपुट का विकल्प)

    • j के लिए 0 से लेकर part1 के आकार तक

      • k के लिए 0 से लेकर part2 के आकार तक

        • अगर इनपुट [i] जोड़ है, तो

          • भाग [जे] + भाग [के] निष्पादित करें और रिट में जोड़ें

        • अगर इनपुट [i] गुणा है, तो

          • भाग [जे] * भाग [के] निष्पादित करें और रिट में जोड़ें

        • अगर इनपुट [i] घटाव है, तो

          • भाग [जे] - भाग [के] निष्पादित करें और रिट में जोड़ें

• यदि रिट खाली है, तो इनपुट स्ट्रिंग को पूर्णांक के रूप में लौटाएं

• मेमो [इनपुट]:=रिट, और रिटर्न रिट

उदाहरण (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, ]