化学方程式

GitHub跳转原题关系图Canvas 关系图返回列表

递归解析括号化学式并累计元素原子数，比较等号两侧的元素映射。

OJ: shumeng

题目 ID: CSP201912C

难度:普及+/提高-

标签:递归字符串模拟解析

日期: 2026-07-31 16:21

目录

  1. 形式化题目
  2. 思路
    1. 递归解析化学式
    2. 表达式与两侧比较
  3. 代码
  4. 复杂度
  5. 总结

形式化题目

判断一个化学方程式是否配平。方程式由等号 = 连接两个表达式，表达式由若干带系数的化学式用 + 连接；化学式由元素、带系数的括号及可嵌套括号组成。比较等号两侧每种元素的原子总数，全部相等即配平。

思路

递归解析化学式

按题目的 BNF 直接递归解析化学式。parse_formula 连续读取项，直到右括号、加号、等号或行尾：

  • 遇到元素就读取一个大写字母和可选小写字母；
  • 遇到左括号则递归读取内部化学式；
  • 项后面的数字是它的系数，递归返回的元素计数整体乘上这个系数再合并到当前映射。

表达式与两侧比较

表达式层先读化学式前的系数，再调用化学式解析，遇到 + 继续。分别解析等号两侧的 map<元素, 原子数>，两个映射相同就是配平。

代码

cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:41
 */
#include <bits/stdc++.h>
using namespace std;

// 元素 -> 原子总数 的映射
typedef map<string, long long> AtomCount;

// 从 position 开始读一个整数；没有数字时按系数 1 处理。
long long read_number(const string &text, int &position) {
    if (position >= (int)text.size() || !isdigit(text[position])) return 1;
    long long result = 0;
    while (position < (int)text.size() && isdigit(text[position])) {
        result = result * 10 + text[position] - '0';
        position++;
    }
    return result;
}

// 把 source 中的元素计数乘 multiplier 后累加进 target。
void add_count(AtomCount &target, const AtomCount &source, long long multiplier) {
    for (AtomCount::const_iterator it = source.begin(); it != source.end(); ++it) {
        target[it->first] += it->second * multiplier;
    }
}

// 递归解析一个化学式：由若干“项+系数”组成，项可以是元素或括号括起来的化学式。
AtomCount parse_formula(const string &text, int &position) {
    AtomCount result;
    while (position < (int)text.size() && text[position] != ')'
            && text[position] != '+' && text[position] != '=') {
        AtomCount term;
        if (text[position] == '(') {
            position++;
            term = parse_formula(text, position); // 括号内整个化学式
            position++;                           // 跳过右括号
        } else {
            // 元素：一个大写字母加可选的一个小写字母。
            string element;
            element += text[position++];
            if (position < (int)text.size() && islower(text[position])) {
                element += text[position++];
            }
            term[element] = 1;
        }
        // 项后面的数字是整体系数，作用到该项包含的全部元素上。
        add_count(result, term, read_number(text, position));
    }
    return result;
}

// 解析一个表达式：若干带系数的化学式用 '+' 连接。
AtomCount parse_expression(const string &text, int &position) {
    AtomCount result;
    while (true) {
        long long multiplier = read_number(text, position);
        AtomCount formula = parse_formula(text, position);
        add_count(result, formula, multiplier);
        if (position >= (int)text.size() || text[position] != '+') break;
        position++;
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int test_count;
    cin >> test_count;
    while (test_count--) {
        string equation;
        cin >> equation;
        int position = 0;
        AtomCount left = parse_expression(equation, position);
        position++; // 跳过 '='
        AtomCount right = parse_expression(equation, position);
        cout << (left == right ? 'Y' : 'N') << '\n';
    }

    return 0;
}

复杂度

设方程式长度为 LL、不同元素数为 EE。每个字符被解析常数次，映射合并的时间复杂度为 O(Llog⁡E)O(L\log E)，空间复杂度为 O(E+D)O(E + D)，其中 DD 是括号嵌套深度。

总结

括号表达式的系数应在递归返回后统一乘到内部全部元素上。把化学式和表达式分成两个解析层，能自然处理化学式前系数、项后系数以及嵌套括号。