需求

输入一个表达式，返回计算结果。比如： 3 + 2 * 6 - 2 = 13
按照运算符的优先级进行正确的运算

思路

image.png

代码

  1. // 栈的运用 - 计算表达式
  3. package main
  5. import (
  6.     "errors"
  7.     "fmt"
  8.     "strconv"
  9. )
  11. type Stack struct {
  12.     MaxTop int     // 栈的容量
  13.     Top    int     // 栈顶下标 默认 -1
  14.     arr    [20]int // 数组模拟栈
  15. }
  17. // 入栈
  18. func (stack *Stack) Push(val int) (err error) {
  19.     // 栈满
  20.     if stack.Top == stack.MaxTop-1 {
  21.         fmt.Println("stack full")
  22.         return errors.New("stack full")
  23.     }
  24.     stack.Top++
  25.     // 放入数据
  26.     stack.arr[stack.Top] = val
  27.     return
  28. }
  30. // 出栈
  31. func (stack *Stack) Pop() (val int, err error) {
  32.     if stack.Top == -1 {
  33.         fmt.Println("空栈")
  34.         return 0, errors.New("空栈")
  35.     }
  36.     // 取出数据
  37.     val = stack.arr[stack.Top]
  38.     stack.Top--
  39.     return val, nil
  40. }
  42. // 遍历栈
  43. func (stack *Stack) List() {
  44.     if stack.Top == -1 {
  45.         fmt.Println("空栈")
  46.         return
  47.     }
  49.     for i := stack.Top; i >= 0; i-- {
  50.         fmt.Printf("arr[%d] = %v \n", i, stack.arr[i])
  51.     }
  53. }
  55. // 判断是运算符的函数 + - * / , 利用 ASCII 码
  56. func (stack *Stack) IsOper(val int) bool {
  57.     if val == 42 || val == 43 || val == 45 || val == 47 {
  58.         return true
  59.     } else {
  60.         return false
  61.     }
  62. }
  64. // 运算的方法
  65. func (stack *Stack) Cal(num1 int, num2 int, oper int) int {
  66.     // 注意运算的顺序
  67.     res := 0
  68.     switch oper {
  69.     case 42:
  70.         res = num2 * num1
  71.     case 43:
  72.         res = num2 + num1
  73.     case 45:
  74.         res = num2 - num1
  75.     case 47:
  76.         res = num2 / num1
  77.     default:
  78.         fmt.Println("运算符错误")
  79.     }
  80.     return res
  81. }
  83. // 返回运算符的优先级： * / => 1 ; + - => 0
  84. func (stack *Stack) Priority(oper int) int {
  85.     res := 0
  86.     if oper == 42 || oper == 47 {
  87.         res = 1
  88.     } else if oper == 43 || oper == 45 {
  89.         res = 0
  90.     }
  91.     return res
  92. }
  94. func main() {
  95.     // 数栈
  96.     numStack := &Stack{
  97.         MaxTop: 20,
  98.         Top:    -1,
  99.     }
  101.     // 符号栈
  102.     operStack := &Stack{
  103.         MaxTop: 20,
  104.         Top:    -1,
  105.     }
  107.     // 表达式
  108.     exp := "33+2*6/1-2" // 字符串本身也是切片
  110.     // 定义需要的变量
  111.     num1 := 0
  112.     num2 := 0
  113.     oper := 0
  114.     keepNum := "" // 字符串 用于拼接多位数
  116.     // 定义索引，扫描表达式
  117.     index := 0
  118.     for {
  119.         ch := exp[index : index+1] // 每次拿到一个字符， 如果数字大于1位就会出问题, 在非符号字符入栈时处理
  120.         temp := int([]byte(ch)[0]) // 字符对应的 ASCII 码
  122.         if operStack.IsOper(temp) {
  123.             // 符号
  124.             if operStack.Top == -1 {
  125.                 // 1. 符号栈为空
  126.                 operStack.Push(temp)
  127.             } else {
  128.                 // 2. 符号栈不为空
  129.                 // 2.1 栈中的符号优先级大于等于即将入栈的符号
  130.                 if operStack.Priority(operStack.arr[operStack.Top]) >= operStack.Priority(temp) {
  131.                     num1, _ = numStack.Pop()
  132.                     num2, _ = numStack.Pop()
  133.                     oper, _ = operStack.Pop()
  134.                     result := operStack.Cal(num1, num2, oper)
  135.                     numStack.Push(result)
  136.                     operStack.Push(temp)
  137.                 } else {
  138.                     // 2.2 栈中的符号优先级小于即将入栈的符号
  139.                     operStack.Push(temp)
  140.                 }
  141.             }
  142.         } else {
  143.             // 数字
  145.             // 多位数拼接
  146.             keepNum += ch
  147.             // 判断扫描的下一位是不是运算符， 边界问题（表达式最后， 预防溢出）
  148.             if index == len(exp)-1 {
  149.                 // 字符 转数字
  150.                 val, _ := strconv.Atoi(keepNum) // Atoi是ParseInt(s, 10, 0)的简写。 返回的就是 int 类型
  151.                 numStack.Push(val)
  152.             } else {
  153.                 // 向后看一位
  154.                 if operStack.IsOper(int([]byte(exp[index+1 : index+2])[0])) {
  155.                     val, _ := strconv.Atoi(keepNum) // Atoi是ParseInt(s, 10, 0)的简写。 返回的就是 int 类型
  156.                     numStack.Push(val)
  157.                     keepNum = ""
  158.                 }
  159.                 // 其它情况不做处理，index++, 判断下一个字符
  160.             }
  162.             /*
  163.                 // 字符 转数字
  164.                 // val, _ := strconv.ParseInt(ch, 10, 0) // 返回 int64, 需要转 int(val)
  165.                 val, _ := strconv.Atoi(ch) // Atoi是ParseInt(s, 10, 0)的简写。 返回的就是 int 类型
  166.                 numStack.Push(val)
  167.             */
  168.         }
  170.         // 判断扫描位置
  171.         if index+1 == len(exp) {
  172.             fmt.Println("扫描到最后了")
  173.             break
  174.         }
  175.         index++
  176.     }
  178.     // 扫描完毕，之后对数栈和符号栈剩余元素处理
  179.     for {
  180.         if operStack.Top == -1 {
  181.             fmt.Println("没有运算符了， 数栈中的值就是计算结果")
  182.             break
  183.         }
  184.         num1, _ = numStack.Pop()
  185.         num2, _ = numStack.Pop()
  186.         oper, _ = operStack.Pop()
  187.         result := operStack.Cal(num1, num2, oper)
  188.         numStack.Push(result)
  189.     }
  191.     // 如果计算正确，数栈中只剩下一个元素，就是计算结果
  192.     res, _ := numStack.Pop()
  193.     fmt.Printf("表达式： %s = %v \n", exp, res)
  194. }