当前位置：首页 > news >正文

力扣227题基本计算器II（Python实现）

news 来源：原创 2024/9/20 16:52:50

在这里插入图片描述

思路

在这里插入图片描述

class Solution:def calculate(self, s):stack = []pre_op = '+'num = 0for i, each in enumerate(s):if each.isdigit():num = 10 * num + int(each)if i == len(s) - 1 or each in '+-*/':if pre_op == '+':stack.append(num)elif pre_op == '-':stack.append(-num)elif pre_op == '*':stack.append(stack.pop() * num)elif pre_op == '/':top = stack.pop()if top < 0:stack.append(int(top / num))else:stack.append(top // num)pre_op = eachnum = 0return sum(stack)作者：负雪明烛
链接：https://leetcode.cn/problems/basic-calculator-ii/solutions/648941/xian-cheng-chu-zai-jia-jian-yong-zhan-ba-hplr/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

这段代码定义了一个名为 Solution 的类，并实现了一个方法 calculate，用于计算给定数学表达式的值。以下是具体解释：

类与方法定义：
- class Solution:：定义一个名为 Solution 的类。
- def calculate(self, s):：定义一个方法 calculate，接收一个字符串 s，表示数学表达式。
初始化：
- stack = []：创建一个空列表 stack，用于存储计算结果。
- pre_op = '+'：初始化一个变量 pre_op，用于记录上一个操作符，默认为加号。
- num = 0：用于存储当前正在处理的数字。
遍历字符串：
- for i, each in enumerate(s):：遍历字符串 s 的每个字符。
- if each.isdigit():：检查当前字符是否为数字。
  - num = 10 * num + int(each)：构建当前数字（考虑多位数情况）。
操作符处理：
- if i == len(s) - 1 or each in '+-*/':：判断是否到达字符串末尾或当前字符是一个操作符。
  - 根据 pre_op 的值决定如何处理 num：
    - 如果是加号 +，将 num 添加到 stack。
    - 如果是减号 -，将 -num 添加到 stack。
    - 如果是乘号 *，将栈顶元素与 num 相乘，再存回栈中。
    - 如果是除号 /，则处理除法（考虑整数除法的情况，负数处理特别）。
  - 更新 pre_op 为当前操作符，重置 num 为 0。
返回结果：
- return sum(stack)：计算栈中所有元素的和并返回，得到最终结果。

总结：这段代码通过栈实现了对基本四则运算的支持，能够处理带有不同操作符的数学表达式，并正确计算结果。

下面以 3-5/2为例解释具体执行流程
让我们详细分析如何通过 calculate 方法计算表达式 "3-5/2" 的执行流程。

输入

s = "3-5/2"

执行流程

初始化
- stack = []: 初始化堆栈为空。
- pre_op = '+': 上一个操作符设为加号。
- num = 0: 当前数字初始化为0。
遍历字符串
- 对每个字符进行遍历。

第一次循环 (`i = 0`, `each = '3'`)

'3' 是数字：
- num = 10 * 0 + 3 → num = 3

第二次循环 (`i = 1`, `each = '-'`)

i 不是字符串的最后一个字符且 '-' 是操作符：
- 因为 pre_op == '+'：
  - stack.append(3) → stack = [3]
- 更新 pre_op = '-'
- 重置 num = 0

第三次循环 (`i = 2`, `each = '5'`)

'5' 是数字：
- num = 10 * 0 + 5 → num = 5

第四次循环 (`i = 3`, `each = '/'`)

i 不是字符串的最后一个字符且 '/' 是操作符：
- 因为 pre_op == '-'：
  - stack.append(-5) → stack = [3, -5]
- 更新 pre_op = '/'
- 重置 num = 0

第五次循环 (`i = 4`, `each = '2'`)

'2' 是数字：
- num = 10 * 0 + 2 → num = 2

第六次循环 (`i = 5`, `each` 是结束位置)

由于到达字符串末尾：
- 当前 pre_op 为 '/'：
  - 执行除法，将栈顶元素与 num 相除：
  - top = stack.pop() → top = -5（从栈中移除 -5）
  - 因为 top < 0：
    - stack.append(int(top / num)) → stack.append(int(-5 / 2)) → stack.append(-2) （结果为 -2.5，取整为 -2）
    - stack 现在为 [3, -2]