fork(3) download 
  1. #include <iostream>
  2. #include <unordered_set>
  3. #include <string>
  4. #include <vector>
  5.  
  6. class RedundantBracketRemover
  7. {
  8. public:
  9.  
  10.    RedundantBracketRemover(const std::string& s)
  11.    {
  12.       remove_redundant_brackets(s, 0);
  13.    }
  14.  
  15.    const std::vector<std::string>& get() const { return m_output; }
  16.  
  17. private:
  18.    void remove_redundant_opening_brackets(const std::string& s, size_t end)
  19.    {
  20.       int balance = 0;
  21.       for (size_t i = end; i--;)
  22.       {
  23.          if (s[i] == ')')
  24.          {
  25.             ++balance;
  26.          }
  27.          else if (s[i] == '(' && --balance < 0)
  28.          {
  29.             char last = 0;
  30.             for (size_t j = i; j < s.length(); ++j)
  31.             {
  32.                if (s[j] == '(' && last != '(')
  33.                {
  34.                   auto s2 = std::string(s).erase(j, 1);
  35.                   if (m_nodes.insert(s2).second)
  36.                      remove_redundant_opening_brackets(s2, i);
  37.                }
  38.                last = s[j];
  39.             }
  40.             return;
  41.          }
  42.       }
  43.       m_output.push_back(s);
  44.    }
  45.  
  46.    void remove_redundant_brackets(const std::string& s, size_t begin)
  47.    {
  48.       int balance = 0;
  49.       for (size_t i = begin; i < s.length(); ++i)
  50.       {
  51.          if (s[i] == '(')
  52.          {
  53.             ++balance;
  54.          }
  55.          else if (s[i] == ')' && --balance < 0)
  56.          {
  57.             char last = 0;
  58.             for (size_t j = 0; j <= i; ++j)
  59.             {
  60.                if (s[j] == ')' && last != ')')
  61.                {
  62.                   auto s2 = std::string(s).erase(j, 1);
  63.                   if (m_nodes.insert(s2).second)
  64.                   {
  65.                      remove_redundant_brackets(s2, i);
  66.                   }
  67.                }
  68.                last = s[j];
  69.             }
  70.             return;
  71.          }
  72.       }
  73.       remove_redundant_opening_brackets(s, s.length());
  74.    }
  75. private:
  76.    std::vector<std::string> m_output;
  77.    std::unordered_set<std::string> m_nodes;
  78. };
  79.  
  80. std::vector<std::string> remove_redundant_brackets(const std::string& s)
  81. {
  82.    return RedundantBracketRemover(s).get();
  83. }
  84.  
  85. int main()
  86. {
  87.    const auto s = "()(())(()())(())((())()))))))()))))(((((()(((((())(()())((())(()()))";
  88.    //const auto s = "(a)())()))((b(b)";
  89.  
  90.    auto variants = remove_redundant_brackets(s).size();
  91.    std::cout << "variants: " << variants << std::endl;
  92.  
  93. //   for (auto&& s : remove_redundant_brackets(s))
  94. //   {
  95. //      std::cout << s << std::endl;
  96. //   }
  97. }
  98.  
  99.  
Success #stdin #stdout 3.99s 540160KB
comments (?)
stdin 
Standard input is empty
stdout 
variants: 966730
https://ideone.com/MV2VDS
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!