困难

问题描述

给你一个类似 Lisp 语句的字符串表达式 expression，求出其计算结果。

表达式语法如下所示:

• 表达式可以为整数，let 表达式，add 表达式，mult 表达式，或赋值的变量。表达式的结果总是一个整数。
• (整数可以是正整数、负整数、0)
• let 表达式采用 "(let v1 e1 v2 e2 ... vn en expr)" 的形式，其中 let 总是以字符串 "let" 来表示，接下来会跟随一对或多对交替的变量和表达式，也就是说，第一个变量 v1 被分配为表达式 e1 的值，第二个变量 v2 被分配为表达式 e2 的值，依次类推；最终 let 表达式的值为 expr 表达式的值。
• add 表达式表示为 "(add e1 e2)" ，其中 add 总是以字符串 "add" 来表示，该表达式总是包含两个表达式 e1、e2 ，最终结果是 e1 表达式的值与 e2 表达式的值之 和 。
• mult 表达式表示为 "(mult e1 e2)" ，其中 mult 总是以字符串 "mult" 表示，该表达式总是包含两个表达式 e1、e2，最终结果是 e1 表达式的值与 e2 表达式的值之 积 。
• 在该题目中，变量名以小写字符开始，之后跟随 0 个或多个小写字符或数字。为了方便，"add" ，"let" ，"mult" 会被定义为 "关键字" ，不会用作变量名。
• 最后，要说一下作用域的概念。计算变量名所对应的表达式时，在计算上下文中，首先检查最内层作用域（按括号计），然后按顺序依次检查外部作用域。测试用例中每一个表达式都是合法的。有关作用域的更多详细信息，请参阅示例。

示例 1：

输入：expression = "(let x 2 (mult x (let x 3 y 4 (add x y))))"
输出：14
解释：
计算表达式 (add x y), 在检查变量 x 值时，
在变量的上下文中由最内层作用域依次向外检查。
首先找到 x = 3, 所以此处的 x 值是 3 。

示例 2：

输入：expression = "(let x 3 x 2 x)"
输出：2
解释：let 语句中的赋值运算按顺序处理即可。

示例 3：

输入：expression = "(let x 1 y 2 x (add x y) (add x y))"
输出：5
解释：
第一个 (add x y) 计算结果是 3，并且将此值赋给了 x 。
第二个 (add x y) 计算结果是 3 + 2 = 5 。

提示：

• 1 <= expression.length <= 2000
• exprssion 中不含前导和尾随空格
• expressoin 中的不同部分（token）之间用单个空格进行分隔
• 答案和所有中间计算结果都符合 32-bit 整数范围
• 测试用例中的表达式均为合法的且最终结果为整数

递归

操作符分别有 $let$、$add$、$mult$ 三种，每种操作都会使用 '(' 和 ')'，编写一个方法 $execute$，对表达式进行处理，当传入的表达式带有'('，则说明是 $let$、$add$、$mult$ 三种中的一种，将表达式中的首尾括号移除，然后遍历表达式字符串，遍历有两种情况：

• 表达式以 '(' 开头，则将表达式从当前位置截取到对应的 ')'，得到一个子表达式，递归调用 $execute$ 进行处理。
• 表达式非 '(' 开头，则遍历到空格为止，得到一个子表达式。

首个得到子表达式，必然是 $let$、$add$、$mult$ 中的一种：

• 如果是以 $let$ 开始，则后续必然是 「变量名 变量值」 这两个成对往复出现，使用 $def$ 进行标记，若 $def = null$，则当前获取到的子表达式就是变量名，赋值给 $def$ 后进行下次遍历，下次遍历的就是需要赋值为上次获取到的变量名的变量值，如果变量值为数字，则将其跟变量名成对记录到 $map$ 中，如果变量值未另外一个变量名，则用过 $map$ 中的记录找到对应的值后再记录，如果是一段子表达式，则递归调用 $execute$ 进行处理，赋值操作完成后，将 $def$ 置为 $null$，表示下个获取到的子表达式仍然是一个变量名。
• 如果是以 $add$ 或 $mult$ 开始，后续必然跟有两个参数，两个参数可能是数字、变量或子表达式，无论是哪种，都直接交由 $execute$ 进行处理，$execute$ 将处理结果返回即可。得到结果后根据操作返回结果即可。

由于变量有作用域的，子表达式中可以定义同名变量和访问上层变量，因此，每次调用 $execute$ 时，需要把当前作用域中的变量值传递到下层，再由下层进行复制与重新赋值。

$execute$ 如果接收到的表达式如果不是以 '(' 开头，则只会是变量值，如果是纯数字，则返回纯数字，如果是字符串，则从变量列表中查找对应的值并返回，其余情况按上面所说的步骤进行处理返回即可。

/**
 * @param {string} expression
 * @return {number}
 */
var evaluate = function (expression) {
  const OPS = ['let', 'add', 'mult']
  const execute = (exp, pm) => {
    if (!isNaN(+exp)) return +exp
    if (!exp.includes('(')) return pm.get(exp)
    exp = exp.substring(1, exp.length - 1)
    const map = new Map()
    if (pm) {
      for (const [k, v] of pm.entries()) map.set(k, v)
    }
    let slow = 0
    let fast = 0
    let action = ''
    let def = null
    let x = null
    let y = null
    while (fast < exp.length) {
      let op
      if (exp[fast] === '(') {
        let cnt = 0
        do {
          if (exp[fast] === '(') cnt++
          else if (exp[fast] === ')') cnt--
          fast++
        } while (cnt > 0)
      } else {
        while (fast < exp.length && exp[fast] !== ' ') fast++
      }
      op = exp.substring(slow, fast)
      if (OPS.includes(op)) {
        action = op
      } else {
        if (action === 'let') {
          if (def == null && !op.startsWith('(')) {
            def = op
          } else if (def != null) {
            const param = execute(op, map)
            if (map.has(param)) {
              map.set(def, map.get(param))
            } else {
              map.set(def, execute(op, map))
            }
            def = null
          } else {
            return execute(op, map)
          }
        } else {
          if (x == null) {
            x = execute(op, map)
          } else {
            y = execute(op, map)
          }
        }
      }
      fast++
      slow = fast
    }
    if (action === 'add') {
      return x + y
    } else if (action === 'mult') {
      return x * y
    } else {
      return isNaN(+def) ? map.get(def) : +def
    }
  }
  return execute(expression, null)
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$