Arthur's Blog

问题

如果只能进行两个值的加减乘除，如何编程计算一个数学表达式的值？
比如计算 1+2*3+(4*5+6)*7，我们知道优先级顺序 () 大于 * / 大于 + - ，直接计算得 1+6+26*7 = 189

中缀、后缀表达式的计算

人利用中缀表达式计算值

数学表达式的记法分为前缀、中缀和后缀记法，其中中缀就是上边的算术记法： 1+2*3+(4*5+6)*7，人计算中缀表达式的值：把表达式分为三部分1 2+3 (4*5+6)*7 分别计算值，求和得 189。但这个理解过程在计算机上的实现就复杂了。

计算机利用后缀表达式计算值

中缀表达式 1+2*3+(4*5+6)*7 对应的后缀表达式： 123*+45*6+7*+，计算机使用栈计算后缀表达式值：

计算后缀表达式的代码实现

1.  
   func calculate(postfix string) int {
2.  
   stack := stack.ItemStack{}
3.  
   fixLen := len(postfix)
4.  
   for i := 0; i < fixLen; i++ {
5.  
   nextChar := string(postfix[i])
6.  
   // 数字：直接压栈
7.  
   if unicode.IsDigit(rune(postfix[i])) {
8.  
   stack.Push(nextChar)
9.  
   } else {
10.  
    // 操作符：取出两个数字计算值，再将结果压栈
11.  
    num1, _ := strconv.Atoi(stack.Pop())
12.  
    num2, _ := strconv.Atoi(stack.Pop())
13.  
    switch nextChar {
14.  
    case "+":
15.  
    stack.Push(strconv.Itoa(num1 + num2))
16.  
    case "-":
17.  
    stack.Push(strconv.Itoa(num1 - num2))
18.  
    case "*":
19.  
    stack.Push(strconv.Itoa(num1 * num2))
20.  
    case "/":
21.  
    stack.Push(strconv.Itoa(num1 / num2))
22.  
    }
23.  
    }
24.  
    }
25.  
    result, _ := strconv.Atoi(stack.Top())
26.  
    return result
27.  
    }

现在只需知道如何将中缀转为后缀，再利用栈计算即可。

中缀表达式转后缀表达式

转换过程

从左到右逐个字符遍历中缀表达式，输出的字符序列即是后缀表达式：

• 遇到数字直接输出

• 遇到运算符则判断：

  • 栈顶运算符优先级更低则入栈，更高或相等则直接输出
  • 栈为空、栈顶是 ( 直接入栈
  • 运算符是 ) 则将栈顶运算符全部弹出，直到遇见 )
• 中缀表达式遍历完毕，运算符栈不为空则全部弹出，依次追加到输出

转换的代码实现

1.  
   // 中缀表达式转后缀表达式
2.  
   func infix2ToPostfix(exp string) string {
3.  
   stack := stack.ItemStack{}
4.  
   postfix := ""
5.  
   expLen := len(exp)
6.  
    
7.  
   // 遍历整个表达式
8.  
   for i := 0; i < expLen; i++ {
9.  
    
10.  
    char := string(exp[i])
11.  
     
12.  
    switch char {
13.  
    case " ":
14.  
    continue
15.  
    case "(":
16.  
    // 左括号直接入栈
17.  
    stack.Push("(")
18.  
    case ")":
19.  
    // 右括号则弹出元素直到遇到左括号
20.  
    for !stack.IsEmpty() {
21.  
    preChar := stack.Top()
22.  
    if preChar == "(" {
23.  
    stack.Pop() // 弹出 "("
24.  
    break
25.  
    }
26.  
    postfix += preChar
27.  
    stack.Pop()
28.  
    }
29.  
     
30.  
    // 数字则直接输出
31.  
    case "0", "1", "2", "3", "4", "5", "6", "7", "8", "9":
32.  
    j := i
33.  
    digit := ""
34.  
    for ; j < expLen && unicode.IsDigit(rune(exp[j])); j++ {
35.  
    digit += string(exp[j])
36.  
    }
37.  
    postfix += digit
38.  
    i = j - 1 // i 向前跨越一个整数，由于执行了一步多余的 j++，需要减 1
39.  
     
40.  
    default:
41.  
    // 操作符：遇到高优先级的运算符，不断弹出，直到遇见更低优先级运算符
42.  
    for !stack.IsEmpty() {
43.  
    top := stack.Top()
44.  
    if top == "(" || isLower(top, char) {
45.  
    break
46.  
    }
47.  
    postfix += top
48.  
    stack.Pop()
49.  
    }
50.  
    // 低优先级的运算符入栈
51.  
    stack.Push(char)
52.  
    }
53.  
    }
54.  
     
55.  
    // 栈不空则全部输出
56.  
    for !stack.IsEmpty() {
57.  
    postfix += stack.Pop()
58.  
    }
59.  
     
60.  
    return postfix
61.  
    }
62.  
     
63.  
    // 比较运算符栈栈顶 top 和新运算符 newTop 的优先级高低
64.  
    func isLower(top string, newTop string) bool {
65.  
    // 注意 a + b + c 的后缀表达式是 ab + c +，不是 abc + +
66.  
    switch top {
67.  
    case "+", "-":
68.  
    if newTop == "*" || newTop == "/" {
69.  
    return true
70.  
    }
71.  
    case "(":
72.  
    return true
73.  
    }
74.  
    return false
75.  
    }

总结

计算机计算数学表达式的值分成了 2 步，利用 stack 将人理解的中缀表达式转为计算机理解的后缀表达式，再次利用 stack 计算后缀表达式的值。