fork download 
// 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 лишних \")\" и %d лишних \"(\"\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]-1; n=R[pr]-R[pr+1]; pr-=2; }
            for(int j=0;j<n;j++) putchar(c);
        }
        putchar('\n');
        */
    }
    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) { left(p-2,0); left_dec(p,i); }
        }    
    }
    void left_dec(int p,int i) {
        L[i+1]++; L[p+1]--; left(p-2);
        if (L[p+1]>0) {
            int j=i; while(j>=0 && L[j+1]>=L[j]) j-=2;
            if (j>=0) left_dec(p,j);
        }
        L[i+1]--; L[p+1]++;
    }
    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;
}
Success #stdin #stdout 0.01s 15304KB
comments (?)
stdin 
Standard input is empty
stdout 
"()(())(()())(())((())()))))))()))))(((((()(((((())(()())((())(()()))" - 9 лишних ")" и 9 лишних "("
count=966730
https://ideone.com/C4L2Cu
language:
C++ (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!