解题思路

题目要求解析化学分子式，计算每种原子的个数。需要处理以下情况：

  1. 单个大写字母表示的原子（如H）
  2. 大写字母加小写字母表示的原子（如Mg）
  3. 带数字的原子（如H2）
  4. 带括号的分子团（如(OH)2）

解题思路：

  1. 使用递归方法处理嵌套的括号结构
  2. 使用map存储每种原子的数量
  3. 按照以下规则解析：
    • 遇到大写字母开始新原子
    • 遇到小写字母继续当前原子
    • 遇到数字乘以当前原子数量
    • 遇到括号递归处理

代码

#include <iostream>
#include <map>
#include <string>
using namespace std;

class Solution {
    string formula;
    int pos = 0;
    
    // 获取数字
    int getNumber() {
        int num = 0;
        while (pos < formula.length() && isdigit(formula[pos])) {
            num = num * 10 + (formula[pos] - '0');
            pos++;
        }
        return num == 0 ? 1 : num;
    }
    
    // 递归解析分子式
    map<string, int> parse() {
        map<string, int> result;
        
        while (pos < formula.length()) {
            if (formula[pos] == ')') {
                pos++;
                return result;
            }
            
            if (formula[pos] == '(') {
                pos++;
                auto subResult = parse();
                int num = getNumber();
                for (auto& [atom, count] : subResult) {
                    result[atom] += count * num;
                }
            } else {
                string atom;
                atom += formula[pos++];
                while (pos < formula.length() && islower(formula[pos])) {
                    atom += formula[pos++];
                }
                result[atom] += getNumber();
            }
        }
        return result;
    }
    
public:
    string countAtoms(string f) {
        formula = f;
        pos = 0;
        string result;
        
        for (auto& [atom, count] : parse()) {
            result += atom;
            if (count > 1) {
                result += to_string(count);
            }
        }
        
        return result;
    }
};

int main() {
    string formula;
    cin >> formula;
    Solution solution;
    cout << solution.countAtoms(formula) << endl;
    return 0;
}

import java.util.*;

public class Main {
    static class Solution {
        String formula;
        int pos = 0;
        
        // 获取数字
        private int getNumber() {
            int num = 0;
            while (pos < formula.length() && 
                   Character.isDigit(formula.charAt(pos))) {
                num = num * 10 + (formula.charAt(pos) - '0');
                pos++;
            }
            return num == 0 ? 1 : num;
        }
        
        // 递归解析分子式
        private TreeMap<String, Integer> parse() {
            TreeMap<String, Integer> result = new TreeMap<>();
            
            while (pos < formula.length()) {
                char c = formula.charAt(pos);
                if (c == ')') {
                    pos++;
                    return result;
                }
                
                if (c == '(') {
                    pos++;
                    TreeMap<String, Integer> subResult = parse();
                    int num = getNumber();
                    for (Map.Entry<String, Integer> entry : subResult.entrySet()) {
                        result.merge(entry.getKey(), 
                                   entry.getValue() * num, 
                                   Integer::sum);
                    }
                } else {
                    StringBuilder atom = new StringBuilder();
                    atom.append(c);
                    pos++;
                    while (pos < formula.length() && 
                           Character.isLowerCase(formula.charAt(pos))) {
                        atom.append(formula.charAt(pos));
                        pos++;
                    }
                    result.merge(atom.toString(), getNumber(), Integer::sum);
                }
            }
            return result;
        }
        
        public String countAtoms(String f) {
            formula = f;
            pos = 0;
            StringBuilder result = new StringBuilder();
            
            for (Map.Entry<String, Integer> entry : parse().entrySet()) {
                result.append(entry.getKey());
                if (entry.getValue() > 1) {
                    result.append(entry.getValue());
                }
            }
            
            return result.toString();
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String formula = sc.next();
        Solution solution = new Solution();
        System.out.println(solution.countAtoms(formula));
    }
}

class Solution:
    def countAtoms(self, formula: str) -> str:
        def parse() -> dict:
            nonlocal pos
            result = {}
            
            while pos < len(formula):
                if formula[pos] == ')':
                    pos += 1
                    return result
                
                if formula[pos] == '(':
                    pos += 1
                    sub_result = parse()
                    num = get_number()
                    for atom, count in sub_result.items():
                        result[atom] = result.get(atom, 0) + count * num
                else:
                    atom = formula[pos]
                    pos += 1
                    while pos < len(formula) and formula[pos].islower():
                        atom += formula[pos]
                        pos += 1
                    result[atom] = result.get(atom, 0) + get_number()
            
            return result
        
        def get_number() -> int:
            nonlocal pos
            num = 0
            while pos < len(formula) and formula[pos].isdigit():
                num = num * 10 + int(formula[pos])
                pos += 1
            return num if num > 0 else 1
        
        pos = 0
        result = []
        
        for atom, count in sorted(parse().items()):
            result.append(atom)
            if count > 1:
                result.append(str(count))
                
        return ''.join(result)

# 读取输入并处理
formula = input()
solution = Solution()
print(solution.countAtoms(formula))

算法及复杂度

  • 算法：递归 + 哈希表
  • 时间复杂度： - 为分子式长度
  • 空间复杂度： - 递归调用栈的深度和哈希表的大小