AOJ 2255 6/2(1+2)

方針は、演算子でまず区切って、区切ったLHSとRHSを再帰的に区切っていく。 eagletmtさんの方針とほぼ同じで、詳しくかかれていたのでそちらを参照のこと。

http://eagletmt.github.io/contests/blog/aoj-2255/

#include <iostream>
#include <vector>
#include <set>
#include <numeric>
#include <algorithm>
#include <cctype>
#include <string>
#include <sstream>

using namespace std;

// for debug.
template<class T>
ostream& operator<<(ostream& os,const vector<T>& vec){
    for(int i=0;i<vec.size();i++){
        os << vec[i];
        if(i != vec.size()-1) os << " ";
    }
    return os;
}

int to_int(string s){
    stringstream ss;
    ss << s;
    int ret;
    ss >> ret;
    return ret;
}

set<int> eval(const string& str){
    vector<string> terms;
    vector<char> ops;
    for(size_t i=0;i<str.size();i++){
        if(isdigit(str[i])){
            string num = "";
            for(;i<str.size() and isdigit(str[i]);i++){
                num += str[i];
            }
            i--;
            terms.push_back(num);
        }else if(str[i] == '('){
            int p = 0;
            int  from = i,to = -1;
            for(;i<str.size();i++){
                if(str[i] == '('){
                    p++;
                }else if(str[i] == ')'){
                    if(p == 1){
                        to = i;
                        break;
                    }
                    p--;
                }
            }
            terms.push_back(str.substr(from,to-from+1));
        }else{
            ops.push_back(str[i]);
        }
    }
    //cerr << "terms:" << terms << endl;
    //cerr << "ops:" << ops << endl;
    set<int> ret;
    if(terms.size() == 1){
        string now = terms[0];
        if(now[0] == '('){
            ret = eval(now.substr(1,now.size()-2));
        }else{
            ret.insert(to_int(now));
        }
        return ret;
    }else{
        // look
        for(size_t i=0;i<ops.size();i++){
            string lhs,rhs;
            for(size_t j=0;j<ops.size();j++){
                if(i >= j){
                    lhs += terms[j];
                    if(i != j){
                        lhs += ops[j];
                    }
                }else{
                    rhs += terms[j];
                    rhs += ops[j];
                }
            }
            rhs += terms.back();
            //cerr << "lhs:" << lhs << endl;
            //cerr << "rhs:" << rhs << endl;
            set<int> le = eval(lhs);
            set<int> re = eval(rhs);
            for(set<int>::iterator lit=le.begin();lit!=le.end();++lit){
                for(set<int>::iterator rit=re.begin();rit!=re.end();++rit){
                    if(ops[i] == '+'){
                        ret.insert(*lit + *rit);
                    }else if(ops[i] == '-'){
                        ret.insert(*lit - *rit);
                    }else if(ops[i] == '*'){
                        ret.insert(*lit * *rit);
                    }else if(ops[i] == '/'){
                        if(*rit == 0) continue;
                        ret.insert(*lit / *rit);
                    }
                }
            }
        }
        return ret;
    }
}

int main(){
    while(true){
        string s;
        cin >> s;
        if(s == "#") break;
        set<int> ret = eval(s);
        cout << ret.size() << endl;
    }
    return 0;
}