欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

编写一个基本计算器

程序员文章站 2022-04-16 16:00:40
题目实现一个基本的计算器来计算一个简单的字符串表达式的值。字符串表达式可以包含左括号 ( ,右括号 ),加号 + ,减号 -,非负整数和空格 。示例 1:输入: "1 + 1"输出: 2示例 2:输入: " 2-1 + 2 "输出: 3示例 3:输入: "(1+(4+5+2)-3)+(6+8)"输出: 23说明:你可以假设所给定的表达式都是有效的。请不要使用内置的库函数 eval解题思路自己的思路是:先分割字符串,然后对于没有括号的部分,计算出来。碰到括号后,对括号...

题目

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

字符串表达式可以包含左括号 ( ,右括号 ),加号 + ,减号 -,非负整数和空格 。

示例 1:

输入: "1 + 1"
输出: 2

示例 2:

输入: " 2-1 + 2 "
输出: 3

示例 3:

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

说明:

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

解题思路

自己的思路是:先分割字符串,然后对于没有括号的部分,计算出来。碰到括号后,对括号内的部分,计算出来。然后再一起计算。这样的话,如果碰到较长的表达式,会出现爆栈的问题。

看了题解的思路,题解的思路太妙了……把每个+-都作为数字的自带符号,然后全部相加。
如果碰到左括号,则把前面计算出来的结果、这个左括号前面的符号入栈,然后从头开始计算括号内的结果
如果碰到右括号,则把当前的结果和栈里的结果合并。合并的时候注意,1 - (4),应该是括号内的结果,和括号前的符号(这里的-)相乘,然后再和1相加。(用到了加法的交换律,-4 + 1 = 1 + (-4)

代码

官方题解版:

class Solution:
    def calculate(self, s: str) -> int:
        res, op = 0, 0
        sign = 1
        stack = []
        for ch in s:
            if ch.isdecimal():
                op = op * 10 + int(ch)
            elif ch == '+':
                res += sign * op
                sign = 1
                op = 0
            elif ch == '-':
                res += sign * op
                sign = -1
                op = 0
            elif ch == '(':
                stack += [res, sign]
                res, op = 0, 0
                sign = 1
            elif ch == ')':
                res += sign * op
                res *= stack.pop()
                res += stack.pop()
                op = 0
                sign = 1
        res += sign * op
        return res

本文地址:https://blog.csdn.net/sinat_41679123/article/details/107450439

相关标签: OJ题目记录