Algoogle

Algorithm for Programming Contest

AOJ 1244 Molecular Formula

Category: AOJ Tag: parsing

Molecular Formula

問題概要


原子量のリストが渡される.
分子のリストを渡すのでそれぞれの重さを求めよ. リストにない原子が出てくる場合は場合はUNKNOWNを出力しろ.

解法


基本的には分子の文字列を頭から見ていけば基本的には,
原子, 数字, 原子, 数字
と並んでいる(数字の長さは0から2, 原子の長さは1か2).
例外としてその原子の部分に括弧でくくられた分子が来ることがあるが中身は同じ構造なので再帰的にやればよい.

コード


(1244.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)
#define all(u) begin(u),end(u)
#define pb push_back
const int inf = 1e9;
string seq;
map<string, int> w;
int cur;

int num(){
    int ret = 0;
    while(cur < seq.size() and isdigit(seq[cur]))
        ret = 10*ret+seq[cur++]-'0';
    return ret;
}

int atm(){
    string a = seq.substr(cur,1);
    cur++;
    while(cur < seq.size() and islower(seq[cur]))
        a.pb(seq[cur++]);
    auto it = w.find(a);
    if(it == end(w)) return -1;
    return it->second;
}

int mol(){
    if(cur == seq.size()) return 0;
    int ret = 0;
    if(seq[cur] == ')') return 0;
    if(seq[cur] == '('){
        ++cur;
        ret = mol();
        ++cur;
        if(ret < 0) return ret;
        ret *= num();
        int d = mol();
        if(d < 0) return d;
        return ret+d;
    }
    ret = atm();
    if(ret < 0) return ret;
    ret *= max(1,num());
    int d = mol();
    if(d < 0) return d;
    return ret+d;
}

void solve(){
    while(1){
        cin >> seq;
        if(seq == "0") break;
        cur = 0;
        int ans = mol();
        if(ans < 0) puts("UNKNOWN");
        else cout << ans << endl;
    }
}

void input(){
    string s;
    while(1){
        cin >> s;
        if(s == "END_OF_FIRST_PART") break;
        int d; cin >> d;
        w[s] = d;
    }
}

signed main(){
    input();
    solve();
    return 0;
}

Comments