読者です 読者をやめる 読者になる 読者になる

るくすの日記 ~ Out_Of_Range ~

主にプログラミング関係

AOJ 0041 Expression

[問題文]
AIZU ONLINE JUDGE



[解法]
構文解析 + 全探索


めんどくさそうだったので放置してた問題。

カタラン数C[3] = 5なので、括弧のつけ方はすべて列挙しても問題ない。あとは数字の並び 4! 通りと 演算子 3^3 通りと 括弧のつけ方C[3]通りを試して構文解析すればおk


眠い中書いたのでいろいろひどい。

typedef string::const_iterator State;

const string C[5] = {"((a x b) x c) x d",
		     "(a x (b x c)) x d",
		     "a x ((b x c) x d)",
		     "a x (b x (c x d))",
		     "(a x b) x (c x d)"};

const char P[3] = {'+','-','*'};

int term(State &now);
int expression(State &now);
int fact(State &now);
int number(State &now);

string solve(int a,int b,int c,int d){
  for(int i = 0; i < 5; i++){
    string s = C[i];
    s[s.find("a")] = '0' + a;
    s[s.find("b")] = '0' + b;
    s[s.find("c")] = '0' + c;
    s[s.find("d")] = '0' + d;
    for(int p1 = 0; p1 < 3; p1++){
      for(int p2 = 0; p2 < 3; p2++){
	for(int p3 = 0; p3 < 3; p3++){
	  string s2 = s;
	  s2[s2.find("x")] = P[p1];
	  s2[s2.find("x")] = P[p2];
	  s2[s2.find("x")] = P[p3];
	  string s3 = s2;
	  s3.erase(remove(all(s3),' '),s3.end());
	  State now = s3.begin();
	  int ans = expression(now);
	  if(ans == 10) return s2;
	}
      }
    }
  }
  return "";
}

int main(){
  int a = 0,b = 0,c = 0,d = 0;
  while(scanf("%d %d %d %d",&a,&b,&c,&d),a|b|c|d){
    int st[4] = {a,b,c,d};
    sort(st,st + 4);
    bool exist = false;
    string res;
    do{
      res = solve(st[0],st[1],st[2],st[3]);
      if(res != ""){
	exist = true;
	break;
      }
    }while(next_permutation(st,st + 4));
    if(exist){
      string r = "(" + res + ")";
      cout<<r<<endl;
    }
    else puts("0");
  }
}

int term(State &now){
  int ret = fact(now);
  while(true){
    if(*now == '*'){
      now++;
      ret *= fact(now);
    }else break;
  }
  return ret;
}

int expression(State &now){
  int ret = term(now);
  while(true){
    if(*now == '+'){
      now++;
      ret += term(now);
    }else if(*now == '-'){
      now++;
      ret -= term(now);
    }else break;
  }
  return ret;
}

int fact(State &now){
  if(*now == '('){
    now++;
    int ret = expression(now);
    now++;
    return ret;
  }else{
    return number(now);
  }
}

int number(State &now){
  int ret = 0;
  while('0' <= (*now) && (*now) <= '9'){
    ret *= 10;
    ret += *now - '0';
    now++;
  }
  return ret;
}