1

Topic: 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. For example, "(a) ()) ())) ((b (b)" - three superfluous ")" and two superfluous "("> (a (())) b (b) (a (())) (bb) (a () ()) b (b) (a () ()) (bb) (a ()) () b (b) (a ()) () (bb) (a) (()) b (b) (a) (()) (bb) (a) () () b (b) (a) () () (bb) Quickly somehow so #include <stdio.h> #include <string.h> #include <set> #include <string> using std:: string; struct Check {const char *text; int len; char* mask; typedef std:: set <string> variants_t; typedef variants_t:: iterator variants_it; variants_t variants; int check () {int level=0, rm_close=0, i, r2=0; char c; for (i=0; c=text [i]; i ++) {if (c == ' (') level ++; if (c == ') ') {if (level> 0) level-; else {rm_close ++; mask [i] =c;}}} for (int l2=0; i> =0; i-) {c=text [i]; if (c == ') ') l2 ++; if (c == ' (') {if (l2> 0) l2-; else {r2 ++; mask [i] =c;}}} if (rm_close || level) printf ("\" %s \"- %d superfluous \") \"and %d superfluous \" (\"\n %s\n\n", text, rm_close, level, mask); return rm_close+level;} void insert () {string s; for (int i=0; i <len; i ++) if (text [i]! =mask [i]) s + = text [i]; variants.insert (s);} void right (int pos) {insert (); while (pos> =0 && mask [pos]! = ' (') pos-; if (pos <0) return; char type=mask [pos]; mask [pos] = ' '; for (int i=pos+1; i <len; i ++) {if (mask [i] == ' ' && text [i] == type) {mask [i] =type; right (i-1); mask [i] = ' ';}} mask [pos] =type;} void left (int pos) {right (len-1); while (pos <len && mask [pos]! = ') ') pos ++; if (pos> =len) return; char type=mask [pos]; mask [pos] = ' '; for (int i=pos-1; i> =0; i-) {if (mask [i] == ' ' && text [i] == type) {mask [i] =type; left (pos+1); mask [i] = ' ';}} mask [pos] =type;} void find () {variants.clear (); left (0);} void show_variants () {int i=0; }}; int main (int argc, char ** argv) {enum {mask_max=64}; char mask [mask_max]; const char* list [] = {"(a) ()) ())) ((b (b)", 0}; for (const char ** s=list; *s; s ++) {Check c; c.text =*s; c.len=strlen (*s); c.mask=mask; memset (mask, ' ', c.len); mask [c.len] =0; if (c.check ()) c.show_variants ();} return 0;} "(a) ()) ())) ((b (b)" - 3 superfluous ")" and 2 superfluous "("))) ((1 (a (())) (bb) 2 (a (())) b (b) 3 (a () ()) (bb) 4 (a () ()) b (b) 5 (a ()) () (bb) 6 (a ()) () b (b) 7 (a) (()) (bb) 8 (a) (()) b (b) 9 (a) () () (bb) 10 (a) () () b (b)

2

Re: Re: Correction of brackets

Hello, Kodt, you wrote: Hello, kov_serg, you wrote: _>> Quickly somehow so _>>#include <set> Here it strains. After all it is easy to create such dial-up which gives combinatorial explosion: k open parentheses, then 2k closing, and is mandatory not parenthesis characters in between all. It is necessary to delete k from 2k brackets that, obviously, gives a C (2k, k) answer variants. Slightly  and the jamb corrected. #include <stdio.h> #include <string.h> #include <set> #include <string> using std:: string; struct Check {const char *text; int len, count; char* mask; typedef std:: set <string> variants_t; typedef variants_t:: iterator variants_it; variants_t variants; int check () {int level=0, rm_close=0, i, r2=0; char c; for (i=0; c=text [i]; i ++) {if (c == ' (') level ++; if (c == ') ') {if (level> 0) level-; else {rm_close ++; mask [i] =c;} }} for (int l2=0; i> =0; i-) {c=text [i]; if (c == ') ') l2 ++; if (c == ' (') {if (l2> 0) l2-; else {r2 ++; mask [i] =c;}}} if (rm_close || level) printf ("\" %s \"- %d superfluous \") \"and %d superfluous \" (\"\n %s\n\n", text, rm_close, level, mask); return rm_close+level;} void insert () {count ++; string s; for (int i=0; i <len; i ++) if (text [i]! =mask [i]) s + = text [i]; variants.insert (s);} void right (int pos) {insert (); for (; pos> =0; pos-) {while (pos> =0 && mask [pos]! = ' (') pos-; if (pos <0) return; char type=mask [pos]; mask [pos] = ' '; int d=0; for (int i=pos+1; i <len && mask [i]! =type; i ++) {if (mask [i] == ' ' && text [i] == type) {if (d } void left (int pos) {right (len-1); for (; pos <len; pos ++) {while (pos <len && mask [pos]! = ') ') pos ++; if (pos> =len) return; char type=mask [pos]; mask [pos] = ' '; int d=0; for (int i=pos-1; i> =0 && mask [i]! =type; i-) {if (mask [i] == ' ' && text [i] == type) {if (d) {mask [i] =type; left (pos+1); mask [i] = ' ';}} else d=1;} mask [pos] =type;}} void find () {count=0; variants.clear (); left (0);} void show_variants () {int i=0; find (); for (variants_it it=variants.begin (); it! =variants.end (); ++ it) {printf ("%-6d%s\n", ++ i, it-> c_str ());} int size=variants.size (); printf ("count = % d k = %. 1f\n", count, (double) count/size);} }; int main (int argc, char ** argv) {enum {mask_max=128}; char mask [mask_max]; const char* list [] = {"(a) ()) ())) ((b (b)","() (()) (() ()) ((() ()))))))) ((((((() (()) (() ()) ((())()","())","(())))","(()))))","(((()))))))","((((()))))))))","((((()))))))))))","(((((()))))))))))))","(((((((()))))))))))))))","(((((((( It would be more preferable to make the generator (let even with O (n) internal storage, where n - length of a line), sequentially producing answers. So here also there are two counters L * R g ++ a.cpp &&. / /a.out | grep-B 2-A 2 count 7 (a) () () (bb) 8 (a) () () b (b) count=10 k=1.2 "() (()) (()() ((() ()))))))) ((((((() (()) (() ()) ((())()" - 6 superfluous ")" and 6 superfluous "(")))))) ((((((- 12749 () (()) (() ()) ((())() (() ()) (() ()) ((() ()) 12750 () (()) (()() ((() ()) () (()) (()() ((() ()) count=719104 k=56.4 "())" - 1 superfluous")" and 0 superfluous "(") 1 () count=1 k=1.0" (()))) "- 2 superfluous")" and 0 superfluous ")) 1 (()) count=1 k=1.0" ((()))))) "- 3 superfluous")" and 0 superfluous "("))) 1 ((())) count=1 k=1.0" (((()))))))) "- 4 superfluous")" and 0 superfluous ")))) 1 ((())) count=1 k=1.0" (((())))))))) "- 5 superfluous")" and 0 superfluous "))))) 1 ((((())))) count=1 k=1.0" (((((()))))))))))) "- 6 superfluous")" and 0 superfluous "))))) ((()))))) count=1 k=1.0 "((((((())))))))))))))" - 7 superfluous ")" and 0 superfluous"))))))) 1 (((((()))))) count=1 k=1.0 "((((((()))))))))))))))" - 8 superfluous ")" and 0 superfluous")))))))) 1 (((((((()))))))) count=1 k=1.0 "((((((((())))))))) ())))))))))" - 9 superfluous ")" and 0 superfluous "("))))))))) - 9 (((((((())))))) ()) 10 ((((((((()))))))) () count=512 k=51.2 "(a (b (c (d (e (f (g (h (i) j) k) l) m) n) o) p) q) r) s) t) u) v) w) x) y) z)" - 9 superfluous ")" and 0 superfluous "(")))))))

3

Re: Re: Correction of brackets

Hello, kov_serg, you wrote: With  overshot #include <stdio.h> #include <string.h> #include <set> #include <string> using std:: string; struct Check {const char *text; int len, count; char* mask; typedef std:: set <string> variants_t; typedef variants_t:: iterator variants_it; variants_t variants; int check () {int level=0, rm_close=0, i, r2=0; char c; for (i=0; c=text [i]; i ++) {if (c == ' (') level ++; if (c == ') ') {if (level> 0) level-; else {rm_close ++; mask [i] =c;}}} for (int l2=0; i> =0; i-) {c=text [i]; if (c == ') ') l2 ++; if (c == ' (') {if (l2> 0) l2-; else {r2 ++; mask [i] =c;}}} if (rm_close || level) printf ("\" %s \"- %d superfluous \") \"and %d superfluous \" (\"\n %s\n\n", text, rm_close, level, mask); return rm_close+level;} void insert () {count ++; string s; for (int i=0; i <len; i ++) if (text [i]! =mask [i]) s + = text [i]; variants.insert (s);} void right (int pos) {insert (); for (; pos> =0; pos-) {while (pos> =0 && mask [pos]! = ' (') pos-; if (pos <0) return; char type=mask [pos]; mask [pos] = ' '; int i=pos+1; while (i <len && (mask [i] == ' ' && text [i] == type)) i ++; for (; i <len && mask [i]! =type; i ++) {if (mask [i] == ' ' && text [i] == type) {mask [i] =type; right (i-1); mask [i] = ' ';}} mask [pos] =type;} } void left (int pos) {right (len-1); for (; pos <len; pos ++) {while (pos <len && mask [pos]! = ') ') pos ++; if (pos> =len) return; char type=mask [pos]; mask [pos] = ' '; int i=pos-1; while (i> =0 && (mask [i] == ' ' && text [i] == type)) i-; i ++; for (; i> =0 && mask [i]! =type; i-) {if (mask [i] == ' ' && text [i] == type) {mask [i] =type; left (pos+1); mask [i] = ' ';}} mask [pos] =type;}} void find () {count=0; variants.clear (); left (0);} void show_variants () {int i=0; find (); for (variants_it it=variants.begin (); it! =variants.end (); ++ it) {printf ("%-6d%s\n", ++ i, it-> c_str ());} int size=variants.size (); printf ("count = % d k = %. 1f\n", count }; int main (int argc, char ** argv) {enum {mask_max=128}; char mask [mask_max]; const char* list [] = {"(a) ()) ())) ((b (b)","() (()) (() ()) ((() ()))))))) ((((((() (()) (() ()) ((())()","())","(())))","(()))))","(((()))))))","((((()))))))))","((((()))))))))))","(((((()))))))))))))","(((((((()))))))))))))))","(((((((( g ++ a.cpp &&. / /a.out | grep-A 2-B 2 count 9 (a) () () (bb) 10 (a) () () b (b) count=38 k=3.8 "() (()) (() ()) ((())())))))) ((((((() (()) (() ()) ((())()" - 6 superfluous ")" and 6 superfluous "(")))))) ((((((- 12749 () (()) (() ()) ((())() (() ()) (() ()) ((() ()) 12750 () (()) (()() ((() ()) () (()) (()() ((() ()) count=3068064 k=240.6 "())" - 1 superfluous")" and 0 superfluous "(") 1 () count=2 k=2.0" (()))) "- 2 superfluous")" and 0 superfluous ")) 1 (()) count=4 k=4.0" ((()))))) "- 3 superfluous")" and 0 superfluous "("))) 1 ((())) count=8 k=8.0" (((()))))))) "- 4 superfluous")" and 0 superfluous ")))) 1 ((())) count=16 k=16.0" (((())))))))) "- 5 superfluous")" and 0 superfluous "))))) 1 ((((())))) count=32 k=32.0" (((((()))))))))))) "- 6 superfluous")" and 0 superfluous "))) (((((()))))) count=64 k=64.0 "((((((())))))))))))))" - 7 superfluous ")" and 0 superfluous "("))))))) 1 ((((((())))))) count=128 k=128.0 "(((((((())))))))))))))))" - 8 superfluous ")" and 0 superfluous")))))))) 1 ((((((())))))) count=256 k=256.0 "(((((((()))))))) ())))))))))" - 9 superfluous ")" and 0 superfluous"))))))))) - 9 (((((((())))))) ()) 10 ((((((((()))))))) () count=19683 k=1968.3 "(a (b (c (d (e (f (g (h (i) j) k) l) m) n) o) p) q) r) s) t) u) v) w) x) y) z)" - 9 superfluous ")" and 0 superfluous "("))))

4

Re: Re: Correction of brackets

Hello, Kodt, you wrote: Not, I mean here that. You use set <string> variants not simply for output buffering, and for elimination of counterparts. For example, the line "())" can be corrected two methods:" (_) "And" () _ ", where _ - a removal place. Yes it not consider symmetry which can to be.> If we submit on an input of algorithm a line in length of 45 brackets, - we receive With (30,15) = 155 million variants in length of 30 brackets. At first, we  to wait, while the first answers appear on an output. (And it I still spared, - and we take a line of 20+40 brackets, there already will be 137 ) Secondly, it  storage. Thirdly, without counterparts - if we add a real amount of variants much less outside characters - too will be much less. So, for example, the line only from brackets gives exactly one variant. And here for the sake of it it will be necessary to thresh so much time? Or I inattentively read your code? Yes I as usual hastened. It was possible to consider is better symmetry of expression. Approximately so #include <stdio.h> #include <string.h> #include <set> #include <string> using std:: string; struct Check {const char *text; int len, count; char* mask; typedef std:: set <string> variants_t; typedef variants_t:: iterator variants_it; variants_t variants; int check () {int level=0, rm_close=0, i, r2=0; char c; for (i=0; c=text [i]; i ++) {if (c == ' (') level ++; if (c == ') ') {if (level> 0) level-; else {rm_close ++; mask [i] =c;}}} for (int l2=0; i> =0; i-) {c=text [i]; if (c == ') ') l2 ++; if (c == ' (') {if (l2> 0) l2-; else {r2 ++; mask [i] =c;}}} if (rm_close || level) printf ("\" %s \"- %d superfluous \") \"and %d superfluous \" (\"\n %s\n\n", text, rm_close, level, mask); return rm_close+level;} void insert () {count ++; string s; for (int i=0; i <len; i ++) if (mask [i] == ' ') s + = text [i]; variants.insert (s);} void right (int pos) {insert (); for (; pos> =0; pos-) {while (pos> =0 && mask [pos]! = ' (') pos-; if (pos <0) return; char type=mask [pos]; mask [pos] = ' '; int i=pos+1; for (int j=i; j <len; j ++) {if (mask [j]! = ' ' || text [j]! =type) break; i=j+1;} for (; i <len && mask [i]! =type; i ++) {if (mask [i] == ' ' && text [i] == type) {for (int j=i+1; j <len; j ++) {if (mask [j]! = ' ' || text [j]! =type) break; i=j;} mask [i] =type; right (i-1); mask [i] = ' ';}} mask [pos] =type;}} void left (int pos) {right (len-1); for (; pos <len; pos ++) {while (pos <len && mask [pos]! = ') ') pos ++; if for (; i> =0 && mask [i]! =type; i-) {if (mask [i] == ' ' && text [i] == type) {for (int j=i-1; j> =0; j-) {if (mask [j]! = ' ' || text [j]! =type) break; i=j;} mask [i] =type; left (pos+1); mask [i] = ' ';}} mask [pos] =type;}} void shift () {char type = ') '; for (int i=1; i <len; i ++) {if (mask [i] == type) {int k=i; for (int j=i-1; j> =0; j-) {if (mask [j]! = ' ' || text [j]! =type) break; k=j;} mask [i] = ' '; mask [k] =type;}} type = ' ('; for (int i=len-2; i> =0; i-) {if (mask [i] == type) {int k=i; for (int j=i+1; j <len; j ++) {if (mask [j]! = '' void show_variants () {int i=0; find (); for (variants_it it=variants.begin (); it! =variants.end (); ++ it) {printf ("%-6d%s\n", ++ i, it-> c_str ());} int size=variants.size (); printf ("count = % d k = %. 1f%s\n", count, (double) count/size, count! =size? "PROBLEM": "");} }; int main (int argc, char ** argv) {enum {mask_max=128}; char mask [mask_max]; const char* list [] = {"(a) ()) ())) ((b (b)","() (()) (() ()) ((() ()))))))) ((((((() (()) (() ()) ((())()","())","(())))","(()))))","(((()))))))","((((()))))))))","((((()))))))))))","(((((()))))))))))))","(((((((()))))))))))))))","(((((((( g ++ a.cpp &&./a.out |grep count count=10 k=1.0 count=58566 k=1.0 count=1 k=1.0 count=1 k=1.0 count=1 k=1.0 count=1 k=1.0 count=1 k=1.0 count=1 k=1.0 count=1 k=1.0 count=1 k=1.0 count=10 k=1.0 count=48620 k=1.0 It is necessary to prove that anywhere  and it is possible set to throw out at once to deduce in insert ()

5

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. For example, "(a) ()) ())) ((b (b)" - three superfluous ")" and two superfluous "("> (a (())) b (b) (a (())) (bb) (a () ()) b (b) (a () ()) (bb) (a ()) () b (b) (a ()) () (bb) (a) (()) b (b) (a) (()) (bb) (a) () () b (b) (a) () () (bb) #include <stdio.h> #include <string.h> struct Check {const char *text; int len, count; char* mask; int check () {int level=0, rm_close=0, i, r2=0; char c; for (i=0; c=text [i]; i ++) {if (c == ' (') level ++; if (c == ') ') {if (level> 0) level-; else {rm_close ++; mask [i] =c;}}} for (int l2=0; i> =0; i-) {c=text [i]; if (c == ') ') l2 ++; if (c == ' (') {if (l2> 0) l2-; else {r2 ++; mask [i] =c;}}} if (rm_close || level) printf ("\" %s \"- %d superfluous \") \"and %d superfluous \" (\"\n", text, rm_close, level); return rm_close+level;} void print () {printf ("%-6d", ++ count); for (int i=0; i <len; i ++) if (mask [i] == ' ') printf ("%c", text [i]);//printf ("- | %s |", mask); printf ("\n");} void right (int pos) {print (); for (; pos> =0; pos-) {while (pos> =0 && mask [pos]! = ' (') pos-; if (pos <0) return; char type=mask [pos]; mask [pos] = ' '; int i=pos+1; for (int j=i; j <len; j ++) {if (mask [j]! = ' ' || text [j] for (; i <len && mask [i]! =type; i ++) {if (mask [i] == ' ' && text [i] == type) {for (int j=i+1; j <len; j ++) {if (mask [j]! = ' ' || text [j]! =type) break; i=j;} mask [i] =type; right (i-1); mask [i] = ' ';}} mask [pos] =type;}} void left (int pos) {right (len-1); for (; pos <len; pos ++) {while (pos <len && mask [pos]! = ') ') pos ++; if (pos> =len) return; char type=mask [pos]; mask [pos] = ' '; int i=pos-1; for (int j=i; j> =0; j-) {if (mask [j]! = ' ' || text [j]! =type) break; i=j-1;} for (; i> =0 && mask [i]! =type; i-) {if (mask [i] == ' ' && text [i] == type) {for (int j=i-1; j } void ground_state () {char type = ') '; for (int i=1; i <len; i ++) {if (mask [i] == type) {int k=i; for (int j=i-1; j> =0; j-) {if (mask [j]! = ' ' || text [j]! =type) break; k=j;} mask [i] = ' '; mask [k] =type;}} type = ' ('; for (int i=len-2; i> =0; i-) {if (mask [i] == type) {int k=i; for (int j=i+1; j <len; j ++) {if (mask [j]! = ' ' || text [j]! =type) break; k=j;} mask [i] = ' '; mask [k] =type;}}} void show_variants () {ground_state (); count=0; left (0); printf ("variants count = % d\n", count);} }; int main (int argc, char ** argv) {enum {mask_len=128}; char mask [mask_len+1]; const char* list [] = {"(a) ()) ())) ((b (b)", argc> 1? argv [1: 0], 0}; for (const char ** s=list; *s; s ++) {Check c; c.text =*s; c.len=strlen (c.text); if (c.len> mask_len) continue; c.mask=mask; memset (mask, ' ', c.len); mask [c.len] =0; if (c.check() c.show_variants ();} return 0;} Like works "(a) ()) ())) ((b (b)" - 3 superfluous ")" and 2 superfluous "(" 1 (a) () () b (b) 2 (a) () () (bb) 3 (a ()) () b (b) 4 (a ()) () (bb) 5 (a () ()) b (b) 6 (a () ()) (bb) 7 (a (())) b (b) 8 (a (())) (bb) 9 (a) (()) b (b) 10 (a) (()) (bb) variants count=10

6

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 - wink {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;}}

7

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

8

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 - wink {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;//}}

9

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.

10

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

11

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 <

12

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