AOJ1244 Molecular Formula

問題概要

---

元素記号と重さの対応表が最初に与えられる。
その後、化学式が与えられるので、その重さを答える。
未知の元素が含まれている場合は"UNKNOWN"と出力する。

<molecule>::=<atom>|<atom><number>|'('<molecule>')'<number>|<molecule><molecule>
<atom>::=<capitaletter>|<capitaletter><smallletter>
<number>::=2|3|4|・・・|97|98|99
<capitalletter>::=A|B|C|・・・|X|Y|Z
<smallletter>::=a|b|c|・・・|x|y|z

解法

---

BNFに従って構文解析するだけ。

ソース

---

#include<iostream>
#include<string>
#include<map>
#include<sstream>
#include<cctype>
using namespace std;
typedef string::const_iterator Cursol;
map < string , int > d;
bool ok;
int stoi(string s) {
  int v;
  stringstream ss(s);
  ss>>v;
  return v;
}
int Num(Cursol &c){
  int ret;
  string s;
  s += *c++;
  if(isdigit(*c)) s += *c++;
  return stoi(s);
}
int Atom(Cursol &c){
  int ret;
  string s;
  s += *c++;
  if(islower(*c)) s += *c++;
  ret = d[s];
  if(ret == 0) ok = false;
  return ret;
}
int Molecule(Cursol &c){
  if( *c == '\0' || *c == ')') return 0; 
  int ret = 0;
  if(*c == '('){
    ret = Molecule(++c) * Num(++c);
  }else if(isupper(*c)){
    ret = Atom(c);
    if(isdigit(*c)) ret *= Num(c);
  }
  return ret + Molecule(c);
}
int main(){
  string s;
  while(cin >> s , s != "END_OF_FIRST_PART"){
    cin >> d[s];
  }
  while(cin >> s , s != "0"){
    Cursol c = s.begin();
    ok = true;
    int ret = Molecule(c);
    if(ok) cout << ret << endl;
    else cout << "UNKNOWN" << endl;
  }
}