SGU 182 Open the brackets

有啟發性的一題，建議各位想想後再看題解

給一邏輯式，轉成不含括號的等價邏輯式

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

精隨

因為只有十個變數，所以可以枚舉真值表

1024*跑過該式2048 = 2*10^6

如果是true，那就印出a&!b&c這樣

中間則用 || 串起來

長度為10*1024*3+1024 = 31XXX 這樣 < 32768

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

我把它想成是一塊一塊的東西，中間連接起來

所以就用有點像DFS的東西去遞迴

雖然co完後，bug一堆（寫了兩個小時＝＝"）

而且一塊一塊還要有等級的需別，才不會弄錯

大致上是用符號的priority分級，可以參考參考我的 code

//By momo
#include<cstdio>
#include<algorithm>
using namespace std;

char s[3000];
int app[10], ans[10], an, comb, p;

bool This();
bool dfs(int ty);

int main(){
    scanf("%s", s);
    for(int i = 0; s[i]; i++)
        if(s[i] >= 'a' && s[i] <= 'j') app[s[i]-'a'] = 1;
   
    for(int i = 0; i < 10; i++)
        if(app[i] != 0) ans[an] = i, app[i] = an++;
   
    bool fir = 1;
    for( ; comb < (1<<an); comb++){
        p = 0;
        if(!dfs(0)) continue;
        if(!fir) printf("||");
        for(int i = 0; i < an; i++){
            if(i != 0) printf("&");
            if((comb | (1<<i)) != comb) printf("!");
            printf("%c", ans[i]+'a');
        }
        fir = 0;
    }
    if(fir) printf("a<=>!a");
    puts("");
}

bool This(){
    bool fl = 0;
    while(s[p] == '!') fl ^= 1, p++; p++;
    if(s[p-1] == '(') return fl^dfs(1);
    else return fl ^ (1 & (comb >> app[s[p-1]-'a']));
}

bool dfs(int ty){
    bool now = This();
    while(1){
        if(s[p] == 0) return now;
        if(ty == 1){
            if(s[p] == ')'){
                p += 1;
                return now;
            }
        }
        if(ty == 2){
            if(s[p] == '<' || s[p] == '=' ||
               s[p] == '#' || s[p] == '|' || s[p] == ')')
                return now;
        }
        if(s[p] == '&'){
            p += 1;
            now = (now & This());
            continue;
        }
        if(s[p] == '|'){
            p += 2;
            now = (now | dfs(2));
            continue;
        }
        if(s[p] == '<'){
            p += 3;
            now = (now == dfs(2));
            continue;
        }
        if(s[p] == '='){
            p += 2;
            now = ((!now) | dfs(2));
            continue;
        }
        if(s[p] == '#'){
            p += 1;
            now = (now ^ dfs(2));
            continue;
        }
    }
}