C++で化学式を解析して各原子の個数を求める方法

問題概要

化学式が与えられたとき、そこに含まれる各原子（元素）の出現回数を求める問題を考えます。

元素名は必ず大文字アルファベットで始まり、その後に0個以上の小文字アルファベットが続きます。また、原子の個数が1より大きい場合は元素名の後ろに1桁以上の数字が付きますが、個数がちょうど1の場合は数字は省略されます。たとえば「H2O」や「H2O2」は有効な化学式ですが、「H1O2」は無効です。

たとえば、入力が「Na2(CO)3」であれば、出力は「C3Na2O3」となります。これは炭素（C）が3個、ナトリウム（Na）が2個、酸素（O）が3個含まれていることを意味します。

解き方のアプローチ

この問題は、元素ごとの出現回数を連想配列（マップ）で管理し、括弧の入れ子構造をスタックで処理することで効率よく解けます。手順は以下の通りです。

1. 結果文字列を組み立てる makeRet() 関数

• マップ m を引数として受け取ります。
• 結果を格納する ret を空文字列で初期化します。
• マップ内の各キーと値のペア it について、以下を行います。
  • ret に元素名（キー）を連結する。
  • 出現回数（値）が1より大きい場合は、数値を文字列に変換して ret に連結する。
• 完成した ret を返します。

2. 化学式を走査する countOfAtoms() 関数

• 集計用のマップ m と、括弧処理用のスタック st を用意します。
• i := 0、n := 文字列 s の長さとし、i が n 未満の間、以下を繰り返します。

（a） '(' を読んだとき

• 現在のマップ m をスタック st にプッシュし、m を新しいマップで置き換えます。これにより、括弧の中の原子を独立してカウントできます。

（b） ')' を読んだとき

• 直後に続く数字を読み取り、係数 val を算出します（val := val × 10 + (s[i] − '0')）。
• スタック st の先頭要素を temp として取得し、ポップします。
• 現在のマップ m 内の各ペアについて、値を val 倍したものを temp[キー] に加算します。
• m := temp として、括弧内の集計結果を外側のスコープに統合します。

（c） 上記以外（元素名を読んだとき）

• c を先頭に、続く小文字をすべて読み込んで元素名 name を作成します。
• 続く数字を読み込んで出現回数 val を求めます。val が 0 のままの場合は 1 に補正します。
• m[name] += val として集計します。

ループが終了したら、makeRet(m) の返り値を答えとして返します。なお、')' の後に数字が続かない入力にも対応したい場合は、val が 0 のままのときに 1 を代入する処理を追加しておくとより安全です。

実装例（C++）

以下のコードで実際の動作を確認できます。

#include <bits/stdc++.h>
using namespace std;
class Solution {
    public:
    string makeRet(map<string, int> m){
        string ret = "";
        for (auto& it : m) {
            ret += it.first;
            if (it.second > 1) {
                ret += to_string(it.second);
            }
        }
        return ret;
    }
    string countOfAtoms(string s){
        map<string, int> m;
        stack<map<string, int> > st;
        int i = 0;
        int n = s.size();
        while (i < n) {
            char c = s[i];
            i++;
            if (c == '(') {
                st.push(m);
                m = map<string, int>();
            }
            else if (c == ')') {
                int val = 0;
                while (i < n && s[i] >= '0' && s[i] <= '9') {
                    val = val * 10 + (s[i] - '0');
                    i++;
                }
                map<string, int> temp = st.top();
                st.pop();
                for (auto& it : m) {
                    it.second *= val;
                    temp[it.first] += it.second;
                }
                m = temp;
            }  
            else {
                string name = "";
                int val = 0;
                name += c;
                while (i < n && s[i] >= 'a' && s[i] <= 'z') {
                    name += s[i];
                    i++;
                }
                while (i < n && s[i] >= '0' && s[i] <= '9') {
                    val = val * 10 + (s[i] - '0');
                    i++;
                }
                val = val == 0 ? 1 : val;
                m[name] += val;
            }
        }
        return makeRet(m);
    }
};
main(){
    Solution ob;
    cout << (ob.countOfAtoms("Na2(CO)3"));
}

入力

Na2(CO)3

出力

C3Na2O3

実装のポイント

• C++ の std::map はキーを辞書順に保持するため、出力結果も自動的に元素名のアルファベット順になります。
• std::to_string を使うことで、整数の個数を簡単に文字列へ変換できます。
• 括弧の入れ子はスタックで管理するのが定石です。括弧を閉じるたびにマップのマージが発生するため、最悪計算量は文字列長に対して O(n² log n) 程度になる点に注意しましょう。