逆波兰表达式

  1. // 中缀转后缀
  2. func pre2Post() *[]string {
  3.     slice := strings.Split("")
  4.     stack := Stack.NewStack(20)
  5.     var slice2 []string
  6.     for _, val := range slice {
  7.         if isOperation(val) {
  8.             if (val != ")") {
  9.                 now := stack.GetValue()
  10.                 if now == "+" || now == "-" {
  11.                     stack.Push(val)
  12.                 } else {
  13.                     var popEle string
  14.                     stack.Pop(&popEle)
  15.                     slice2 = append(slice2, popEle)
  16.                 }
  18.             } else {
  19.                 for ele := stack.Pop(&ele); ele != "(" {
  20.                     slice2 = append(slice2, ele)
  21.                 }
  22.             }
  23.         } else {
  24.             slice2 = append(slice2, val)
  25.         }
  26.     }
  27. }
  28. // 后缀表达式
  29. func postFun() {
  30.     nums := []string{"9", "3", "1", "-", "3", "*", "+", "10", "2", "/", "+"}
  31.     stack := Stack.NewStack(20)
  33.     for _, val := range nums {
  34.         if isOperation(val) {
  35.             var prev, next int
  36.             stack.Pop(&next)
  37.             stack.Pop(&prev)
  38.             result := operation(prev, next, val)
  39.             stack.Push(result)
  40.         } else {
  41.             num, _ := strconv.Atoi(val)
  42.             stack.Push(num)
  43.         }
  44.     }
  45.     fmt.Println(stack.GetValue())
  46. }
  47. // 辅助方法
  48. func operation(a, b int, opt string) int {
  49.     switch opt {
  50.     case "-":
  51.         return a - b
  52.     case "+":
  53.         return a + b
  54.     case "*":
  55.         return a * b
  56.     case "/":
  57.         return a / b
  58.     default:
  59.         panic("wrong operation")
  61.     }
  62. }
  64. func isOperation(str string) bool {
  65.     slice := []string{"+", "-", "*", "/"}
  66.     for _, val := range slice {
  67.         if val == str {
  68.             return true
  69.         }
  70.     }
  71.     return false
  72. }

没有泛型是真的不方便

中缀表达式 (栈用来进出运算的符号)

  • 定义当前元素 ele
  • 数字类型直接输出
  • 遇到 ( 进栈 遇到 ) 开始出栈输出,直到 ( 出栈为止
  • 如果当前栈顶元素 比 ele 优先级低 (“* /“ < “+ -“),入栈
  • 如果当前栈顶元素 比 ele 优先级高 (如果栈顶), 则出栈所有栈中元素,直到栈空, 然后将当前元素入栈
  • 如果当前栈顶元素 和 ele 优先级相等, 输出当前元素
  • 当前元素为 nil 后，出栈输出到队尾

后缀表达式 (栈用来进出运算的数字)

  • 定义当前元素 ele
  • 如果 ele 是数字类型入栈
  • 如果 ele 是运算符类型 出栈两个元素(一定是数字类型), 第一个出栈的元素为b, 第二个出栈的元素为a, (a opt b)将得到结果入栈