LeetCode 基本计算器题解

LeetCode 基本计算器题解

题目描述

实现一个基本的计算器来计算一个简单的字符串表达式s的值。

示例：

输入：s = "1 + 1"
输出：2

输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

解题思路

方法：栈

思路：

• 使用栈来解决这个问题。
• 遍历字符串，对于每个字符：
  • 如果是数字，累积计算当前数字。
  • 如果是运算符（+、-），将当前数字和运算符压入栈，然后重置当前数字。
  • 如果是左括号，将当前结果和运算符压入栈，然后重置当前结果和运算符。
  • 如果是右括号，弹出栈顶的运算符和结果，进行计算。
• 最后将栈中的所有元素相加。

复杂度分析：

• 时间复杂度：O(n)，其中 n 是字符串的长度。每个字符最多被访问一次。
• 空间复杂度：O(n)，最坏情况下需要存储所有的元素。

代码实现

方法：栈

# 基本计算器（栈） def calculate(s): stack = [] result = 0 num = 0 sign = 1 # 1 表示正数，-1 表示负数 for char in s: if char.isdigit(): num = num * 10 + int(char) elif char == '+': result += sign * num num = 0 sign = 1 elif char == '-': result += sign * num num = 0 sign = -1 elif char == '(': # 将当前结果和符号压入栈 stack.append(result) stack.append(sign) # 重置结果和符号 result = 0 sign = 1 elif char == ')': # 先计算当前括号内的结果 result += sign * num num = 0 # 弹出符号和之前的结果 sign = stack.pop() prev_result = stack.pop() result = prev_result + sign * result # 加上最后一个数字 result += sign * num return result # 测试 def test_calculate(): print(calculate("1 + 1")) # 输出：2 print(calculate("(1+(4+5+2)-3)+(6+8)")) # 输出：23 if __name__ == "__main__": test_calculate()

测试用例

测试用例 1：基本情况

输入：s = "1 + 1"
输出：2

测试用例 2：带括号

输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

总结

基本计算器是一个经典的栈问题，它可以通过栈来高效地解决。

栈的核心思想是：使用栈来保存括号前的结果和符号，当遇到右括号时，弹出栈中的元素进行计算。

掌握栈的使用方法，对于解决类似的问题非常重要。