逆波兰表达式求值 python vs golang

pardon110 的个人博客 / 0 / 0 / 创建于 4年前 / 更新于 4年前

栈在一些匹配性场景存在巨大优势，对计算机十分友好

题面#

计算逆波兰式（后缀表达式）的值，整数除法只保留整数部分
运算符仅包含 "+","-","*" 和 "/"，被操作数可能是整数或其他表达式

["20", "10", "+", "30", "*"] -> ((20 + 10) * 30) -> 900
["40", "130", "50", "/", "+"] -> (40 + (130 / 50)) -> 42

分析#

遇到操作数入栈
碰到操作符取栈顶两操作数，计算结果入栈
注意出栈顺序，先进后出，尤其在计算除法与减法时

python 解法#

不失短小精悍

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        st = []
        for v in tokens:
            if v in "+-*/":
                b, a = st.pop(),st.pop()
                if v == "+": st.append(a + b)
                if v == "-": st.append(a - b)
                if v == "*": st.append(a * b)
                if v == "/": st.append(int(a / b))
            else:
                st.append(int(v))
        return st[-1]

或如此用丧心病狂的 eval

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        st = []
        for v in tokens:
            if v in "+-*/":
                b,a = st.pop(),st.pop()
                st.append(eval("%d%s%d"%(a,v,b)))
            else:
                st.append(int(v))
        return int(st[-1])

golang 实现#

rune 类型隐式转换字符串

import "strconv"
func evalRPN(tokens []string) int {
    st := []int{}
    for _,v := range tokens {
        if v == "+" || v == "-" || v == "*" || v == "/" {
            if len(st)< 2 {
                return 0
            }
            b := st[len(st)-1]
            st = st[:len(st)-1]
            a := st[len(st)-1]
            st = st[:len(st)-1]
            switch v {
                case "+": st = append(st, a+b)
                case "-": st = append(st, a-b)
                case "*": st = append(st, a*b)
                case "/": st = append(st, a/b)
            }
        }else{
            if num,err := strconv.Atoi(v); err == nil {
                st = append(st, num)
            }
        }
    }
    return st[len(st)-1]
}