leetcode 736. Lisp 语法解析

[xxleyi]

题：

给定一个类似 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"会被定义为"关键字"，不会在表达式的变量命名中出现。
最后，要说一下作用域的概念。计算变量名所对应的表达式时，在计算上下文中，首先检查最内层作用域（按括号计），然后按顺序依次检查外部作用域。我们将保证每一个测试的表达式都是合法的。有关作用域的更多详细信息，请参阅示例。
 

示例：

输入: (add 1 2)
输出: 3

输入: (mult 3 (add 2 3))
输出: 15

输入: (let x 2 (mult x 5))
输出: 10

输入: (let x 2 (mult x (let x 3 y 4 (add x y))))
输出: 14
解释:
表达式 (add x y), 在获取 x 值时, 我们应当由最内层依次向外计算, 首先遇到了 x=3, 所以此处的 x 值是 3.

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

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

输入: (let x 2 (add (let x 3 (let x 4 x)) x))
输出: 6
解释:
(let x 4 x) 中的 x 的作用域仅在()之内。所以最终做加法操作时，x 的值是 2 。

输入: (let a1 3 b2 (add a1 1) b2)
输出: 4
解释:
变量命名时可以在第一个小写字母后跟随数字.
 

注意:

我们给定的 expression 表达式都是格式化后的：表达式前后没有多余的空格，表达式的不同部分(关键字、变量、表达式)之间仅使用一个空格分割，并且在相邻括号之间也没有空格。我们给定的表达式均为合法的且最终结果为整数。
我们给定的表达式长度最多为 2000 (表达式也不会为空，因为那不是一个合法的表达式)。
最终的结果和中间的计算结果都将是一个 32 位整数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/parse-lisp-expression
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

---

答：

这题很难用纯迭代来完成，用递归很符合题目特点，但内部一些地方依然需要使用迭代。总体结构是递归，小处迭代，未尝不可。有些问题就是天生适合使用递归来解决啊！

这个题应该只是一个引子，意在让人真切的感受代码即数据。

把代码这种特殊的数据喂给解释器或者编译器，通过种种处理得到表达式的值。

最近得到一个契机，在认真学习编译器。通过这么一个很新很棒针对入门选手的材料：https://craftinginterpreters.com/

在计算机科学中，合理的抽象是宏伟大厦的根基。

先辈们的各种实践告诉我们，面对代码，还是要曲线救国，不能直接干。什么是直接干呢？就是有些人觉得，反正代码很结构化，用各种正则表达式一路处理下来，理应得到运算结果。

这种抽象结构是 code => interpret(code) => result。

这种方法或许能解决眼前这道问题，但远远不足以支撑一个宏伟大厦。

目前较为健壮也不复杂的抽象结构是 code => scanner(code) => tokens => parser(tokens) => bytes => vm(bytes) => result。

在 parser 这一步，还可以进一步扩充或缩减，可以缩减为 parser(tokens) => result，也可以扩充为 parser(tokens) => ast => compile(ast) => bytes。

面对这道题，可以采取缩减的方式，并且可以进一步缩减，边扫描边解析边求值，但所有抽象概念都已潜藏其中，和正则硬刚不在一个层面。

此外，求值过程中有意不使用 scope 的概念，因为 scope 只是一种求值规则，它规定了代码该如何被求值，但却并不直接对应于求值过程中的实体。

所以，本题解的求值过程使用 environments 这个在简易解释器中非常好用，且解释能力强悍的概念。

同样的，environments 会存在于简单的解释器中，并不代表它会存在于复杂的编译器和虚拟机中，但最终行为可以一致。想要真正掌握词法作用域，此概念不可缺少。

var evaluate = function(expr, environments=[]) {
  const digits = new Set('-0123456789')
  let nextIndex = 0
  const eof = expr.length

  // token 化，此题规则很简单，但可以很复杂
  function token() {
    const start = nextIndex
    while (expr[nextIndex] != ')' && nextIndex != eof) {
      nextIndex++
    }
    return expr.slice(start, nextIndex)
  }

  // 字面量，此题只有数字一种字面量，但同样可以很复杂
  function literal() {
    return parseInt(token())
  }

  // 变量求值，此题按照环境逐层向上取值即可，效率不高，但核心思想已经有了，可以在编译期做优化
  function variable() {
    const name = token()
    for (let i = environments.length - 1; i >= 0; i--) {
      const env = environments[i]
      if (name in env) return env[name]
    }
    throw Error(`variable: ${name} not defined`)
  }

  // 递归求子表达式的值，核心维护好环境，并在环境中求值
  // 此题只有三种，且只有 let 的处理稍稍麻烦。但同样可以很复杂，也可以优化
  function subExpr() {
    // 跨过左括号
    nextIndex++
    // 括号平衡值为 1
    let balance = 1
    // 记录起始 index
    const start = nextIndex
    // 用于存放最外层空格的索引值，正确分割子表达式
    const spaceIndice = []
    // 循环迭代，直至括号值为零，即复归平衡，子表达式提取完毕

    const weight = {'(': 1, ')': -1}
    while (balance != 0) {
      const next = expr[nextIndex]
      balance += weight[next] || 0
      // 括号平衡值为 1 时，记录空格所在的索引
      if (balance === 1 && next === ' ') spaceIndice.push(nextIndex)
      nextIndex++
    }

    const operator = expr.slice(start, spaceIndice[0])

    // sub expr is let
    if (operator === 'let') {
      // let expr will create an new env
      const env = {}
      environments.push(env)
      // iterate variable delcarations
      for (let i = 0; i < spaceIndice.length - 2; i += 2) {
        const name = expr.slice(spaceIndice[i] + 1, spaceIndice[i + 1])
        const operand = expr.slice(spaceIndice[i + 1] + 1, spaceIndice[i + 2])
        env[name] = evaluate(operand, environments)
      }

      // evaluate the result of let sub expr
      const v = evaluate(expr.slice(spaceIndice[spaceIndice.length - 1] + 1, nextIndex - 1), environments)
      // when let sub expr is done, we need to pop the top one of environments
      environments.pop()

      // return the result of let sub expr
      return v
    }

    // sub expr is add or mult
    const operand1 = expr.slice(spaceIndice[0] + 1, spaceIndice[1])
    const operand2 = expr.slice(spaceIndice[1] + 1, nextIndex)
    // evaluate two operands(which is also expression) in current environments
    const v1 = evaluate(operand1, environments)
    const v2 = evaluate(operand2, environments)

    // get result of sub expr
    if (operator === 'add') {
      return v1 + v2
    } else if (operator == 'mult') {
      return v1 * v2
    }
  }

  // 表达式求值，核心是一路携带环境
  // 此题中的表达式只有字面量，子表达式，变量三种情况
  function expression() {
    let next = expr[nextIndex]
    if (digits.has(next)) {
      return literal()
    } else if (next == '(') {
      return subExpr()
    } else {
      return variable()
    }
  }

  return expression()
};