2045 Molecular Formula

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

「2045 Molecular Formula」(2006/04/17 (月) 02:08:05) の最新版変更点

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

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

**2045 Molecular Formula
**問題
http://acm.pku.edu.cn/JudgeOnline/problem?id=2045
**解答方針
文法は次のようにもかくことができる．A+はAの1回以上の繰り返しを意味する．なお，下の式では文法を記述するためのカッコは(,)と書き，記号としてのカッコは'(',')'と書いている．
 Molecular ->　( Atom | Atom Number | '(' Molecular ')' Number )+
これに従って構文解析器を設計すればよい．

なお，未知の原子があったときの処理には例外処理を利用している．
**解答例
 import java.util.*;
 
 public class Main {
     public static void main(String[] args) {
         Scanner sc = new Scanner(System.in);
         HashMap<String,Integer> dictionary = new HashMap<String,Integer>();
         while(true){
             String atom = sc.next();
             if(atom.equals("END_OF_FIRST_PART")) break;
             int weight = sc.nextInt();
             dictionary.put(atom,weight);
         }
         
         Solver sol = new Solver(dictionary);
         
         while(true){
             String molecule = sc.next();
             if(molecule.equals("0")) break;
             int ans = sol.solve(molecule);
             if(ans<0) System.out.println("UNKNOWN");
             else System.out.println(ans);
         }
     }
 }
 
 class Solver{
     HashMap<String,Integer> dictionary;
     String input;
     int c;
     
     Solver(HashMap<String, Integer> dictionary) {
         // TODO Auto-generated constructor stub
         this.dictionary = dictionary;
     }
     
     public int solve(String input){
         this.input = input.concat("$");
         this.c = 0;
         int ret;
         try{
             return molecule();
         }
         catch(UnknownException e){
             return -1;
         }
     }
     private int molecule() throws UnknownException{
         int ret = 0;
         while(true){
             if(input.charAt(c)==')'|input.charAt(c)=='$'){
                 c++;
                 break;
             }
             else if(input.charAt(c)=='('){
                 c++;
                 int m = molecule();
                 if(isDisit(input.charAt(c))) m *= number();
                 ret += m;
             }
             else{
                 int a = atom();
                 if(isDisit(input.charAt(c))) a *= number();
                 ret += a;
             }
         }
         return ret;
     }
     private int atom() throws UnknownException{
         String a;
         if(isSmall(input.charAt(c+1))){
             a = input.substring(c,c+2);
             c++;
             c++;
         }
         else{
             a = input.substring(c,c+1);
             c++;
         }
         
         if(dictionary.containsKey(a)){
             return dictionary.get(a);
         }
         else{
             throw new UnknownException();
         }
     }
     private int number(){
         int ret;
         if(isDisit(input.charAt(c+1))){
             ret = ctoi(input.charAt(c))*10+ctoi(input.charAt(c+1));
             c++;
             c++;
         }
         else{
             ret = ctoi(input.charAt(c));
             c++;
         }
         return ret;
     }
     private boolean isCapital(char c){
         return 'A'<=c&&c<='Z';
     }
     private boolean isSmall(char c){
         return 'a'<=c&&c<='z';
     }
     private boolean isDisit(char c){
         return '0'<=c&&c<='9';
     }
     private int ctoi(char c){
         return c-'0';
     }
 }
 class UnknownException extends Exception{
     
 }