逆波兰表达式求值 python vs golang

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

题面

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

["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]
}

性能

提交时间 提交结果 运行时间 内存消耗 语言
几秒前 通过 4 ms 4.1 MB Go
几秒前 通过 44 ms 13.7 MB Python3
本作品采用《CC 协议》,转载必须注明作者和本文链接
pardon110
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
开发者 @ 社科大
文章
133
粉丝
24
喜欢
100
收藏
54
排名:107
访问:8.9 万
私信
所有博文
社区赞助商