fork(2) download 
  1. #include <iostream>
  2. #include <set>
  3. #include <string>
  4.  
  5. void remove_redundant_opening_brackets(const std::string& s, size_t end, std::set<std::string>& output)
  6. {
  7.    int level = 0;
  8.    for (size_t i = end; i--;)
  9.    {
  10.       if (s[i] == ')')
  11.       {
  12.          ++level;
  13.       }
  14.       else if (s[i] == '(' && --level < 0)
  15.       {
  16.          char last = 0;
  17.          for (size_t j = i; j < s.length(); ++j)
  18.          {
  19.             if (s[j] == '(' && last != '(')
  20.             {
  21.                remove_redundant_opening_brackets(std::string(s).erase(j, 1), i, output);
  22.             }
  23.             last = s[j];
  24.          }
  25.          return;
  26.       }
  27.    }
  28.    output.insert(s);
  29. }
  30.  
  31. void remove_redundant_brackets(const std::string& s, size_t begin, std::set<std::string>& output)
  32. {
  33.    int level = 0;
  34.    for (size_t i = begin; i < s.length(); ++i)
  35.    {
  36.       if (s[i] == '(')
  37.       {
  38.          ++level;
  39.       }
  40.       else if (s[i] == ')' && --level < 0)
  41.       {
  42.          char last = 0;
  43.          for (size_t j = 0; j <= i; ++j)
  44.          {
  45.             if (s[j] == ')' && last != ')')
  46.             {
  47.                remove_redundant_brackets(std::string(s).erase(j, 1), i, output);
  48.             }
  49.             last = s[j];
  50.          }
  51.          return;
  52.       }
  53.    }
  54.    remove_redundant_opening_brackets(s, s.length(), output);
  55. }
  56.  
  57. std::set<std::string> remove_redundant_brackets(const std::string& s)
  58. {
  59.    std::set<std::string> output;
  60.    remove_redundant_brackets(s, 0, output);
  61.    return output;
  62. }
  63.  
  64. int main()
  65. {
  66.    const auto s = "(a)())()))((b(b)";
  67.  
  68.    for (auto&& s : remove_redundant_brackets(s))
  69.    {
  70.       std::cout << s << std::endl;
  71.    }
  72. }
  73.  
  74.  
Success #stdin #stdout 0s 16064KB
comments (?)
stdin 
Standard input is empty
stdout 
(a(()))(bb)
(a(()))b(b)
(a()())(bb)
(a()())b(b)
(a())()(bb)
(a())()b(b)
(a)(())(bb)
(a)(())b(b)
(a)()()(bb)
(a)()()b(b)
https://ideone.com/8jWHts
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!