算法第三十三天-笨阶乘

笨阶乘

题目要求

解题思路

我们已经知道了求解没有括号的表达式的时候，运算符是优先级的：先乘除，后加减
对于表达式求值，大家已经很熟悉了，需要用到[栈]这个数据结构。求没有括号的中缀表达式的时候，可以用一句顺口溜来概括：遇到乘除立即算，遇到加减先入栈。

Python 躲坑

当使用python进行答题的时候，需要注意下面的这个坑。Python语言中的整数除法是向下取整的，而不是向零取整，对于负数的除法会有问题。

• 解决方法一：
  对Python的整数除法问题，可以使用int(num1/float(num2))来做，即先用浮点数除法，然后取整。
• 解决方法二：
  使用库函数operator.truediv(num1,num2)，调用该函数等价于num1/float(num2)

代码

class Solution:
    def clumsy(self, N: int) -> int:
        stack=[N]
        op=0
        for i in range(N-1,0,-1):
            if op==0:
                stack.append(stack.pop()*i)
            elif op==1:
                stack.append(int(stack.pop()/float(i)))
            elif op==2:
                stack.append(i)
            elif op==3:
                stack.append(-i)
            op = (op+1) % 4
        return sum(stack)

复杂度分析

时间复杂度：$O(N)$
空间复杂度：$O(N)$