【阿里算法题】原子数量 - Javascript版本

题目描述

给你一个字符串化学式 formula ，返回 每种原子的数量 。

原子总是以一个大写字母开始，接着跟随 0 个或任意个小写字母，表示原子的名字。

如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。

• 例如，"H2O" 和 "H2O2" 是可行的，但 "H1O2" 这个表达是不可行的。

两个化学式连在一起可以构成新的化学式。

• 例如 "H2O2He3Mg4" 也是化学式。

由括号括起的化学式并佐以数字（可选择性添加）也是化学式。

• 例如 "(H2O2)" 和 "(H2O2)3" 是化学式。

返回所有原子的数量，格式为：第一个（按字典序）原子的名字，跟着它的数量（如果数量大于 1），然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。

示例 1：

输入：formula = "H2O"
输出："H2O"
解释：原子的数量是 {'H': 2, 'O': 1}。

示例 2：

输入：formula = "Mg(OH)2"
输出："H2MgO2"
解释：原子的数量是 {'H': 2, 'Mg': 1, 'O': 2}。

示例 3：

输入：formula = "K4(ON(SO3)2)2"
输出："K4N2O14S4"
解释：原子的数量是 {'K': 4, 'N': 2, 'O': 14, 'S': 4}。

解题思路

看到括号表达式，第一反应就是应用栈操作；方题解压入栈的每一层是一个哈希表，每一层计算出原子的数量，遇到右括号后获取倍数值，乘以倍数后弹出最上层，数据并入次上层；

个人习惯只用一层，连带左括号一起压入栈，遇到右括号时一直弹出顶层，直到第一个左括号时停止，获取这一段的原子和数字，将倍数计入括号内的表达式数字，再压入栈中，继续读取后面的字符，重复操作直到结束。

化学表达式有很明显的字符串特征，第一反应使用正则表达式解析原子和数字。 正则表达式 /([A-Z][a-z]?)(\d\*)/g

小技巧：正则表达式带有全局修饰符时，循环调用 exec 方法，方法内部会记录每次执行的索引，结果和 match 全局的正则表达式类似，不过循环 exec 可以获取每次匹配到的分组数据，而前者只有匹配结果。

const formulaReg = /([A-Z][a-z]?)(\d\*)/g;
let RegArr;
while ((RegArr = formulaReg.exec("C4H6CaO4"))) {
  console.log(RegArr);
}

这道题跟解析数学运算表达式很像，其实题目不难，思路比较朴素，细心一点处理就好了。

附上代码：

/**
 * @param {string} formula
 * @return {string}
 */
var countOfAtoms = function (formula) {
  const stack = [];
  const formulaMap = {};
  const formulaArr = formula.split("");
  const length = formulaArr.length;
  let formulaTmp = "";

  function genFormulaMap(formulaStr, times = 1) {
    const formulaReg = /([A-Z][a-z]?)(\d*)/g;
    let RegArr;
    while ((RegArr = formulaReg.exec(formulaStr))) {
      const atom = RegArr[1];
      const num = Number(RegArr[2]) || 1;
      if (formulaMap[atom] === undefined) {
        formulaMap[atom] = num * times;
      } else {
        formulaMap[atom] += num * times;
      }
    }
  }

  function push2Stack(formulaStr, times = 1) {
    const formulaReg = /([A-Z][a-z]?)(\d*)/g;
    let RegArr;
    while ((RegArr = formulaReg.exec(formulaStr))) {
      const atom = RegArr[1];
      const num = Number(RegArr[2]) || 1;
      stack.push(`${atom}${num * times}`);
    }
  }

  for (let i = 0; i < length; ++i) {
    const item = formulaArr[i];
    if (item === ")") {
      let str = "";
      while (str !== "(") {
        formulaTmp = str + formulaTmp;
        str = stack.pop();
      }
      let formulaNum = "";
      let j;
      for (j = i + 1; j < length && /\d/.test(formulaArr[j]); ++j) {
        formulaNum += formulaArr[j];
      }
      i = j - 1;
      if (stack.length > 0) {
        push2Stack(formulaTmp, Number(formulaNum) || 1);
        formulaTmp = "";
      } else {
        genFormulaMap(formulaTmp, Number(formulaNum) || 1);
        formulaTmp = "";
      }
    } else if (item === "(" || stack.length > 0) {
      stack.push(item);
      if (formulaTmp !== "") {
        genFormulaMap(formulaTmp);
        formulaTmp = "";
      }
    } else {
      formulaTmp += item;
    }
  }
  if (formulaTmp !== "") {
    genFormulaMap(formulaTmp);
    formulaTmp = "";
  }
  return Object.entries(formulaMap)
    .sort()
    .map((x) => (x[1] === 1 ? x[0] : x.join("")))
    .join("");
};