726.原子的数量

链接：726.原子的数量
难度：Hard
标签：栈、哈希表、字符串、排序
简介：给定一个化学式，输出所有原子的数量。格式为：第一个（按字典序）原子的名子，跟着它的数量（如果数量大于 1），然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。

题解 1 - typescript

• 编辑时间：2021-07-05
• 执行用时：112ms
• 内存消耗：43MB
• 编程语言：typescript
• 解法介绍：递归检索括号，逐个存入哈希表中。

function countOfAtoms(formula: string): string {
  const uperChar = /^[A-Z]$/;
  const lowerChar = /^[a-z]$/;
  const numChar = /^[0-9]$/;
  const data = getRecord(formula);
  return Object.entries(data)
    .sort(([k1], [k2]) => {
      const len1 = k1.length;
      const len2 = k2.length;
      let i = 0;
      while (i < Math.min(len1, len2)) {
        const code1 = k1.codePointAt(i)!;
        const code2 = k2.codePointAt(i)!;
        if (code1 !== code2) return code1 - code2;
        else i++;
      }
      if (i === len1) return -1;
      else if (i === len2) return 1;
      else return 0;
    })
    .map(([k, v]) => k + (v === 1 ? '' : v))
    .join('');
  function getRecord(str: string): Record<string, number> {
    const len = str.length;
    const stack: string[] = [];
    const map: Record<string, number> = {};
    for (let i = 0; i < len; i++) {
      let c = str[i];
      if (uperChar.test(c)) {
        stack.push(c);
      } else if (lowerChar.test(c)) {
        stack.push(stack.pop()! + c);
      } else if (c === '(') {
        let left = 1;
        let tempStr = '';
        while (true) {
          if (str[i + 1] === '(') left++;
          if (str[i + 1] === ')' && --left === 0) break;
          tempStr += str[++i];
        }
        const internalRecord = getRecord(tempStr);
        i++;
        let numStr = '';
        while (numChar.test(str[i + 1])) numStr += str[++i];
        const num = +numStr;
        Object.entries(internalRecord).forEach(([k, v]) => {
          map[k] = (map[k] ?? 0) + v * (num === 0 ? 1 : num);
        });
      } else {
        while (numChar.test(str[i + 1])) c = c + str[++i];
        const num = +c;
        const char = stack.pop()!;
        map[char] = (map[char] ?? 0) + num;
      }
    }
    while (stack.length !== 0) {
      const c = stack.pop()!;
      map[c] = (map[c] ?? 0) + 1;
    }
    return map;
  }
}