1460 Firefighters

「1460 Firefighters」の編集履歴（バックアップ）一覧はこちら

「1460 Firefighters」(2006/04/17 (月) 01:45:08) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

**1460 Firefighters
**問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=1460
**解答方針
四則演算の電卓を作るところが勝負．あとは全探索．

四則演算の式は次のように表現できる．"A|B"は「AまたはB」，"E*"は「Eの0回以上の繰り返し」，"E+"は「Eの1回以上の繰り返し」を意味する．
 expr ::= term (('+' | '-') term)*
 term ::= factor (('*' | '/') factor)*
 factor ::= num | '(' expr ')'
 num ::= ('0'|'1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'|'9')+
これに従って再帰的下向き構文解析を行う．

なお，0除算が発生した場合は例外を投げて上の階層で処理している．
**解答例
 import java.util.*;
 
 public class Main {
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         int n = sc.nextInt();
         for(int i=0;i<n;i++){
             String left = sc.next();
             String right = sc.next();
             Solver sol = new Solver(left,right);
             if(sol.solve()){
                 System.out.println("yes");
             }
             else{
                 System.out.println("no");
             }
         }
     }
 }
 
 class Solver{
     String left;
     String right;
     Solver(String l,String r){
         left = l;
         right = r;
     }
     public boolean solve(){
         int quesnum = countques(left);
         int[] quesloc = new int[quesnum];
         
         int counter = 0;
         for(int i=0;i<left.length();i++){
             if(left.charAt(i)=='?'){
                 quesloc[counter] = i;
                 counter++;
             }
         }
         
         int rightval = Integer.parseInt(right);
         
         if(quesnum==0){
             Evaluator eval = new Evaluator(left);
             try{
                 return rightval==eval.evaluate();
             }
             catch(Exception e){
                 return false; // this code mustn't be executed
             }
         }
 
         for(int i=0;i<1<<(2*quesnum);i++){
             char[] concleftc = left.toCharArray();
             for(int j=0;j<quesnum;j++){
                 int symbol = (i>>(2*j))%4;
                 switch (symbol){
                 case 0:
                     concleftc[quesloc[j]] = '+';
                     break;
                 case 1:
                     concleftc[quesloc[j]] = '-';
                     break;
                 case 2:
                     concleftc[quesloc[j]] = '*';
                     break;
                 case 3:
                     concleftc[quesloc[j]] = '/';
                     break;
                 }
             }
             String concleft = new String(concleftc);
             Evaluator eval = new Evaluator(concleft);
             try{
                 int leftval = eval.evaluate();
                 if(leftval==rightval) return true;
             }
             catch(Exception e){
                 // do nothing
             }
         }
 
         return false;
     }
     private static int countques(String s){
         int len = s.length();
         int counter = 0;
         for(int i=0;i<len;i++){
             if(s.charAt(i)=='?') counter++;
         }
         return counter;
     }
 }
 
 class Evaluator{
     String str;
     int size;
     int c;
     Evaluator(String s){
         str = s.concat("$");
         size = s.length();
         c = 0;
     }
     public int evaluate() throws Exception{
         return expr();
     }
     private int expr() throws Exception{
         int ret = term();
         while(true){
             if(str.charAt(c)=='+'){
                 c++;
                 ret += term();
             }
             else if(str.charAt(c)=='-'){
                 c++;
                 ret -= term();
             }
             else if(str.charAt(c)==')'||str.charAt(c)=='$'){
                 break;
             }
             else{
                 //
             }
         }
         return ret;
     }
     private int term() throws Exception{
         int ret = factor();
         while(true){
             if(str.charAt(c)=='*'){
                 c++;
                 ret *= factor();
             }
             else if(str.charAt(c)=='/'){
                 c++;
                 int f = factor();
                 if(f==0) throw new Exception();
                 ret /= f;
             }
             else if(str.charAt(c)=='+'||str.charAt(c)=='-'||
                     str.charAt(c)==')'||str.charAt(c)=='$'){
                 break;
             }
             else{
                 //
             }
         }
         return ret;
     }
     private int factor() throws Exception{
         if(str.charAt(c)=='('){
             c++;
             int ret = expr();
             c++;
             return ret;
         }
         else{
             int ret = num();
             return ret;
         }
     }
     private int num(){
         int ret = 0;
         while('0'<=str.charAt(c)&&str.charAt(c)<='9'){
             ret = ret*10 + (str.charAt(c)-'0');
             c++;
         }
         return ret;
     }
 }