假如我们有这样的一个需求，接受一个用户录入的算术表达式，解析并计算出结果。

其中，这个表达式中，可以存在：

数，表示参与计算的对象
运算符（可以是自定义的运算符），表示不同的计算
括号，表示对计算顺序的干预

那可以怎么做？

本系列文章，将提供几种不同的解决方案。本篇将介绍一种常见的方案：“逆波兰表示法”。

首先我们先了解一些概念。

中缀表示法

中缀表示法，应该是我们最常接触的算术表示法了。该表示法，操作符位于两个操作数中间，因此而得名。

【例 1】：

1
(10 + 15 - 20) * 30 / 40 ^ 2

这就是一个使用中缀表示法的例子。

在中缀表示法中，括号可以改变一个表达式的计算顺序。

(1 - 1) - 1 和 1 - (1 - 1) 是完全不同的。所以， 1 - 1 - 1 这样的表达式，对于计算机来说，是存在解析的歧义的，处理起来相对麻烦。

逆波兰表示法

逆波兰表示法中，操作符放在操作数的后面，因此也叫做后缀表示法，上面的【例 1】，可以这样等价地表示：

1
10 15 + 20 - 30 * 40 2 ^ /

虽然跟我们的数学经验有着很大的差别，但是在计算机处理方面，却有着其独特的优势。逆波兰表示法的一个特点是，只要元数固定，无需括号，也能无歧义地解析。

就像【例 2】中的 (1 - 1) - 1 ，可以用 1 1 - 1 - 来表示，而 1 - (1 - 1) 则为 1 1 1 - -。

逆波兰表示法中，运算顺序才是决定运算顺序的因素，而非括号。

而且，逆波兰表示法的计算规则比较简单，利用栈就可以高效地运算，所以，简直就是为计算机量身定制。

为了更好地说明逆波兰表示法，下面开始实现一个简单的算术表达式计算器，通过代码来加深理解。

首先设定一些小目标：

数值支持，为了方便，只支持正数
运算符支持，+（加）, -（减）, *（乘）, /（除）, %（模）, ^ （指数）等运算
圆括号支持

同时还是为了简单起见，不实现表达式 tokenize 方法，直接人工输入分好词的 token（下文使用记号一词代替 token）数组。

例如上述【例 1】，直接使用 ["10", "15", "+", "20", "-", "30", "*", "40", "2", "^", "/"] 这种形式的输入来表示。

然后是程序的大致执行流程：

将中缀表示法的记号序列，转换成逆波兰表示法的记号序列，即 ["10", "15", "20", "+", "30", "40", "2", "^", "*", "/", "-"] 这种形式
实现转换后的逆波兰记号序列的计算，如录入上述记号流的运算结果应为 0.09375。

开始实现

首先定义支持的运算符，此处需要关注运算符的优先级和结合性。

优先级决定了不同运算符之间的运算顺序优先级，例如，加法和乘法，加法的优先级低于乘法，所以 10 + 10 * 10，会解析成 10 + (10 * 10) 而非 (10 + 10) * 10。

而结合性决定了相同的运算符连续出现时操作数的组合规则，例如减号是左结合的，所以，10 - 10 - 10 要先运算左边的操作数，再将结果和后面的操作数结合，相当于 (10 - 10) - 10。而右结合则相反，比如我们这里规定 ^ 运算为右结合，那么 10 ^ 10 ^ 10，就相当于 10 ^ (10 ^ 10)。

下面代码用一个对象来配置运算符，key 为运算符，value 为运算符的优先级和结合性。

1
const operators = {
2
  '+': {
3
    precedence: 1,
4
    associativity: 'left',
5
  },
6
  '-': {
7
    precedence: 1,
8
    associativity: 'left',
9
  },
10
  '*': {
11
    precedence: 2,
12
    associativity: 'left',
13
  },
14
  '/': {
15
    precedence: 2,
16
    associativity: 'left',
17
  },
18
  '%': {
19
    precedence: 2,
20
    associativity: 'left',
21
  },
22
  '^': {
23
    precedence: 3,
24
    associativity: 'right',
25
  },
26
}

定义好运算符之后，再定义一对分组用的符号，用于中缀表示法中调整优先级，此处我们按照习惯使用圆括号。

1
const groupStart = '('
2
const groupEnd = ')'

然后，开始实现中缀表示法转逆波兰表示法，此处我们使用一个经典的算法，“调度场算法（Shunting Yard Algorithm）” 来进行。

调度场算法

该算法需要两个数组，一个放输出（即结果），一个当作栈使用，用来存放算法过程的一些运算符。

算法执行过程要点如下：

从左到右扫描中缀表示法的每个元素，根据遇到的不同元素，执行对应的逻辑：

case 1: 当前为操作数
直接输出操作数
case 2: 当前为运算符，且运算符栈空
运算符直接入栈
case 3: 当前为左括号，或运算符栈顶是左括号
运算符直接入栈
case 4: 当前为右括号
运算符栈一直弹出并输出，直至遇到左括号。左括号弹出不输出，右括号舍弃不输出
case 5: 当前为运算符，且运算符栈非空若栈顶是左括号，则停止比较，当前运算符直接入栈若当前运算符优先级大于栈顶运算符，则停止比较，当前运算符直接入栈若当前运算符与栈顶运算符相同，并且当前运算符是右结合的，则停止比较，当前运算符直接入栈其他情况，将栈顶运算符出栈输出，回到 case 5，直至栈空时，将当前运算符入栈

扫描完毕之后，将运算符栈中的所有剩余运算符输出

下面是对应的代码实现

1
// 帮助函数：获取栈顶元素
2
const stackTop = (stack) => stack[stack.length - 1]
3

4
// 帮助函数：是否操作数
5
const isNumber = (n) => /\d/.test(n)
6

7
// 转换函数
8
// infixTokens 即为 ['1', '+', '1'] 形式的中缀表示法的记号流
9
function toRpn(infixTokens) {
10
  const len = infixTokens.length
11
  // 存放输出
12
  const output = []
13
  // 运算符栈
14
  const opStack = []
15

16
  let index = -1
17
  while (++index < len) {
18
    const token = infixTokens[index]
19

20
    // case 1
21
    if (isNumber(token)) {
22
      output.push(token)
23
      continue
24
    }
25

26
    // case 2
27
    // case 3
28
    if (!opStack.length || groupStart === token) {
29
      opStack.push(token)
30
      continue
31
    }
32

33
    // case 4
34
    if (groupEnd === token) {
35
      while (opStack.length) {
36
        const top = opStack.pop()
37
        if (groupStart === top) break
38
        output.push(top)
39
      }
40
      continue
41
    }
42

43
    // assert operator
44
    const op = operators[token]
45
    if (!op) throw new Error(`运算符(${token})未定义`)
46

47
    // case 5
48
    while (opStack.length) {
49
      if (groupStart === stackTop(opStack)) break
50
      const top = stackTop(opStack)
51
      const topOp = operators[top]
52
      if (op.precedence - topOp.precedence > 0) break
53
      if (token === top && topOp.associativity === 'right') break
54
      output.push(opStack.pop())
55
    }
56

57
    opStack.push(token)
58
  }
59

60
  // 将栈中所有剩余运算符输出
61
  while (opStack.length) {
62
    output.push(opStack.pop())
63
  }
64

65
  return output
66
}

通过上面的 toRpn 函数，即可将中缀表示法转换成逆波兰表示法。

1
const rpnTokens = toRpn(["10", "15", "+", "20", "-", "30", "*", "40", "2", "^", "/"])
2
console.log(rpnTokens) // ["10", "15", "20", "+", "30", "40", "2", "^", "*", "/", "-"]

有了后缀表示法记号流之后，我们接下来开始实现计算逻辑。

实现计算

逆波兰表示法的计算，需要利用栈。过程中比较简单，扫描表达式，遇到操作数，则入栈，遇到运算符，则从栈中取出操作数，执行运算。

开始之前，先改进下之前的 operators 定义，为每个运算符指定对应的计算语义，实现运算逻辑。

1
const operators = {
2
  '+': {
3
    precedence: 1,
4
    associativity: 'left',
5
    calc: (a, b) => a + b
6
  },
7
  '-': {
8
    precedence: 1,
9
    associativity: 'left',
10
    calc: (a, b) => a - b
11
  },
12
  '*': {
13
    precedence: 2,
14
    associativity: 'left',
15
    calc: (a, b) => a * b
16
  },
17
  '/': {
18
    precedence: 2,
19
    associativity: 'left',
20
    calc: (a, b) => a / b
21
  },
22
  '%': {
23
    precedence: 2,
24
    associativity: 'left',
25
    calc: (a, b) => a % b
26
  },
27
  '^': {
28
    precedence: 3,
29
    associativity: 'right',
30
    calc: (a, b) => Math.pow(a, b)
31
  },
32
}

注意上面的代码中，每个运算符的定义中都多了一个 calc 函数，该函数接受两个操作数，返回对应的计算结果。

然后开始运算的逻辑实现。

1
// 参数 rpnTokens 为转换好的逆波兰表示法记号流
2
function calc(rpnTokens) {
3
  const stack = []
4
  const len = rpnTokens.length
5
  let position = -1
6
  let result = 0
7

8
  for (let i = 0; i < len; i++) {
9
    const token = rpnTokens[i]
10

11
    if (isNumber(token)) {
12
      position++
13
      stack[position] = token
14
      continue
15
    }
16

17
    const op = operators[token]
18
    if (!op) throw new Error(`运算符(${token})未定义`)
19

20
    // 操作数字符串转数值
21
    const left = +stack[position - 1]
22
    const right = +stack[position]
23
    stack[--position] = op.calc(left, right)
24
  }
25

26
  result = stack[position]
27
  return result
28
}

如此便完成了计算逻辑的实现。

1
calc(rpnTokens) // 0.09375

可以看到代码如期望地计算出了结果。

改进

理解了上面的算法逻辑后，就可以根据需要，增加支持的运算符、修改分组符号、甚至增加其他语法成分的支持了。

如果感兴趣，可以在我的 Github 上获得对应本文一份完整的参考代码。

下篇预告

算术表达式解析系列之优先级爬升法

算术表达式解析系列之逆波兰表示法