题解 P2382 【化学分子式】

· · 题解

化学分子式，嗯，大家很熟悉的对吧……

但是，这改变不了只是一道模拟题的事实！

我们发现有一系列这样的题目——字符串，又嵌套，类似于2017提高组的Day1T2，它们的解法也有一种共性，堆栈罢了。递归也好，循环也罢……反正能搞出来就OK啦qwq~

本人欺这题数据特小，map, string乱搞一下，哈希或者暴力扫描也行的啦。

1、遇到'('，我们就把栈的层数+1，以便出栈时累计

2、遇到字母后，判断下一位是否是小写字母，将其在map中的值取出加入栈中，再将最近一次的元素保存（暂记作key），等会有用^_^，别忘了判断UNKNOWN。

3、遇到数字，while循环取出它（记作x），说明上次的key有了用武之地，在栈中加入（x - 1）倍的key元素质量，因为上一次加了一份嘛

4、若遇到')'，我们考虑直接取出后面的数字（还是x），然后将本层栈中答案乘上x，加入上一层栈中并清空这一层。

完结撒花！

（PS: stirng类型属于c++的一等公民，使用总有意想不到的效果，但是容易爆时间爆空间，竞赛慎用）

#include<map>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100;
map<string, int> ref;//定义map
string s, END = "END_OF_FIRST_PART";
int a[N], top;
int read() {//无聊的读入优化
    int x = 0; char ch = getchar(); bool f = 0;
    while(!isdigit(ch)) {
        if(ch == '-') f = 1;
        ch = getchar();
    }
    while(isdigit(ch)) {
        x = (x << 1) + (x << 3) + (ch ^ '0');
        ch = getchar();
    }
    return ! f ? x : -x;
}
bool sum(string ss) {
    a[0] = 0; int x; string key; top = 0;
    for(int i = 0; i < ss.length(); i++) {
        if(ss[i] == '(') top++;//第一步
        if(isalpha(ss[i])) {//STEP 2
            if('a' <= ss[i + 1] && ss[i + 1] <= 'z')
                key = ss.substr(i, 2), a[top] += ref[key], i++;//substr截取子串真心好用
            else key = ss.substr(i, 1), a[top] += ref[key];
            if(!ref[key]) return 0;//判断无解
        }
        if(isdigit(ss[i])) {//STEP 3
            x = 0;
            while(isdigit(ss[i]))
                x = (x << 1) + (x << 3) + (ss[i] ^ '0'), i++;//类读入优化打法
            i--; a[top] += (x - 1) * ref[key];
        }
        if(ss[i] == ')') {//STEP 4
            i++; x = 0;
            while(isdigit(ss[i]))
                x = (x << 1) + (x << 3) + (ss[i] ^ '0'), i++;
            a[top - 1] += x * a[top];
            i--; a[top] = 0; top --;
        }
    }
    return 1;
}
int main() {
    cin >> s;
    while(s != END) {//一等公民判断使用不等号，就是这么简单
        int x = read();
        ref[s] = x; cin >> s;
    }
    cin >> s;
    while(s != "0") {
        if(!sum(s)) printf("UNKNOWN\n");
            else printf("%d\n", a[0]);
        cin >> s;
    }
    return 0;
}