#### Re: Re: Correction of brackets

Hello, Kodt, you wrote: the Problem with , a head to itself broke, - how to make gracefully. It is given: a line, in which there are brackets (one type - round) and other characters. Brackets, probably, unbalanced. It is necessary: to delete the minimum quantity of brackets so that to recover balance. (Well it is simple). And to deduce all possible decisions.  I understand, the snap in avoiding duplication, and, it should be provided with algorithm, the filtration of doubles with the help, for example, std:: set is not considered the beautiful decision? Well here, for example, such decision  as beautiful? http://ideone.com/8jWHts #include <iostream> #include <set> #include <string> void remove_redundant_opening_brackets (const std::string& s, size_t end, std::set<std::string>& output) {int level = 0; for (size_t i = end; i - {if (s [i] == ') ') {++ level;} else if (s [i] == ' (' && - level <0) {char last = 0; for (size_t j = i; j <s.length (); ++ j) {if (s [j] == ' (' && last! = ' (') {remove_redundant_opening_brackets (std:: string (s).erase (j, 1), i, output);} last = s [j];} return;}} output.insert (s);} void remove_redundant_brackets (const std::string& s, size_t begin, std::set<std::string>& output) {int level = 0; for (size_t i = begin; i <s.length (); ++ i) {if (s [i] == ' (') {++ level;} else if (s [i] == ') ' && - level <0) {char last = 0; for (size_t j = 0; j <= i; ++ j) {if (s [j] == ') ' && last! = ') ') {remove_redundant_brackets (std:: string (s).erase (j, 1), i, output);} last = s [j];} return;}} remove_redundant_opening_brackets (s, s.length std:: set <std:: string> remove_redundant_brackets (const std::string& s) {std:: set <std:: string> output; remove_redundant_brackets (s, 0, output); return output;} int main () {const auto s = "(a) ()) ())) ((b (b)"; for (auto && s: remove_redundant_brackets (s)) {std:: cout <<s <<std:: endl;}}

#### Re: Re: Correction of brackets

Hello, rg45, you wrote: R> Well here, for example, such decision  as beautiful? R> http://ideone.com/8jWHts with this line try c "() (()) (()() (()) ((()) ())))))) ())))) (((((() (((((()) (() ()) ((()) (()))" g ++ aa.cpp && time. / /a.out "() (()) (() ()) (()) ((()) ())))))) ())))) (((((() (((((()) (() ()) ((()) (()))" | tail 681114 () (()) (() ()) (()) ((()) (())) (((((() ((((()))))))))) 681115 () (()) (() ()) (()) ((()) (())) (() (((()) (() ()) ((()))))) 681116 () (()) (()() (()) ((()) (())) ((() ((() (() ()) ((())))) 681117 () (()) (() ()) (()) ((( (() ())) 681122 () (()) (() ()) (()) ((()) (())) ((())) (() ()) ((()) (())) variants count=681122 real 0m0.602s user 0m0.598s sys 0m0.037s

#### Re: Re: Correction of brackets

Hello, kov_serg, you wrote: _> Hello, rg45, you wrote: R>> Well here, for example, such decision  as beautiful? R>> http://ideone.com/odUmiM _> with this line try c "() (()) (()() (()) ((()) ())))))) ())))) (((((() (((((()) (() ()) ((()) (()))" _> _> g ++ aa.cpp && time. / /a.out "() (()) (() ()) (()) ((()) ())))))) ())))) (((((() (((((()) (() ()) ((()) (()))" | tail _> 681114 () (()) (()() (()) ((()) (())) (((((() ((((()))))))))) _> 681115 () (()) (() ()) (()) ((()) (())) (() (((()) (() ()) ((()))))) _> 681116 () (()) (() ()) (()) ((()) (())) ((() ((() (() ()) ((())))) _> 681117 () (()) (() () ()() (() ()) ((() (())) _> 681122 () (()) (()() (()) ((()) (())) ((())) (() ()) ((()) (())) _> variants count=681122 _> Well so that after all was simply the sketch without any optimization. After the most cosmetic optimization at me this example is considered for 4 seconds (on ideone). Only the amount of variants at me turns out more, than at you, namely 966730. Someone from us somewhere  I Can send archive mine  if you want. http://ideone.com/MV2VDS #include <iostream> #include <unordered_set> #include <string> #include <vector> class RedundantBracketRemover {public: RedundantBracketRemover (const std:: string and s) {remove_redundant_brackets (s, 0);} const std:: vector <std:: string> and get () const {return m_output;} private: void remove_redundant_opening_brackets (const std:: string AND s, size_t end) {int balance = 0; for (size_t i = end; i - {if (s [i] == ') ') {++ balance;} else if (s [i] == ' (' && - balance <0) {char last = 0; for (size_t j = i; j <s.length (); ++ j) {if (s [j] == ' (' && last! = ' (') {auto s2 = std:: string (s).erase (j, 1); if (m_nodes.insert (s2).second) remove_redundant_opening_brackets (s2, i);} last = s [j];} return;}} m_output.push_back (s);} void remove_redundant_brackets (const std:: string AND s, size_t begin) {int balance = 0; for (size_t i = begin; i <s.length (); ++ i) {if (s [i] == ' (') {++ balance;} else if (s [i] == ') ' && - balance <0) {char last = 0; for (size_t j = 0; j <= i; ++ j) {if (s [j] == ') ' && last! = ') ') {auto s2 = std:: string (s).erase (j, 1); if (m_nodes.insert (s2).second) {remove_redundant_brackets (s2, i);}} last = s [j];} return;}} remove_redundant_opening_brackets (s, s.length ());} private: std:: vector <std:: string> m_output; std:: unordered_set <std:: string> m_nodes;}; std:: vector <std:: string> remove_redundant_brackets (const std:: string AND s) {return RedundantBracketRemover (s).get ();} int main () {const auto s = "() (()) (() ()) (()) ((()) ())))))) ())))) (((((() (((((()) (() ()) ((()) (()))"; <<variants <<std:: endl;//for (auto && s: remove_redundant_brackets (s))//{//std:: cout <<s <<std:: endl;//}}

#### Re: Re: Correction of brackets

Hello, Kodt, you wrote:. Because it is very easy to invent a line on which combinatorial explosion turns out. I already spoke above: 15 open parentheses, then 30 outside characters closing with some blob. And there and then you use set <string>. Well wrote after all already, not to disappear to good And the main thing, I experienced an essence of a problem and to a smog with it to consult purely algorithmically as it seems to me. It demands more time, certainly.

#### Re: Re: Correction of brackets

Hello, rg45, you wrote: R> Well so that after all there was simply a sketch without any optimization. After the most cosmetic optimization at me this example is considered for 4 seconds (on ideone). Only the amount of variants at me turns out more, than at you, namely 966730. Someone from us somewhere  I Can send archive mine  if you want. R> http://ideone.com/MV2VDS rewrote anew. Now is "much more correct" http://ideone.com/C4L2Cu//a3.cpp #include <stdio.h> struct Check {const char* text; int len; int *L, *R; int nl, nr, lim, count; int check () {int level, rm_close, rm_open, i; char c; nr=0; nl=0; L [0 =0; L [1 =0; R [0 =0; R [1 =0; level=0; rm_close=0; rm_open=0; c=0; for (i=0; c=text [i]; i ++) {if (c == ' (') level ++; if (c == ') ') {L [nl] ++; if (level> 0) level-; else {L [nl+1] ++; rm_close ++;}} else {if (L [nl]) {nl + = 2; if (nl+2> =lim) throw this; L [nl] =0; L [nl+1] =0;} }} rm_open=level; level=0; len=i; for (- i; i> =0; i-) {c=text [i]; if (c == ') ') level ++; if (c == ' (') {R [nr] ++; if (level> 0) level-; else R [nr+1] ++;} else {if (R [nr]) {nr + = 2; if (nl+2> =lim) throw this; R [nr] =0; R [nr+1] =0;}}} if (! L [nl]) nl - = 2; if (! R [nr]) nr - = 2; if (rm_close || rm_open) printf ("\" %s \"- %d superfluous \") \"and %d superfluous \" (\"\n", text, rm_close, rm_open); return rm_close+rm_open;} void show () {count ++;//printf ("%-6d", count); for (int pl=0, pr=nr, i=0; i <len; i ++) {int n=1; char c=text [i]; if (c == ') ') {i + = L [pl]-1; n=L [pl]-L [pl+1]; pl + = 2;} if (c == ' (') {i + = R [pr] void right (int p, int s=1) {if (s) show (); while (p> =0 && R [p+1] == 0) P - = 2; if (p> =0) {int i=p-2; while (i> =0 && R [i+1]> =R [i]) I - = 2; if (i> =0) {right (p-2,0); right_dec (p, i);}}} void right_dec (int p, int i) {R [i+1] ++; R [p+1]-; right (p-2); if (R [p+1]> 0) {int j=i; while (j> =0 && R [j+1]> =R [j]) J - = 2; if (j> =0) right_dec (p, j);} R [i+1]-; R [p+1] ++;} void left (int p, int s=1) {if (s) right (nr); while (p> =0 && L [p+1] == 0) P - = 2; if (p> =0) {int i=p-2; while (i> =0 && L [i+1]> =L [i]) I - = 2; if (i> =0) void show_variants () {count=0; left (nl); printf ("count = % d\n", count);}}; int main (int argc, char ** argv) {enum {limit=128}; int L [limit], R [limit]; const char* list [] = {"(a) ()) ())) ((b (b)",//"() (()) (() ()) (()) ((()) ())))))) ())))) (((((() (((((()) (() ()) ((()) (()))", argc> 1? argv [1: 0], 0}; for (const char ** s=list; *s; s ++) {Check c; c. L=L; c. R=R; c.lim=limit; c.text =*s; try {if (c.check() c.show_variants ();} catch (Check *) {printf ("limit exceeded - %s\n", *s);}} return 0;} g ++ a3.cpp && time. / /a.out "() (()) (()() (()) ((()) ())))))) ())))) (((((() (((((()) (() ()) ((()) (()))" | tail [code] ((((((((((()()))))) ())))) (((((() (((()) ())) ()))))) ((((((((((()()))))) ())))) (((((() (((()) () ()))))))) ((((((((((()()))))) ())))) (((((() (((()) (())))))))) ((((((((((()()))))) ))) ())))) (((((() ((((()))))))))) count=966730 real 0m0.623s user 0m0.641s sys 0m0.019s

#### Re: Re: Correction of brackets

Hello, Kodt, you wrote: It is given: a line, in which there are brackets (one type - round) and other characters. Brackets, probably, unbalanced. It is necessary: to delete the minimum quantity of brackets so that to recover balance. (Well it is simple). And to deduce all possible decisions. For example, "(a) ()) ())) ((b (b)" - three superfluous ")" and two superfluous "(" we solve to begin with the task for brackets without other characters. We count the following dynamics: number of various lines in length i on a suffix in length j with balance b also we learn to find k th line in dictionary order. We receive the decision for O (N 4). At dynamics count by greedy image we will take the first opening and first closing parenthesis. length: 8 total: 5 string #1: (()) () string #2: (() ()) () string #3: (()) () () string #4: () (()) () string #5: () () () () int length; string line; vector <vector <vector <int>>> cache; int how_many (int position, int balance, int left) {int &result = cache [position] [balance] [left]; if (result! =-1) return result; if (left == 0) return balance == 0; result = 0; for (int p = position; p <line.size (); ++ p) {if (line [p] == ' (') {result + = how_many (p + 1, balance + 1, left - 1); break;}} for (int p = position; balance> 0 && p <line.size (); ++ p) {if (line [p] == ') ') {result + = how_many (p + 1, balance - 1, left - 1); break;}} return result;} string get (string AND answer, int position, int balance, int length, int k) {if (length == 0) return answer; int result = 0; int p = position; for (; p <line.size (); ++ p) {if (line [p] == ' (') {result + = how_many (p + 1, balance + 1, length - 1); break; else {for (int p = position; balance> 0 && p <line.size (); ++ p) {if (line [p] == ') ') {answer.push_back (') '); get (answer, p + 1, balance - 1, length - 1, k - result); break;}}} return answer;} string get (int k) {string answer = ""; return get (answer, 0, 0, length, k);} int main () {#ifndef ONLINE_JUDGE freopen ("in.txt", "r", stdin); freopen ("out.txt", "w", stdout); #endif getline (cin, line); const int n = line.size (); cache.assign (n + 1, vector <vector <int>> (n, vector <int> (n + 1,-1))); length = 0; for (int i = 0; i <n; i + = 2) {int t = how_many (0, 0, i); if (t> 0) length = i;} int total = how_many (0, 0, length); cout <<"length:" <<length <

#### Re: Re: Correction of brackets

Hello, NotImplemented, you wrote: NI> Hello, Kodt, you wrote:>> It is given: a line, in which there are brackets (one type - round) and other characters.>> Brackets, probably, unbalanced.>> It is necessary: to delete the minimum quantity of brackets so that to recover balance. (Well it is simple). And to deduce all possible decisions.>> For example, "(a) ()) ())) ((b (b)" - three superfluous ")" and two superfluous "(" NI> we solve to begin with the task for brackets without other characters. NI> we count the following dynamics: number of various lines in length i on a suffix in length j with balance b also we learn to find k th line in dictionary order. NI> we receive the decision for O (N 4). At dynamics count by greedy image we will take the first opening and first closing parenthesis. For count it is possible to calculate kol-in the left variants and to increase on kol-in right, will be much faster (in a root of times from a direct variant). (a) ()) ())) ((b (b) l ll lLL RR r L: 0/1 0/2 2/3 R: 0/1 2/2 count (L) =5 count (R) =2 5*2=10 () ()) ())) ((() l ll lLL RRr L: 0/1 0/2 2/3 R: 2/3 count (L) =5 count (R) =1 5*1=5