题目难度: 中等

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

给定一个包含正整数、加(+)、减(-)、乘(*)、除(/)的算数表达式(括号除外)，计算其结果。

表达式仅包含非负整数，+， - ，*，/ 四种运算符和空格 。 整数除法仅保留整数部分。

示例 1:

  • 输入: "3+2*2"
  • 输出: 7

示例 2:

  • 输入: " 3/2 "
  • 输出: 1

示例 3:

  • 输入: " 3+5 / 2 "
  • 输出: 5

说明：

  • 你可以假设所给定的表达式都是有效的。
  • 请不要使用内置的库函数 eval。

题目思考

  1. 需要使用哪些数据结构?
  2. 什么时候进行运算?

解决方案

思路

  • 分析题目, 总共有 4 种运算, 且存在不同的优先级, 所以我们不能遇到一个运算符就直接将其左右两边的数字进行运算, 这样有可能破坏优先级关系
  • 例如 1+2*3, 我们不能先计算 1+2, 那样结果就完全错了
  • 而对于 1-2+3 或 1*2+3, 则是从左到右计算
  • 总结来说, 对于前后两个字符 op1 和 op2, 有以下两种情况:
    1. op1 优先级大于等于 op2 (例如*和+, -和+), 则正常从左向右计算;
    2. op1 优先级小于 op2 (例如+和*, -和/), 则需要从右向左计算
  • 所以这里我们可以用栈来实现不同顺序的计算: 首先定义好每个运算符的优先级, 然后初始化数字栈和运算符栈, 分别用于保存遍历的数字和运算符
  • 遍历过程分为两种情况:
    1. 如果栈顶运算符的优先级大于等于当前运算符, 则优先使用栈顶运算符来计算栈顶的两个数字, 模拟从左到右计算;
    2. 否则就先将当前运算符压入栈中, 等待后续处理
  • 当遍历结束后, 假如运算符栈中仍有元素, 则其从栈顶到栈底一定是优先级单调递减的情况, 否则会在上面的情况 1 中直接计算
  • 此时我们就从栈顶开始, 依次计算栈顶两个数字, 直到运算符栈为空为止, 这就模拟了从右向左计算的过程
  • 最后, 数字栈中一定只留下一个数字, 即为最终结果
  • 下面的代码对必要步骤有详细的解释, 方便大家理解

复杂度

  • 时间复杂度 O(N): 遍历字符需要 O(N), 计算数字也需要 O(N)
  • 空间复杂度 O(N): 使用两个栈分别存储数字和运算符

代码

class Solution:
    def calculate(self, s: str) -> int:
        i = 0
        numStack = []
        opStack = []
        pri = {
            "*": 1,
            "/": 1,
            "+": 2,
            "-": 2,
        }

        def calTwo():
            # 使用opStack栈顶运算符以及numStack栈顶两元素作为运算数, 进行计算
            if len(numStack) < 2 or len(opStack) < 1:
                # 元素数目不够, 无效
                return
            # 弹出numStack栈的两个数字, 以及opStack栈的一个运算符
            # 注意栈顶是第二个操作数
            b, a = numStack.pop(), numStack.pop()
            op = opStack.pop()
            # 根据运算符的不同来计算结果, 并将结果压入栈中
            if op == "+":
                numStack.append(a + b)
            elif op == "-":
                numStack.append(a - b)
            elif op == "*":
                numStack.append(a * b)
            elif op == "/":
                numStack.append(int(a / b))

        while i < len(s):
            if "0" <= s[i] <= "9":
                # 当前是数字开头, 直接遍历得到整个数字, 并加入数字栈
                j = i
                num = 0
                while j < len(s) and "0" <= s[j] <= "9":
                    num = 10 * num + int(s[j])
                    j += 1
                numStack.append(num)
                i = j - 1
            elif s[i] != " ":
                # 当前是运算符
                while opStack and pri[opStack[-1]] <= pri[s[i]]:
                    # 注意如果栈顶运算符优先级等于或高于当前运算符, 则优先计算栈顶的两个数字
                    # 例如1*2/3, 遍历到/时先计算1*2, 同理1*2+3也是如此
                    # 而对于1+2*3, 遍历到*时由于+的优先级低, 所以不先计算1+2
                    calTwo()
                opStack.append(s[i])
            i += 1
        # 如果opStack仍有元素, 则其从栈顶到栈底一定是优先级单调递减的情况(否则会在上面直接计算)
        # 对应于上面例子的1+2*3的情况, 先计算2*3得到6, 然后将6压入栈中再计算1+6
        while opStack:
            calTwo()
        return numStack[-1]

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊

算法精选 - 微信扫一扫关注我