概述

表达式一般由操作数(Operand)、运算符(Operator)组成，例如算术表达式中，通常把运算符放在两个操作数的中间，
这称为中缀表达式(Infix Expression)，如A+B。
波兰数学家Jan Lukasiewicz提出了另一种数学表示法，它有两种表示形式：
把运算符写在操作数之前，称为波兰表达式(Polish Expression)或前缀表达式(Prefix Expression)，如+AB；
把运算符写在操作数之后，称为逆波兰表达式(Reverse Polish Expression)或后缀表达式(Suffix Expression)，如AB+；
其中，逆波兰表达式在编译技术中有着普遍的应用。

算法

一、 将中缀表达式转换成后缀表达式算法：

1、从左至右扫描一中缀表达式。
2、若读取的是操作数，则判断该操作数的类型，并将该操作数存入操作数堆栈
3、若读取的是运算符
(1) 该运算符为左括号”(“，则直接存入运算符堆栈。
(2) 该运算符为右括号”)”，则输出运算符堆栈中的运算符到操作数堆栈，直到遇到左括号为止。
(3) 该运算符为非括号运算符：
(a) 若运算符堆栈栈顶的运算符为括号，则直接存入运算符堆栈。
(b) 若比运算符堆栈栈顶的运算符优先级高或相等，则直接存入运算符堆栈。
(c) 若比运算符堆栈栈顶的运算符优先级低，则输出栈顶运算符到操作数堆栈，并将当前运算符压入运算符堆栈。
4、当表达式读取完成后运算符堆栈中尚有运算符时，则依序取出运算符到操作数堆栈，直到运算符堆栈为空。

二、逆波兰表达式求值算法：

1、循环扫描语法单元的项目。
2、如果扫描的项目是操作数，则将其压入操作数堆栈，并扫描下一个项目。
3、如果扫描的项目是一个二元运算符，则对栈的顶上两个操作数执行该运算。
4、如果扫描的项目是一个一元运算符，则对栈的最顶上操作数执行该运算。
5、将运算结果重新压入堆栈。
6、重复步骤2-5，堆栈中即为结果值。

实现

将中缀表达式转后缀表达式

将人们熟悉的中缀表达式转换为后缀表达式，便于计算机的计算，这里需要用到栈数据结构。

  1. // 定义符号优先级
  2. var symbolMap = map[string]int{
  3.     "+": 1,
  4.     "-": 1,
  5.     "*": 2,
  6.     "/": 2,
  7.     "(": 3,
  8.     ")": 3,
  9. }
  11. func main() {
  12.     // 待解析的表达式
  14.     var str string = "1+1+(2+3)+3-3+4"
  15.     // 检查括号是否对齐
  16.     bracketCheck(str)
  17.     suffixExp := trans2SuffixExp(str)
  18.     fmt.Println("后缀表达式：", suffixExp)
  19.     // 计算
  20.     ret := parseExpression(str)
  21.     fmt.Printf("表达式[%s]=%d", str, ret)
  22. }
  24. func trans2SuffixExp(exp string) string {
  25.     var resultStr = ""
  27.     var stack = InitStack(20)
  28.     for _, e := range exp {
  29.         ele := string(e)
  30.         if unicode.IsNumber(e) {
  31.             resultStr += ele
  32.             continue
  33.         }
  34.         // 操作符
  35.         if stack.isEmpty() {
  36.             stack.Push(ele)
  37.             continue
  38.         }
  39.         // 将栈顶元素比当前元素优先级高的出栈，追加到表达式后面
  40.         topEleStr := fmt.Sprintf("%v", stack.TopEle())
  41.         if ele != ")" && symbolMap[topEleStr] < symbolMap[ele] {
  42.             stack.Push(ele)
  43.             continue
  44.         }
  45.         // 栈顶是左括号直接入栈
  46.         if "(" == topEleStr {
  47.             stack.Push(ele)
  48.             continue
  49.         }
  51.         if ")" == ele {
  52.             // 弹出栈顶元素，直到遇到（
  53.             for {
  54.                 topEleStr := fmt.Sprintf("%v", stack.Pop())
  55.                 if topEleStr == "(" {
  56.                     break
  57.                 }
  58.                 resultStr += topEleStr
  59.             }
  60.         } else {
  61.             // 弹出栈顶优先级大于等于当前元素的符号
  62.             for {
  63.                 topEleStr = fmt.Sprintf("%v", stack.TopEle())
  64.                 if symbolMap[topEleStr] < symbolMap[ele] {
  65.                     break
  66.                 }
  67.                 // 追加
  68.                 resultStr += fmt.Sprintf("%v", stack.Pop())
  69.             }
  70.             // 当前符号入栈
  71.             stack.Push(ele)
  72.         }
  73.     }
  75.     // 弹出栈内所有元素
  76.     for !stack.isEmpty() {
  77.         resultStr += fmt.Sprintf("%v", stack.Pop())
  78.     }
  79.     return resultStr
  80. }

计算后缀表达式的结果

上小结已经得到了表达式的后缀表达式，那么我们可以直接利用后缀表达式计算结果了，这里也需要用到栈数据结构

  1. func calSuffixExp(exp string) interface{} {
  2.   // 根据后缀表达式计算
  3.   numStack := InitStack(20)
  4.   for _, e := range exp {
  5.     if unicode.IsNumber(e) {
  6.       num, _ := strconv.ParseInt(string(e), 0, 64)
  7.       numStack.Push(num)
  8.       continue
  9.     }
  10.     // 符号
  11.     cal(string(e), numStack)
  12.   }
  13.   result := numStack.Pop()
  14.   return result
  15. }
  17. func cal(symbol string, stack *Stack) {
  18.   sec, _ := stack.Pop().(int64)
  19.   first, _ := stack.Pop().(int64)
  20.   if "+" == symbol {
  21.     stack.Push(first + sec)
  22.   } else if "-" == symbol {
  23.     stack.Push(first - sec)
  24.   } else if "*" == symbol {
  25.     stack.Push(first * sec)
  26.   } else if "/" == symbol {
  27.     stack.Push(first / sec)
  28.   }
  29. }

测试

  1. func main() {
  2.     // 待解析的表达式
  3.     var str string = "1+1+(2+3)+3-3+4"
  4.     fmt.Println("中缀表达式：", str)
  5.     // 检查括号是否对齐
  6.     bracketCheck(str)
  7.     suffixExp := trans2SuffixExp(str)
  8.     fmt.Println("后缀表达式：", suffixExp)
  9.     result := calSuffixExp(suffixExp)
  10.     fmt.Println("后缀表达式计算结果：", result)
  11. }

输出

中缀表达式： 1+1+(2+3)+3-3+4 后缀表达式： 11+23++3+3-4+ 后缀表达式计算结果： 11

通过中缀表达式一步计算

上文我们通过先将中缀表达式转后缀表达式完成后再计算，这里用到了两个栈帧，一个符号栈，一个数字栈，我们如果结合两个栈空间同样可以一步计算到位（过程中有转后缀及计算的含义）

  2. func parseExpression(str string) Element {
  3.     symbolStack := InitStack(20)
  4.     numStack := InitStack(20)
  5.     var currNum = ""
  6.     for _, ch := range str {
  7.         ele := string(ch)
  8.         if unicode.IsNumber(ch) {
  9.             currNum += ele
  10.             continue
  11.         }
  12.         // 操作数入栈
  13.         if currNum != "" {
  14.             num, _ := strconv.ParseInt(currNum, 0, 32)
  15.             numStack.Push(num)
  16.             currNum = ""
  17.         }
  18.         if symbolStack.isEmpty() || "(" == ele {
  19.             // 第一个操作符直接入栈
  20.             symbolStack.Push(ele)
  21.             continue
  22.         }
  23.         topSymbol := symbolStack.TopEle()
  24.         var symbolStr = fmt.Sprintf("%v", topSymbol)
  25.         // 栈顶操作符的优先级更低，当前操作符直接入栈
  26.         if symbolMap[symbolStr] < symbolMap[ele] && ")" != ele {
  27.             symbolStack.Push(ele)
  28.             continue
  29.         }
  30.         if "(" == symbolStr {
  31.             symbolStack.Push(ele)
  32.             continue
  33.         }
  34.         // 当前操作符优先级较高
  35.         if ")" == ele {
  36.             for {
  37.                 // 弹出栈顶操作符直到遇到“（”
  38.                 symbolStr = fmt.Sprintf("%v", symbolStack.Pop())
  39.                 if symbolStr == "(" {
  40.                     break
  41.                 }
  42.                 cal(symbolStr, numStack)
  43.             }
  44.         } else {
  45.             for {
  46.                 symbolStr = fmt.Sprintf("%v", symbolStack.Pop())
  47.                 if symbolStr == "<nil>" {
  48.                     break
  49.                 } else if symbolMap[symbolStr] < symbolMap[ele] {
  50.                     symbolStack.Push(symbolStr)
  51.                     break
  52.                 }
  53.                 cal(symbolStr, numStack)
  54.             }
  55.         }
  56.         // 当前操作符入栈
  57.         if ")" != ele {
  58.             symbolStack.Push(ele)
  59.         }
  60.         //
  61.     }
  63.     if currNum != "" {
  64.         num, _ := strconv.ParseInt(currNum, 0, 32)
  65.         numStack.Push(num)
  66.         currNum = ""
  67.     }
  69.     // 计算剩余表达式
  70.     for !symbolStack.isEmpty() {
  71.         symbolStr := fmt.Sprintf("%v", symbolStack.Pop())
  72.         cal(symbolStr, numStack)
  73.     }
  74.     // 操作数栈中栈顶元素就为结果：
  75.     ret := numStack.Pop()
  76.     return ret
  77. }
  79. func cal(symbol string, stack *Stack) {
  80.     sec, _ := stack.Pop().(int64)
  81.     first, _ := stack.Pop().(int64)
  82.     if "+" == symbol {
  83.         stack.Push(first + sec)
  84.     } else if "-" == symbol {
  85.         stack.Push(first - sec)
  86.     } else if "*" == symbol {
  87.         stack.Push(first * sec)
  88.     } else if "/" == symbol {
  89.         stack.Push(first / sec)
  90.     }
  91. }