LeetCode 基本计算器题解

LeetCode 基本计算器题解题目描述实现一个基本的计算器来计算一个简单的字符串表达式s的值。示例输入s 1 1输出2输入s (1(452)-3)(68)输出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(452)-3)(68))) # 输出23 if __name__ __main__: test_calculate()测试用例测试用例 1基本情况输入s 1 1输出2测试用例 2带括号输入s (1(452)-3)(68)输出23总结基本计算器是一个经典的栈问题它可以通过栈来高效地解决。栈的核心思想是使用栈来保存括号前的结果和符号当遇到右括号时弹出栈中的元素进行计算。掌握栈的使用方法对于解决类似的问题非常重要。