Molecular Formula

[問題] ACM/ICPC Asia Regional 2003 Aizu: Problem E

[解説]

構文解析。
詳細は後日。

[サンプルプログラム]

001 #include<iostream>
002 #include<string>
003 #include<map>
004 #include<cassert>
005 using namespace std;
006 
007 map<string, int> T;
008 bool isUnknown;
009 int cursor;
010 string line;
011 
012 bool isDigit( char ch ){
013     return ( '0' <= ch && ch <= '9' );
014 }
015 
016 bool isLower( char ch ){
017     return ( 'a' <= ch && ch <= 'z' );
018 }
019 
020 int getDigit(){
021     string digit = "";
022     while( isDigit(line[cursor]) ){
023         digit += line[cursor++];
024     }
025     if ( digit == "" ) digit = "1";
026     return atoi( digit.c_str());
027 }
028 
029 int molecular(){
030     assert( line[cursor] == '(') ;
031     cursor++;
032     string str ="";
033     int total = 0;
034     
035     while(1){
036         if ( line[cursor] == ')' ) break;
037         str = "";
038         if ( line[cursor] == '(' ) {
039             total += molecular()*getDigit();
040         } else {
041             str += line[cursor++];
042             if ( isLower(line[cursor]) ) str += line[cursor++];
043             if ( T.find( str ) == T.end() ) isUnknown = true;
044             total += T[str]*getDigit();
045         }
046     }
047     cursor++;
048     return total*getDigit();
049 }
050 
051 void makeTable(){
052     string name;
053     int x;
054     while(1){
055         cin >> name;
056         if ( name == "END_OF_FIRST_PART" ) break;
057         cin >> x;
058         T[name] = x;
059     }
060 }
061 
062 main(){
063     makeTable();
064     while(1){
065         cin >> line;
066         if ( line == "0" ) break;
067         line = "(" + line + ")1";
068         isUnknown = false;
069         cursor = 0;
070         int w = molecular();
071         if ( isUnknown ) cout << "UNKNOWN" << endl;
072         else cout << w << endl;
073     }
074 }
075