AOJ : 2255 - 6/2(1+2)

問題概要

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2255
日本語の問題文なので省略です.
ちなみに, 僕は 6/2(1+2) の答えは 9 だと思います.

アルゴリズム

O(10!)の単純再帰で書きました.
方法は次のような感じ.(説明下手)

ある数式文字列の中の「数字 演算子 数字」という二項演算の文字列は, 必ず計算することができます.
数式の中に, そのような文字列があれば計算して, その計算結果で置換することを繰り返します.
最終的に, 数字ひとつだけの文字列になるはずなので, これでひとつの解ができたとして, setにaddします.
あとは, setのサイズを出力するだけ.

たとえば, 6/2*(1+2) という数式の場合, 計算が可能な二項演算は,

• 6/2
• 1+2

の２つです.

• 2*(1+2)

は右側の項がまだ演算されていないため, すぐに計算することは無理なので, この*の演算はあとまわし.

とすると, 6/2*(1+2) という数式からは, 次の2つの数式が作り出せることがわかります.

• 3*(1+2)
• 6/2*3

以上の作業を繰り返すと,

• 6/2*(1+2)
  • 3*(1+2)
    • 3*3
      • 9 →数字ひとつだけだからひとつの解
  • 6/2*3
    • 3*3
      • 9 →数字ひとつだけだからひとつの解
    • 6/6
      • 1 →数字ひとつだけだからひとつの解

となり, 9, 9, 1 の解が得られ, 答えは2となります.
あとは, ひたすら実装する.

プログラム

public class Main{
  static final char MINUS = 'M';
  static HashSet<Integer> set;

  static boolean isdigit(char ch){
    return '0' <= ch && ch <= '9' || ch == MINUS;
  }

  static String replace(String s){
    int before = s.length();

    while(true){
      for(int i=0;i<s.length();i++){
        if(s.charAt(i) == '('){
          int j = i+1;
          while(isdigit(s.charAt(j)))j++;
          if(s.charAt(j) == ')'){
            s = s.substring(0,i) + s.substring(i+1,j) + s.substring(j+1);
            break;
          }
        }
      }

      if(before == s.length()) return s;
      before = s.length();
    }
  }

  static boolean check(String s){
    for(int i=0;i<s.length();i++){
      if(!isdigit(s.charAt(i))){
        return false;
      }
    }
    return true;
  }

  static int toInt(String s){
    if(s.charAt(0) == MINUS){
      return -1 * Integer.parseInt(s.substring(1));
    }
    else{
      return Integer.parseInt(s);
    }
  }

  static void solve(String s){
    if(check(s)){
      set.add(toInt(s));
      return;
    }

    for(int i=0;i<s.length();i++){
      char op = s.charAt(i);
      if(op != '+' && op != '-' && op != '*' && op != '/') continue;
      if(!isdigit(s.charAt(i-1)) || !isdigit(s.charAt(i+1))) continue;

      int l = i-1;
      int r = i+1;
      while(l>=0 && isdigit(s.charAt(l))) l--;
      while(r<s.length() && isdigit(s.charAt(r))) r++;

      int left = toInt(s.substring(l+1,i));
      int right = toInt(s.substring(i+1,r));
      int cal = 0;

      switch(op){
      case '+': cal = left + right; break;
      case '-': cal = left - right; break;
      case '*': cal = left * right; break;
      case '/':
        if(right == 0) continue;
        cal = left / right;
      }

      String next = "" + Math.abs(cal);
      if(cal < 0) next = MINUS + next;

      solve(replace( s.substring(0,l+1) + next + s.substring(r) ));
    }
  }

  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    while(true){
      String s = sc.next();
      if(s.equals("#")) break;
      set = new HashSet<Integer>();
      solve(replace(s));
      System.out.println(set.size());
    }
  }
}