美文网首页栈专题
Leetcode 基本计算器 II

Leetcode 基本计算器 II

作者: Yohann丶blog | 来源:发表于2021-03-11 15:01 被阅读0次
    WechatIMG581.jpeg

    题目描述

    leetcode 第227题:基本计算器 II
    给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。
    整数除法仅保留整数部分。
    示例:
    输入:s = " 3+5 / 2 "
    输出:5

    解题方法


    参照题解

    • 解题思路

    由于字符串表达式s中存在空格,需要先去除空格,这时s中仅存在数字、加减乘除号
    然后定义变量sign来标示每个数前面的运算符
    对于s,第一个数前面的符号一定为,3+5看作0+3+5,所以sign默认为+
    先计算乘除后整体转换为加法运算,创建栈stack存储每次需要相加的数值
    获取s的长度n,在[0,n)的范围内循环得到当前字符s[i]
    如果s[i]为数字,计算当前数字的数值num
    如果s[i]为运算符或者下标i等于n-1(保证末尾数字参与运算)时
    分别考虑以下情况:
    s[i]+号,num压栈
    s[i]-号,负的num压栈
    s[i]*号,计算num与栈顶元素相乘的结果后压栈
    s[i]/号,计算num与栈顶元素相除的结果后压栈
    每次压栈后,更新sign为当前的运算符并将num清零
    最后将栈stack中元素求和,即为s计算后的值

    • 复杂度

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

    python3

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

    php

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

    相关文章

      网友评论

        本文标题:Leetcode 基本计算器 II

        本文链接:https://www.haomeiwen.com/subject/gjznqltx.html