WechatIMG579.jpeg

题目描述

leetcode 第224题：基本计算器
实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。
示例：
输入：s = " (1+(4+5+2)-3)+(6+8) "
输出：23

解题方法

栈
参照题解

• 解题思路

由于字符串表达式s中存在空格，需要先去除空格，这时s中仅存在数字、加减号、括号
将s整体转换为加法运算，减去一个数可以理解为加上这个数的负数，1-1看作1+(-1)
然后定义变量sign来标示每个数前面的正负符号{-1,+1}
对于s，第一个数前面的符号一定为正，1-1看作0+1-1，所以sign默认为1并压栈
定义变量sumS，存储s计算后的值，初始为0
获取s的长度n，在[0,n)的范围内循环得到当前字符s[i]
如果s[i]为+号，则更新sign为栈顶元素
如果s[i]为-号，则更新sign为栈顶元素的负数
如果s[i]为（号，将当前的sign压栈
如果s[i]为）号，弹出栈顶元素
如果s[i]为数字，sumS累加当前数字的数值sign*num
最后s计算后的值就是sumS

• 复杂度

时间复杂度：O(n)，n为字符串s的长度
空间复杂度：O(n)，n为字符串s的长度

• 代码实现

python3

class Solution:
    def calculate(self, s: str) -> int:
        s = s.replace(" ","")
        n = len(s)
        sign = 1
        stack = [sign]
        i = sumS = 0
        while i<n:
            if s[i]=="(":
                stack.append(sign)
                i+=1
            elif s[i]==")":
                stack.pop()
                i+=1
            elif s[i]=="+":
                sign = stack[-1]
                i+=1
            elif s[i]=="-":
                sign = -stack[-1]
                i+=1
            else:
                num = 0
                while i<n and s[i].isdigit():
                    num = num*10+int(s[i])
                    i += 1
                sumS += sign*num
        return sumS

php

class Solution {
    function calculate($s) {
        $s = str_replace(" ","",$s);
        $n = strlen($s);
        $sign = 1;
        $stack = [$sign];
        $i = $sumS = 0;
        while($i<$n){
            if($s[$i]=="+"){
                $sign = end($stack);
                $i++;
            }elseif($s[$i]=="-"){
                $sign = -end($stack);
                $i++;
            }elseif($s[$i]=="("){
                array_push($stack,$sign);
                $i++;
            }elseif($s[$i]==")"){
                array_pop($stack);
                $i++;
            }else{
                $num = 0;
                while($i<$n && is_numeric($s[$i])){
                    $num = $num*10+$s[$i];
                    $i++;
                }
                $sumS += $sign*$num;
            }
        }
        return $sumS;
    }
}