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
总结
基本计算器是一个经典的栈问题，它可以通过栈来高效地解决。
栈的核心思想是：使用栈来保存括号前的结果和符号，当遇到右括号时，弹出栈中的元素进行计算。
掌握栈的使用方法，对于解决类似的问题非常重要。
