Leetcode 224:基本计算器(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 224:基本计算器(超详细的解法!!!)

in leetcode with 0 comment

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

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

示例 1:

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

示例 2:

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

示例 3:

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

说明:

解题思路

经典问题,首先采用递归的方式求解。这里使用了trick,使用1表示加法,使用-1表示减法,使用l表示左值,使用r表示右值。

class Solution:
    def calculate(self, s: str) -> int:
        u, s_len = 0, len(s)
        def dfs():
            nonlocal u
            l, r, op = 0, 0, 1
            while u < s_len:
                if s[u] == ' ':
                    u += 1
                    continue
                elif s[u] in '+-':
                    l += op * r
                    r, op = 0, 1 if s[u] == '+' else -1
                    u += 1
                elif s[u] == '(':
                    u += 1
                    l += op * dfs()
                elif s[u] == ')':
                    u += 1
                    return l + op * r
                else:
                    r = r * 10 + int(s[u])
                    u += 1
            return l + op * r
        return dfs()

同样也可以使用递归解决,递归我们也使用了trick,只使用一个栈就解决了。算法思路和上面的方法类似,只是当访问的元素是'('的时候,将lop添加到栈中,同时更新op=1l=0。当访问的元素是')'的时候,将栈中的lop弹出,并且更新l

class Solution:
    def calculate(self, s):
        st, op, r, l = [], 1, 0, 0
        for c in s:
            if c.isdigit():
                r = r * 10 + int(c)
            elif c in "+-":
                l += op * r
                r, op = 0, 1 if c == '+' else -1
            elif c == "(":
                st.append(l)
                st.append(op)
                op, l = 1, 0
            elif c == ")":
                l += op * r
                r = 0
                l = st.pop() * l + st.pop()
        return l + op * r

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses