AOJ : 1244 - Molecular Formula

問題概要

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1244
問題文中に書いてある構文で, 分子を表す文字列が入力されます.
この分子の重さを答える問題です.
ただし, 文字列中に出てくる原子記号が, 入力の前半で与えられた原子記号の中にない場合, UNKNOWN と出力する必要があります.

アルゴリズム

構文解析器を書くだけです.

プログラム

int idx;
string s;
map<string,int> atom;

int Number(){
  string res = "";
  while(isdigit(s[idx])){
    res += s[idx++];
  }
  return atoi(&res[0]);
}

int Atom(){
  string res = "";
  res += s[idx++];
  if(islower(s[idx])){
    res += s[idx++];
  }
  return atom.find(res) != atom.end() ? atom[res] : -1;
}

int Molecule(){
  int res = 0;

  while(idx < s.length() && s[idx] != ')'){
    if(s[idx] == '('){
      idx++;
      int tmp = Molecule();
      if(tmp == -1) return -1;
      idx++;
      res += tmp * Number();
    }
    else{
      int tmp = Atom();
      if(tmp == -1) return -1;
      if(isdigit(s[idx])){
        res += tmp * Number();
      }
      else{
        res += tmp;
      }
    }
  }

  return res;
}

int main(void){
  while(cin>>s,s!="END_OF_FIRST_PART"){
    int w;
    cin>>w;
    atom[s] = w;
  }

  while(cin>>s,s!="0"){
    idx = 0;
    int rst = Molecule();
    if(rst == -1)
      cout<<"UNKNOWN\n";
    else
      cout<<rst<<endl;
  }

  return 0;
}