之前在字节面试的时候，面试官给我出了一道算法题：给定一个用字符串表示的算式，算式中只有+， -， *， /，请计算出最终结果。
比如 2+3*4-2/2。
很明显，如果没有 * 和 / ，那我们直接一个循环处理即可，但是有了 * 和 /，算式就有了优先级，我们需要先计算优先级高的，在计算优先级低的。
面试官提醒我可以使用栈来处理，我才恍然大悟，然后迅速用代码实现。
面试结束后，我就去细了解了一下这类问题的做法，这种字符串公式的表达叫做：中缀表达式，与之类似的还有前缀表达式和后缀表达式，前缀表达式和后缀表达式又被叫做波兰表达式和逆波兰表达式。

中缀表达式

其实很多读者在数据结构这一门课上，就已经学过中缀表达式了，但是对于我这个非科班的来说，第一次接触还是非常新鲜的，对于学过的朋友权当复习了。
使用栈这种数据结构，可以很好的处理仅有加减乘除四种运算符（不含括号）的公式。
栈是一种先入后出（FILO）的数据结构，可以将数据入栈和出栈，入栈数据会在栈顶，出栈是将栈顶的数据取出。
对 2+3*4-2/2 表达式来说，我们将数字压入栈，如果遇到 * 和 / 这两个优先级高的操作，我们将栈中的数据出栈，和操作符后面的数据进行 * 和 / 操作之后，将结果入栈，遇到 + 则不做操作，遇到 - 则对后一个数据进行取负，将数据压入栈即可。

就对 2+3*4-2/2 举例子：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

轮询到第一个数字 2 压入栈中，当前栈 [2]
操作符 +， 抛弃
数字 3 压入栈，当前栈：[2, 3]
操作符 *,将栈顶取出一个值 3，当前栈 [2]
将下一个数字 4 和刚刚取出的值 3 做 * 操作得到 12，压入栈，目前栈：[2, 12]
操作符 -, 对下一个数取负
数字 2，取负后压入栈，目前栈 [2, 12, -2]
操作符 /, 取出栈顶值 -2,目前栈 [2, 12]
将下一个数字 2 和刚刚取出的值 -2 做 / 操作得到 1,压入栈，目前栈 [2, 12, -1]
最后对栈里的数据进行相加，得到 2+12-1 = 13

13 即是最终值。
因为 golang 中没有现成的栈 api，我们需要用队列来手动实现一个。
实现代码如下：

 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


type Stack struct {
   Data []int
}

func (s *Stack) isEmpty() bool {
   if len(s.Data) == 0 {
      return true
   }
   return false
}

func (s *Stack) push(num int) {
   s.Data = append(s.Data, num)
}

func (s *Stack) pop() int {
   num := s.Data[len(s.Data)-1]
   s.Data = s.Data[:len(s.Data)-1]
   return num
}

func (s *Stack) top() int {
   return s.Data[len(s.Data)-1]
}

func getStack() *Stack {
   return &Stack{}
}

栈的基本功能已经实现，有：

  • push 方法，在栈顶压入数据
  • pop 方法，从栈顶删除一个数据，并返回该数据
  • top 方法，去栈顶的数据返回，不删除栈顶数据
  • isEmpty 方法，判断栈是否为空

下面我们来实现计算中缀表达式的代码：

 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


func calculator(s string) int {
   var stack = getStack()
   num := 0
   var op byte = '+'
   for i := 0; i < len(s); i++ {
      isDigit := s[i] >= '0' && s[i] <= '9'
      if isDigit {
         num = 10*num + int(s[i]-'0')
      }
      // 需要处理轮询到最后一位的数据，最后一位的数据肯定是数字
      if !isDigit || i == len(s)-1 {
         switch op {
         case '+':
            stack.push(num)
         case '-':
            stack.push(-num)
         case '*':
            stack.push(stack.pop() * num)
         default:
            stack.push(stack.pop() / num)
         }
         op = s[i]
         num = 0
      }
   }
   var ans = 0
   for _, num := range stack.Data {
      ans += num
   }
   return ans
}

逆波兰表达式（后缀表达式）

对中缀表达式来说，如果不涉及 （） 这种计算，那么用上面的代码即可处理，但是一旦涉及了 （），计算就会非常复杂。
波兰的一位逻辑学家卢卡西维兹在 1929 年提出了一种计算表达式的表达方法： 将操作符放到操作数之前（中缀表达式是将操作符放到操作数中间）。
由于操作符在操作数之前，于是这种表达式被叫做前缀表达式，因为发明者是波兰人，这种表达式又被叫做波兰表达式。
很明显，逆波兰表达式就是操作符在操作数之后的。
举个例子：

  • 中缀表达式为：2+3*2-2
  • 波兰表达式为：[-, +, 2, *, 3, 2, 2]
  • 逆波兰表达式为：[2, 3, 2, *, +, 2, -]

我们来看看如何计算逆波兰表达式。
根据逆波兰表达式的特点，操作符是表示前两个数的操作的，比如 [3, 2, *],代表的就是 3 * 2。
那么我们在对表达式轮询的时候，如果是操作数，就压入栈中，如果是操作符，那么就把栈顶的两个数据取出，进行操作之后，压入栈中。
轮询完之后，栈顶的数据就是我们需要的值。
代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func reversePolishNotation(notation []string) int {
   var stack = getStack()
   for _, v := range notation {
      num, err := strconv.Atoi(v)
      if err == nil {
         stack.push(num)
      } else {
         num1, num2 := stack.pop(), stack.pop()
         switch v {
         case "+":
            stack.push(num2 + num1)
         case "-":
            stack.push(num2 - num1)
         case "/":
            stack.push(num2 / num1)
         default:
            stack.push(num2 * num1)
         }
      }
   }
   return stack.top()
}

中缀表达式转逆波兰表达式

我们通过各种表达式的表达中可以发现：
中缀表达式为：2+3*2-2
逆波兰表达式为：[2, 3, 2, *, +, 2, -]
操作数的顺序是没有变化的，都是 2、3、2、2
只有操作符的顺序发生了改变，那么我们在中缀表达式转逆波兰表达式中，维护一个操作符的栈，一个操作数的栈，然后将操作符插入操作数的栈中即可。
以下是具体的操作步骤：

  • 遇到操作数，将操作数压入操作数栈中
  • 遇到操作符，在操作符栈中找平级或更高级的操作符，依次将这些操作符压入操作数栈，将本身轮询到的操作符压入栈中
  • 遇到界限符 ()，如果是 ( 直接压入操作符栈中，遇到 )，就在操作符中往前查找，直到找到 (，将中间遇到的所有操作符都加到操作数栈中，然后将 ( 删除

中缀表达式轮询完毕，将操作符栈里面的所有数据都加到操作数中。
操作数栈数据即为逆波兰表达式
我们来模拟一次：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

中缀表达式：2+3-(2+4*2)+2/2
操作数栈：[]  操作符栈: []
轮询 1：2 是操作数，直接压入操作数栈。操作数栈：[2]  操作符栈: []
轮询 2: + 是操作符，此时操作符栈为空，没有平级或更高级的操作符，直接将 + 压入操作符栈。操作数栈：[2]  操作符栈: [+]
轮询 3: 3 是操作数，直接压入操作数栈。操作数栈：[2, 3]  操作符栈: [+]
轮询 4: - 是操作符，操作符栈中有 + 是平级，将 + 压入操作数栈，- 压入操作符栈。操作数栈：[2, 3, +]  操作符栈: [-]
轮询 5: ( 是界限符，直接压入操作符栈。操作数栈：[2, 3, +]  操作符栈: [-, (]
轮询 6: 2 是操作数，直接压入操作数栈。操作数栈：[2, 3, +, 2]  操作符栈: [-, (]
轮询 7: + 是操作符，操作符栈里往前只有 (, 没有平级或更高级操作符。直接将 + 压入操作符栈中。操作数栈：[2, 3, +, 2]  操作符栈: [-, (, +]
轮询 8: 4 直接加到操作数栈中。操作数栈：[2, 3, +, 2, 4]  操作符栈: [-, (, +]
轮询 9: * 操作符，栈中往前找，没有更高级的，压入操作符栈中。操作数栈：[2, 3, +, 2, 4]  操作符栈: [-, (, +, *]
轮询 10: 2 直接压入操作数栈。操作数栈：[2, 3, +, 2, 4, 2]  操作符栈: [-, (, +, *]
轮询 11: ) 界限符。栈中往前找 (,将中间的操作符压入操作数栈。操作数栈：[2, 3, +, 2, 4, 2, *, +]  操作符栈: [-]
轮询 12: +, 往前有 -, 将 - 加到操作数栈。操作数栈：[2, 3, +, 2, 4, 2, *, +, -]  操作符栈: [+]
轮询 13: 2 直接压入操作数栈。操作数栈：[2, 3, +, 2, 4, 2, *, +, -, 2]  操作符栈: [+]
轮询 14: /,往前没有平级或更高级操作符。操作数栈：[2, 3, +, 2, 4, 2, *, +, -, 2]  操作符栈: [+, /]
轮询 15: 2 压入栈中。操作数栈：[2, 3, +, 2, 4, 2, *, +, -, 2, 2]  操作符栈: [+, /]

退出循环。判断操作符栈。
操作符栈不为空，以此加到操作数栈中。
操作数栈：[2, 3, +, 2, 4, 2, *, +, -, 2, 2, /, +]  操作符栈: []

[2, 3, +, 2, 4, 2, *, +, -, 2, 2, /, +] 即为逆波兰表达式。
里面涉及了一个操作符优先级的比较，我们先写一个方法比较：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


func lowerOP(op1, op2 string) bool {
   switch op1 {
   case "+", "-":
      if op2 == "*" || op2 == "/" {
         return true
      }
   case "(":
      return true
   }
   return false
}

该方法名是 lowerOP，返回 true 代表 op1 比 op2 低级，false 代表 op1 比 op2 高级。
op1 代表操作符栈中的数据，op2 代表循环的中缀表达式中的操作符。
如果 op1 是 + 或者 -，那么就比 op2 的 * 或 / 要低级。
如果 op1 是 (, 直接返回 true，因为 ( 是界限符，不参与比较，循环到这里就要停止。
其他情况，都是 op1 比 op2 优先级高。
我们还需要注意一点，上面写的 stack api ，只能接受 int 类型数据，波兰表达式里面是 string 类型数据，需要对 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

func CoverToReversePolishNotation(s string) []string {
   var opStack, numStack = getStack(), getStack()
   for i := 0; i < len(s); {
      isDigit := s[i] <= '9' && s[i] >= '0'
      if isDigit {
         num := int(s[i] - '0')
         j := i + 1
         for ; j < len(s); j++ {
            if s[j] <= '9' && s[j] >= '0' {
               num = 10*num + int(s[j]-'0')
            } else {
               break
            }
         }
         numStack.push(strconv.Itoa(num))
         i = j
         continue
      }
      if !isDigit {
         op := string(s[i])
         switch op {
         case "(":
            opStack.push(op)
         case ")":
            for !opStack.isEmpty() {
               op := opStack.pop()
               if op == "(" {
                  break
               }
               numStack.push(op)
            }
         default:
            for !opStack.isEmpty() {
               op1 := opStack.pop()
               if op1 == "(" || lowerOP(op1, op) {
                  opStack.push(op1)
                  break
               }
               numStack.push(op1)
            }
            opStack.push(op)
         }
      }
      i++
   }
   for !opStack.isEmpty() {
      numStack.push(opStack.pop())
   }
   return numStack.Data
}

我们可以看到代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

  if isDigit {
      num := int(s[i] - '0')
      j := i + 1
      for ; j < len(s); j++ {
        if s[j] <= '9' && s[j] >= '0' {
          num = 10*num + int(s[j]-'0')
        } else {
          break
        }
      }
      numStack.push(strconv.Itoa(num))
      i = j
      continue
    }

这是为了处理有可能多位数字，比如 12、13 等。
如果循环到当前，发现是数字，就另起循环，对下一个数进行探测，如果是数字，就 10*num + int(s[j]-'0’)
如果不是数据，就终止循环，然后将外层循环的指针 i ，指向 j，把数字压入操作数栈中。
核心逻辑代码：

 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

  if !isDigit {
      op := string(s[i])
      switch op {
      case "(":
        opStack.push(op)
      case ")":
        for !opStack.isEmpty() {
          op := opStack.pop()
          if op == "(" {
            break
          }
          numStack.push(op)
        }
      default:
        for !opStack.isEmpty() {
          op1 := opStack.pop()
          if op1 == "(" || lowerOP(op1, op) {
            opStack.push(op1)
            break
          }
          numStack.push(op1)
        }
        opStack.push(op)
      }
    }

case ( 和 case ) 都比较简单。
只有 default 里面涉及到了 op1 和 op 的比较。
op1 是操作符栈中取出的数据，op 是循环到当前 s 中的操作符。
如果 op1 比 op 优先级高或平级，那么加入操作数栈中。
我们试着输入：

  • 输入：2+3-(2+4*2)+2/2
  • 输出：[2 3 + 2 4 2 * + - 2 2 / +]

输出结果和我们之前模拟结果：[2, 3, +, 2, 4, 2, *, +, -, 2, 2, /, +] 是一致的。

结尾

无论是中缀表达式还是逆波兰表达式，其实都是栈的应用，无非就是中缀表达式转逆波兰表达式的时候，需要注意的点有点多，需要操作的逻辑比较负责，其实核心还是不停使用栈的 pop 和 push 方法，利用栈的后进先出，来实现我们的需要。

参考资料