2269:Friends

keyword

集合　構文解析　C

概要

和と差と積の入った集合演算をする問題。
集合の個数が26個以下なのでビットで扱う。構文解析の部分は、よくあるBNFで定義してから実装した。

int n, p;
char str[300];

int expr();
int term();
int fact();
int set();

int expr(){
    int a,b;
    char op;
    if(!str[p]) return -1;
    a = term();
    while( op = str[p++] ){
        if(op=='+'){
            b = term();
            a |= b;
        }
        else if(op=='-'){
            b = term();
            a &= ~b;
        }
        else break;
    }
    p--;
    return a;
}

int term(){
    int a, b;
    char op;
    if(!str[p]) return -1;
    a = fact();
    while( (op=str[p++]) == '*'){
        b = fact();
        a &= b;
    }
    p--;
    return a;
}

int fact(){
    int a;
    if(str[p] == '('){
        p++;
        a = expr();
        if(str[p]==')'){
            p++;
            return a;
        }
        else{
            return -1;
        }
    }
    a = set();
    return a;
}

int set(){
    int a=0;
    if(str[p++]=='{'){
        while('A'<=str[p]&&str[p]<='Z'){
            a |= 1<<(str[p++]-'A');
        }
        p++;
        return a;
    }
    return -1;
}

int main(){
    int ans,i;
    while(scanf("%s\n",str)!=EOF){
        p = 0;
        ans = expr();
        putchar('{');
        for(i=0;i<26;i++)if((ans>>i)&1)
            putchar(i+'A');
        puts("}");
    }
}