表达式求值

如何计算不含括号的四则运算表达式？

• 关键: 乘除优先于加减, 所以不能边扫边从左到右算;
• 做法 (227): 用 op 记住"当前数字之前的运算符", 用栈暂存各加数;
  • + 或 -: 把 num 或 -num 压栈;
  • * 或 /: 取出栈顶算出中间结果再压回;
• 收尾: 扫描结束后把栈中所有数求和;
• 除法: 题目要求向零截断, 所以取绝对值整除后再补符号;

const calculate = (s) => {
  const stack = [];
  let op = "+";
  let num = 0;
  for (let i = 0; i < s.length; i++) {
    const char = s[i];
    if (/\d/.test(char)) num = num * 10 + Number(char);
    if (/[+\-*/]/.test(char) || i === s.length - 1) {
      if (op === "+") stack.push(num);
      else if (op === "-") stack.push(-num);
      else if (op === "*") stack.push(stack.pop() * num);
      else {
        const top = stack.pop();
        const sign = Math.sign(top);
        stack.push(Math.floor(Math.abs(top) / num) * sign);
      }
      num = 0;
      op = char;
    }
  }
  return stack.reduce((a, b) => a + b, 0);
};

加入括号后如何处理？

• 观察 (224): 一对括号内本身就是一个完整算式, 可以和外层用同一套逻辑;
• 递归: 遇到 ( 递归求值, 遇到 ) 返回结果与当前下标;
• 调用方: 把递归返回值作为 num 继续参与外层计算;
• 边界: 括号出现在字符串末尾时, 返回的下标需要回退一位, 避免外层漏掉最后一个操作数;
• 时间 $O(n)$, 空间 $O(n)$;

const calculateWithParens = (s) => {
  const dfs = (str, i) => {
    const stack = [];
    let op = "+";
    let num = 0;
    for (; i < str.length; i++) {
      const char = str[i];
      if (/\d/.test(char)) num = 10 * num + Number(char);
      if (/[+\-*/]/.test(char) || i === str.length - 1 || char === ")") {
        if (op === "+") stack.push(num);
        else if (op === "-") stack.push(-num);
        else if (op === "*") stack.push(stack.pop() * num);
        else {
          const top = stack.pop();
          const sign = Math.sign(top);
          stack.push(Math.floor(Math.abs(top) / num) * sign);
        }
        num = 0;
        op = char;
      }
      if (char === "(") {
        const [value, next] = dfs(str, i + 1);
        num = value;
        i = next === str.length - 1 ? next - 1 : next;
      }
      if (char === ")") break;
    }
    return [stack.reduce((a, b) => a + b, 0), i];
  };

  return dfs(s, 0)[0];
};