逆波兰式

名字很高大上？不，它很简单

1+1

A：别急着理解标题，先看看 1 + 1。

A：1+1 是什么？

B：是 2 ？

A：不不不，我要说的不是这个，在表达式层面来讲，它是最简单的表达式。

A：它由 1 + 1 组成。

B：这不是废话吗。

A：不不不，我说的是。

A：它由 1 + 1 组成。

A：而不是 + 1 1

A：也不是 1 1 +

B：你有病吗？

A：哈哈哈，这就引出了我们的标题，符合我们常理的 1+1 称为中缀表达式，符号在中间嘛。而 +11 是前缀表达式。

B: 我猜 11+ 是后缀表达式。

A：你他娘真是个人才。确实它是后缀表达式。也称为 逆波兰式。

B：我去，绕这么大一圈…….

A：不扯淡了，进入正题吧。

后缀表达式

它是如何定义的呢？

E 为常量或变量

如果E是一个常量或变量，那E的后缀式是它本身

比如，2 是 2 的后缀式。

E1 op E2 的形式

如果E是E1 op E2形式的表达式，这里op是任何二元操作符，则E的后缀式为E1’E2’ op，这里E1’和E2’分别为E1和E2的后缀式。

这很好理解。

1+2 => 12+
以下是上一条规则：
1 => 1的后缀式
2 => 2的后缀式

加上括号的 E

如果E是（E1）形式的表达式，则E1的后缀式就是E的后缀式

这条也好理解。

1+1 的后缀式 与 (1+1) 的后缀式相同。

中缀 -> 后缀

A：现在给你派一批任务，将中缀表达式转换为后缀表达式，你能完成吗。
B：SO EASY！

a + b

B: ab+

(a+b)/e

B: （a+b)e/
B: (a+b) 与 a+b 后缀式应该相同。那：ab+e/
B：最后是这个吧 ab+e/

(a+b)*c

B：跟上面差不多，ab+c*

(a+b)*c-(a+b)/e

B: 不就是把前两部放一块儿了吗，可以先用括号包起来 ((a+b)c)-((a+b)/e)，整体算一下 ((a+b)c)((a+b)/e)-，括号内部再做转换

B：ab+c*ab+e/-

整这么复杂干啥

B: 这就完了吗。

A：完了，我说过了，很简单的。在构造后缀表达式的时候，只要考虑好运算符的优先级，就可万无一失

B：你整这么复杂干啥，中缀表达式看的挺爽，干嘛转成后缀呢？

A：嗯，中缀对于我们来说看的很爽，但对于代码实现来说，就很不爽了。

计算器

用户输入了一串表达式：(a+b)*c-(a+b)/e
快～快用代码计算下结果！
过去5s……
10s……
怎么还没算出来呀！什么！你不会！好吧好吧，因为要考虑到运算符优先级，这个难度确实高。

biubiubiu～

试试这个，直接按以下规则计算即可。

ab+c*ab+e/-

规则：

字符按顺序出 stack 栈，
如果是数字，则添加到 byte 栈里，
如果是符号，则拿 byte 的栈顶两项数字，进行运算，将运算结果入栈，直到 stack 为空

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

const stack = [a, b,'+',c,'*',a,b,'+',e,'/','-']

function calculator(arr) {
  const op = ['+', '-', '*', '/']
  const byte = []
  while(arr.length) {
    let now = arr.shift()
    const index = op.indexOf(now)
    // 是符号
    if(index !== -1) {
      // 栈顶两元素
      const end = byte.pop(),
            first = byte.pop();
      switch(index){
        case 0:
          byte.push( first + end)
          break;
        case 1:
          byte.push( first - end)
          break;
        case 2:
          byte.push( first * end)
          break;
        case 3:
          byte.push( first / end)
          break;
      }
    // 不是符号
    } else {
      byte.push(now)
    }
  }
  console.log(byte)
}

大概是这样的
a => b => +

可以累加了 a + b = r1

继续出

r1 => c => *

可以累乘了 r1 * c = r2

继续出

r2 => a => b => +

可以累加了 a + b = r3

继续出

r2 => r3 => e => /

可以 除法 了 r3 / e = r4

继续出
r2 => r4 => -

可以减法了

r2 - r4 = r5

花费 0.000000001 s，结果是 r5。

因为不考虑优先级，所以按照顺序计算，就可以把后缀表达式计算完成。不仅代码实现快，运行的也快～这就是为什么把中缀转为后缀的原因。

后/前缀表达式语言 LISP

既然后/前缀表达式的执行效率高，那有没有后/前缀编程语言呢？

当然有。

先看看它的代码如何： 

1
2
3
4
5
6
7
8
(setq a 10)
(setq b 20)
(format t "~% A + B = ~d" (+ a b))
(format t "~% A - B = ~d" (- a b))
(format t "~% A x B = ~d" (* a b))
(format t "~% B / A = ~d" (/ b a))
(format t "~% Increment A by 3 = ~d" (incf a 3))
(format t "~% Decrement A by 4 = ~d" (decf a 4))

输出

1
2
3
4
5
6
7
8
A + B = 30
A - B = -10
A x B = 200
B / A = 2
Increment A by 3 = 13
Decrement A by 4 = 9

//原文出自【易百教程】，商业转载请联系作者获得授权，非商业请保留原文链接:https://www.yiibai.com/lisp/lisp_operators.html

本文不是来推崇 lisp 的，你可以点击这篇文章了解更多：
上帝的lisp

中缀转后缀

B：emmm，后缀简单是简单，但写起来也太反人类了

A: 对呀，所以现代编程语言在计算机运算和代码可编写性上做了取舍，我们也不需要人肉换算逆波兰式了。不过，我们可以用代码先从中缀转后缀，再计算后缀表达式，来实现简单的计算器。

A：首先，我们得实现中缀转后缀，逻辑是这样的：

  • 首先构造 S1 运算符栈，和 S2 结果栈。中缀表达式 str 栈
  • str 按运算顺序从左到右出栈。
    • 当字符为数字时，直接压栈 S2
    • 当字符为运算符时
      • 如果 S1 栈顶元素优先级高于当前字符，则将 S1 栈顶元素出栈，并压栈 S2，直到 S1 栈顶元素优先级低于当前字符。最后，将当前字符压栈 S1
      • 如果 S1 栈顶元素优先级低于当前字符，则当前字符压栈 S1
    • 当字符为 （ 时，直接压栈,之后字符按照以上规则压栈。
    • 当字符为 ）时，取与最近的 （ 中间的运算符，重复以上步骤
  • 当 str 栈空，依次出 S1 的栈

用 javascript 实现它 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

function calculator(str) {
  let n = 0, charStack = [], numStack = [], reducerStr =  [], leftIndex = -1
  const op = {
    '+' : 1,
    '-' : 1,
    '*' : 2,
    '/' : 2,
    '(' : 3,
    ')' : 3
  }
  while(n < str.length) {
    const byte = str[n]
    // 数字
    if(/\d/.test(byte)) {
      reducerStr.push(byte)
    } else if(/\(|\)/.test(byte)) {
      // 左括号入栈
      if(byte === '(') {
        charStack.push(byte)
        leftIndex = n
        console.log('左括号', byte)
      // 右括号出栈
      } else {
        let nowChar = charStack.pop()
        while(nowChar && nowChar !== '(') {
          reducerStr.push(nowChar)
          nowChar = charStack.pop()
        }
      }
    // 符号
    } else {
      // 字符栈顶元素
      let nowChar = charStack[charStack.length - 1]
      while(nowChar && op[byte] < op[nowChar] && nowChar !== '(') {
        charStack.pop()
        reducerStr.push(nowChar)
        nowChar = charStack[charStack.length - 1]
      }
      charStack.push(byte)
    }
    n++
  }
  while(charStack.length) {
    reducerStr.push(charStack.pop())
  }
  return reducerStr.join('')
}

便于理解，我写了一个简单的 demo ，让转换过程可视化。你可以戳以下链接去推理一边。

可视化理解转换过程

我们实现了中缀转后缀，又实现了后缀表达式的计算，剩余的工作就是将这二者结合起来。这里就不演示了。

完