AOJ 2428 Lost Number

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2428

穴あきの数式が与えられる。穴に適当な文字を入れて計算結果を最大化せよ。

解法

構文解析はエラーが起こったらメッセージ付きの例外を投げる実装にするのが一番実装もデバッグも楽だと思う。

文字の入れ方は高々 {7^{5}}通りしかないのでパーサを書いて全探索する。()の間には<operator>がちょうど1個だけ入るので事前にチェックする。

inline bool valid(int x){ return 0<=x && x<1024; }
 
char e[128];
 
inline bool ispm(char c){
    return c=='+' || c=='-';
}
inline bool ispd(char c){
    return c=='*' || c=='/';
}
 
int num(char* &p);
int fac(char* &p);
int term(char* &p);
int expr(char* &p);
 
int num(char* &p){
    int res = 0;
    if(isdigit(*p)){
        ;
    }else{
        throw "num begin";
    }
    while (isdigit(*p)){
        res<<=1;
        res+=*p-'0';
        p++;
    }
 
    if(*p=='\0' || *p==')' || ispm(*p) || ispd(*p)){
        ;
    }else{
        throw "num end";
    }
 
    if(!valid(res)) throw "overflow";
    return res;
}
 
int fac(char* & p){
    int res = 0;
    if(*p=='(' || isdigit(*p)){
        ;
    }else{
        throw "fac begin";
    }
 
    if(*p=='('){
        p++;
        res += expr(p);
        p++;
    }else if(isdigit(*p)){
        res += num(p);
    }
    if(*p=='\0' || *p==')' || ispm(*p) || ispd(*p)){
        ;
    }else{
        throw "fac end";
    }
 
    if(!valid(res)) throw "overflow";
    return res;
}
 
int term(char* & p){
    int res;
    if(*p=='(' || isdigit(*p)){
        res = fac(p);
    }else{
        throw "term begin";
    }
    while(1){
        if(*p=='*'){
            p++;
            res *= fac(p);
        }else if(*p=='/'){
            p++;
            res /= fac(p);
        }else if(*p=='\0' || *p==')' || *p=='+' || *p=='-'){
            break;
        }else{
            throw "term end";
        }
    }
 
    if(!valid(res)) throw "overflow";
    return res;
}
 
int expr(char* & p){
    int res;
    if(*p=='(' || isdigit(*p)){
        res=term(p);
    }else{
        throw "exp begin";
    }
 
    while(1){
        if(*p=='+'){
            p++;
            res += term(p);
        }else if(*p=='-'){
            p++;
            res -= term(p);
        }else if(*p=='\0' || *p==')' || ispm(*p) || ispd(*p)){
            break;
        }else{
            throw "exp end";
        }
        if(!valid(res)) throw "overflow";
    }
 
    return res;
}
 
bool check(char* e){
    stack<int> s;
    for(int i=0;e[i];i++){
        if(e[i]=='(')s.push(i);
        else if(e[i]==')'){
            if(s.size()){
                int j=s.top();
                s.pop();
                int depth=0;
                bool ok=false;
                loop(k,j,i+1){
                    if((ispm(e[k]) || ispd(e[k])) && depth==1) ok=true;
                    else if(e[k]=='(') depth++;
                    else if(e[k]==')') depth--;
                }
                if(!ok) return false;
            }else{
                return false;
            }
        }
    }
    return s.size()==0;
}
 
int solve(){
    int ps[10];
    int c=0;
    for(int i=0;e[i];i++){
        if(e[i]=='.'){
            ps[c++]=i;
        }
    }
    int fine=1;
    rep(i,c)fine*=7;
    int ans=-1;
    rep(mask,fine){
        int k=mask;
        rep(i,c){
            int p=k%7;
            static const char cs[]="1-(*0+)";
            e[ps[i]]=cs[p];
            k/=7;
        }
        if(!check(e)) continue;
        try{
            auto it=e;
            ans=max(ans,expr(it));
            // cout << e << " : " << "ok" << endl;
        }catch(const char* c){
            // cout << e << " : " << c << endl;
        }
    }
    return ans;
}
 
int main(){
    scanf("%s",e);
    cout << solve() << endl;
}