逆波兰式

逆波兰式（Reverse Polish notation, RPN），又称后缀表达式。
要想了解逆波兰式的特点及作用，那要从我们最常见的中缀表达式说起。

中缀表达式

定义：通用的算术或逻辑公式表示方法。
特点：操作符在操作数之间。
例子：1 - (2 + 3)
没错，中缀表达式就是我们人类常常书写一个算术表达式的形式，但是这种写法适合人进行运算却不适合计算机运算。因此科学家们设计了前缀表达式和后缀表达式，两者都可以很方便地让计算机实现一些基础运算。

前缀表达式

特点：操作符在操作数之前。
例子：1 - (2 + 3) 的前缀表达式为 - 1 + 2 3
当计算机处理时，利用栈，从后往前扫描，遇到操作数就入栈，遇到操作符就弹出两个操作数进行运算，并将运算结果重新入栈，最终计算结果在栈顶（此时栈只有 1 个元素，就是计算结果）。

遇到 3 入栈，遇到 2 入栈；
遇到 + 弹出 2 和 3，计算 2 + 3 = 5，将 5 入栈；
遇到 1 入栈；
遇到 - 弹出 1 和 5，计算 1 - 5 = -4，将 -4 入栈，扫描完毕，-4 就是计算结果。

后缀表达式

特点：操作符在操作数之后。
例子：1 - (2 + 3) 的前缀表达式为 1 2 3 + -
当计算机处理时，利用栈，从前往后扫描，遇到操作数就入栈，遇到操作符就弹出两个操作数进行运算，并将运算结果重新入栈，最终计算结果在栈顶（此时栈只有 1 个元素，就是计算结果）。

遇到 1, 2, 3 分别入栈；
遇到 + 弹出 3 和 2，计算 2 + 3 = 5，将 5 入栈；
遇到 - 弹出 5 和 1，计算 1 - 5 = -4，将 -4 入栈，扫描完毕， -4 就是计算结果。

为什么选择逆波兰式

既然前缀表达式和后缀表达式都可以实现简单的四则运算，为什么多采用后缀表达式呢？
我个人觉得是因为在利用后缀表达式计算时，是从前往后扫描，比较符合大多数人的逻辑。
但是这里要注意：采用后缀表达式求值时，遇到操作符 ops 时，要先后弹出两个操作数 x 和 y，但其实正确的运算顺序是 y ops x，即先弹出的 x 是第二个操作数，后弹出的 y 是第一个操作数。
而前缀表达式却正好相反，先弹出的就是第一个操组作数，自己看上面两个例子就可以发现了。

构建逆波兰式

假设中缀表达式只含有 +, -, *, /, % 操作符和括号 ()，操作数都是 0-9 的整数，并且保证表达式有效。
假设中缀表达式以字符串的形式给出，如 s = “1-(2+3)”
根据中缀表达式构建后缀表达式的过程如下：

借助一个字符串数组和一个栈：操作数数组 RPN 和操作符栈 st。
从左往右扫描 s：
1. 若遇到操作数则加入 RPN 末尾；
2. 若遇到左括号则直接压入 st；
3. 若遇到右括号，则依次把栈顶放入 RPN 数组末尾，直至遇到左括号停止。
4. 遇到操作符 ops 若栈空则直接压入；否则先与 st 的栈顶 st.peek() 的操作符比较优先级，若，则直接将 ops 压入 st；否则循环将 st.peek() 放入 RPN 数组末尾，再把 ops 压入 st。
5. 重复以上操作直至扫描完毕，把栈中剩余元素倒入 RPN 数组。

一个图示过程如下：

代码实现如下：

func priority(x byte) int {
    if x == '(' || x == ')' {
        return 0
    } else if x == '+' || x == '-' {
        return 1
    } else if x == '*' || x == '/' || x == '%' {
        return 2
    } else {
        return -1
    }
}
// @s 中缀表达式
func buildRPN(s string) []byte {
    RPN := make([]byte, 0, len(s))
    stack := make([]byte, 0, len(s) / 2)
    for i := range s {
        // 操作数
        if priority(s[i]) == -1 {
            RPN = append(RPN, s[i])
            continue
        }
        // 操作符
        for {
            // 栈空 或 左括号 或 优先级比栈顶高
            if len(stack) == 0 || s[i] == '(' ||
                (priority(s[i]) > priority(stack[len(stack)-1])) {
                stack = append(stack, s[i])
                break
            }
            // 右括号 或 优先级比栈顶低
            tmp := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            if tmp == '(' {
                break
            } else {
                RPN = append(RPN, tmp)
            }
        }
    }
    // stack 剩余元素倒入 RPN
    for len(stack) > 0 {
        RPN = append(RPN, stack[len(stack)-1])
        stack = stack[:len(stack)-1]
    }
    return RPN
}

计算逆波兰表达式

计算过程如下：

借助一个栈 stack
从左往右扫描 RPN 数组，若遇到的是操作数则直接入栈。
若遇到的是操作符，则依次出栈两个操作数进行相应计算，把计算结果入栈。

一个图示过程如下：

代码实现如下：

func eval(RPN []byte) int {
    stack := make([]int, 0, len(RPN))

    for i := range RPN {
        if RPN[i] >= '0' && RPN[i] <= '9' {            
            stack = append(stack, int(RPN[i]-'0'))
        } else {
            size := len(stack)
            operand1, operand2 := stack[size-2], stack[size-1]
            stack = stack[:size-2]
            ans := 0
            if RPN[i] == '+' {
                ans = operand1 + operand2
            } else if RPN[i] == '-' {
                ans = operand1 - operand2
            } else if RPN[i] == '*' {
                ans = operand1 * operand2
            } else if RPN[i] == '/' {
                ans = operand1 / operand2
            } else if RPN[i] == '%' {
                ans = operand1 % operand2
            }
            stack = append(stack, ans)
        }
    }

    return stack[0]
}

上述代码实现的很简单，而且输入限制的很死，如果放宽条件限制，要处理的细节会变的非常多，比如：

输入是什么？如果是 string 字符串，那么需要根据输入分割操作数和操作符，分成一个 []string 则方便进行 RPN 的构建？
如果 RPN 采用了 []string 类型，那么计算时如何快速把 “123” 转成数字 123 进行运算呢？如何快速判断 RPN[i] 是操作数还是操作符呢？
除法操作若不能除整，处理规则是什么呢？除数为 0 怎么处理呢？
计算过程中或结果是否会溢出呢？
……

下面给出一个另外一个简陋的代码，它放宽了对表达式的限制：

表达式可以包含空格；
表达式中整数的位数可以超过 1 位；

但是仍然有其他要求：

计算过程中，中间结果和最终结果都不能超过 int32 的存储范围。 ```go func buildRPN(s string) []string { RPN := make([]string, 0) stack := list.New() var builder strings.Builder

for i := 0; i < len(s); i++ {

  // 空格
  if s[i] == ' ' {
      continue
  } 
  // 操作数
  if s[i] >= '0' && s[i] <= '9' {
      for ; i < len(s) && s[i] >= '0' && s[i] <= '9'; i++ {
          builder.WriteByte(s[i])    
      }
      i--
      RPN = append(RPN, builder.String())
      builder.Reset()
      continue
  }
  // 操作符 或 括号
  for {
      // 栈空 或 左括号 或 优先级比栈顶高
      if stack.Len() == 0 || s[i] == '(' || (priority(s[i]) > priority(stack.Back().Value.(byte))) {
          stack.PushBack(s[i])
          break
      }
      // 右括号 或 优先级比栈顶低
      tmp := stack.Back()
      stack.Remove(tmp)
      if tmp.Value.(byte) == '(' {
          break
      } else {
          RPN = append(RPN, string(tmp.Value.(byte)))
      }
  }

}

// 栈剩余元素倒入 RPN for stack.Len() > 0 {

  e := stack.Back()
  RPN = append(RPN, string(e.Value.(byte)))
  stack.Remove(e)

}

return RPN }

func calcalateRPN(RPN []string) int { stack := list.New()

for i := 0; i < len(RPN); i++ {
    if RPN[i][0] >= '0' && RPN[i][0] <= '9' {    // 操作数
        number, _ := strconv.Atoi(RPN[i])
        stack.PushBack(number)
    } else {    // 操作符
        e1, e2 := stack.Back().Prev(), stack.Back()
        operand1, operand2 := e1.Value.(int), e2.Value.(int)
        stack.Remove(e1)
        stack.Remove(e2)
        tmp := 0
        if RPN[i] == "+" {
            tmp = operand1 + operand2
        } else if RPN[i] == "-" {
            tmp = operand1 - operand2
        } else if RPN[i] == "*" {
            tmp = operand1 * operand2
        } else if RPN[i] == "/" {
            tmp = operand1 / operand2
        } else if RPN[i] == "%" {
            tmp = operand1 % operand2
        }
        stack.PushBack(tmp)
    }
}

return stack.Back().Value.(int)

} ```