聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

LeetCode 224:基本计算器

2022-08-29 14:05 浏览: 2910031 次 我要评论(0 条) 字号:

来自公众号:吴师兄学算法

今天的题目来源于 LeetCode 第 224 号问题:基本计算器,难度为「困难」,根据评论区的反馈,在字节面试出现过。

一、题目描述

给你一个字符串表达式 s ,请你实现一个基本计算器来计算并返回它的值。

示例 1:

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

示例 2:

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

示例 3:

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

提示:

  • 1 <= s.length <= 3 * 105
  • s 由数字、'+''-''('')'、和 ' ' 组成
  • s 表示一个有效的表达式

二、题目解析

对于一个表达式来说,它包含三部分:

  • 1、左表达式
  • 2、运算符
  • 3、右表达式

左边和右边的表达式可以是一个数字,也可以是一个括号包起来的表达式;运算符可以是加减。

对于一个只包含加减和括号的表达式来说,是按照从左到右的顺序进行计算,但遇到括号就先算括号里面的

具体操作如下:

1、使用栈来储存字符串表达式中的数字,设置变量 res 保存计算的结果,一开始可以认为 res = 0,作为左表达式,同时当前的运算符为 + ,接下来去变量字符数组,先去寻找出右表达式出来。

2、获取字符串里面的每个字符

3、如果当前字符是数字的话,需要去查看当前字符的后一位是否存在,如果后一位依旧是数字,那么就需要把后面的数字累加上来,比如下图中的 12,查看到 1 时,继续查看后面的数字是 2 ,于是和 1 组成了 12,再向后看发现是字符,自此,这个数字 12 就形成了。

4、一旦确定了一个数字,需要把这个数字进行一个计算, res = res + sign * value

5、如果遇到的是运算符 + 或者 - ,那么为了方便计算,所有的操作都视为加法操作,即原先的减法操作就相当于是加一个负数。

6、如果遇到的是 ( ,根据数学计算规则,需要先计算括号里面的数字,而什么时候计算呢?遇到 ) 为止,所以,在遇到 ) 之前需要把之前计算好的结果存储起来再计算。

7、如果遇到的是 ),那么就需要把栈中存放的元素取出来了。

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 基本计算器( LeetCode 224 ):https://leetcode-cn.com/problems/basic-calculator
class Solution {
    public int calculate(String s) {

        // 使用栈来储存字符串表达式中的数字
        Stack<Integer> stack = new Stack<Integer>();

        // 为了方便计算,所有的操作都视为加法操作
        // 那么原先的减法操作就相当于是加一个负数
        // 默认都是正数
        int sign = 1;

        // 保存计算的结果
        int res = 0;

        // 获取字符串的长度,然后获取里面的每个字符
        int length = s.length();

        // 获取字符串里面的每个字符
        for (int i = 0; i < length; i++) {

            // 获取此时的字符
            char ch = s.charAt(i);

            // 如果当前字符是数字的话
            if (Character.isDigit(ch)) {

                // 那么可以通过 - '0' 这个操作把字符转换为整数
                // 相当于转换成了 ascii 码进行的数字运算
                int value = ch - '0';

                // 去查看当前字符的后一位是否存在
                // 如果操作并且后一位依旧是数字,那么就需要把后面的数字累加上来

                while (i + 1 < length && Character.isDigit(s.charAt(i + 1))){
                    
                    // i 向后移动,直到遇到非数字为止
                    i++;

                    // i 每向后移动一位,当前的值就需要乘以 10
                    // 比如 s 为 "123+456"
                    // 此时 i = 0,那么 value 为 1
                    // i = 1,那么 value 为 1 * 10 + 2 = 12
                    // i = 2,那么 value 为 12 * 10 + 3 = 123
                    value = value * 10 + s.charAt(i) - '0';

                }

                // 那么把获取到的数累加到结果 res 上
                res = res + sign * value;

              // 如果是 '+'
            } else if (ch == '+') {
                
                // 那么说明直接加一个正数
                sign = 1;

              // 如果是 '-'
            } else if (ch == '-') {

                // 那么说明加一个负数
                sign = -1;

              // 如果是 '('
            } else if (ch == '(') {
                // 根据数学计算规则,需要先计算括号里面的数字
                // 而什么时候计算呢?
                // 遇到 ) 为止
                // 所以,在遇到 ) 之前需要把之前计算好的结果存储起来再计算
                // ( ) 直接的计算规则和一开始是一样的

                // 1、先把 ( 之前的结果存放到栈中
                stack.push(res);

                // 2、重新初始化 res 为 0
                res = 0;
                // 3、把 ( 左边的操作符号存放到栈中
                // 比如如果是 5 - ( 2 + 3 ) ,那么就是把 -1 存放进去
                // 比如如果是 5 +( 2 + 3 ) ,那么就是把 1 存放进去
                stack.push(sign);

                // 4、为了方便计算,所有的操作都视为加法操作
                // 那么原先的减法操作就相当于是加一个负数
                // 默认都是正数
                sign = 1;

                // 如果是 ')'
            } else if (ch == ')') {
                
                // 那么就需要把栈中存放的元素取出来了
                // 在 ch == '(' 这个判断语句中,每次都会往栈中存放两个元素
                // 1、先存放左括号外面的结果
                // 2、再存放左括号外面的符号

                // 1、先获取栈顶元素,即左括号外面的符号,查看是 + 还是 -
                int formerSign = stack.peek();

                // 把栈顶元素弹出
                stack.pop();

                // 2、再获取栈顶元素,即左括号结果
                int formerRes = stack.peek();

                // 把栈顶元素弹出
                stack.pop();

                // 那结果就是括号外面的结果 + 括号里面的结果,至于是加正数还是负数,取决于左括号外面的符号
                res = formerRes +  formerSign * res ;

            }
        }

        // 返回计算好的结果
        return res;
    }
}

2、C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者:程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// 基本计算器( LeetCode 224 ):https://leetcode-cn.com/problems/basic-calculator
class Solution {
public:
    int calculate(string s) {
        // 使用栈来储存字符串表达式中的数字
        stack<int> st;

        // 为了方便计算,所有的操作都视为加法操作
        // 那么原先的减法操作就相当于是加一个负数
        // 默认都是正数
        int sign = 1;

        // 保存计算的结果
        int res = 0;

        // 获取字符串的长度,然后获取里面的每个字符
        int length = s.length();

        // 获取字符串里面的每个字符
        for(int i = 0;i < length;i++){

            // 获取此时的字符
            char ch = s[i];

            // 如果当前字符是数字的话
            if( ch >= '0' && ch <= '9' ) {
                // 那么可以通过 - '0' 这个操作把字符转换为整数
                // 相当于转换成了 ascii 码进行的数字运算
                long value = ch - '0';

                // 去查看当前字符的后一位是否存在
                // 如果操作并且后一位依旧是数字,那么就需要把后面的数字累加上来
                while (i + 1< length &&s[i+1]>='0'&&s[i+1]<='9'){
                    // i 向后移动,直到遇到非数字为止
                    i++;

                    // i 每向后移动一位,当前的值就需要乘以 10
                    // 比如 s 为 "123+456"
                    // 此时 i = 0,那么 value 为 1
                    // i = 1,那么 value 为 1 * 10 + 2 = 12
                    // i = 2,那么 value 为 12 * 10 + 3 = 123
                     value = value*10 + s[i] - '0';
                     
                }
                // 那么把获取到的数累加到结果 res 上
                res = res + sign * value;

              // 如果是 '+'
            }else if(ch == '+'){
                // 那么说明直接加一个正数
                sign = 1;
              // 如果是 '-'
            }else if(ch == '-'){
                // 那么说明加一个负数
                sign = -1;

              // 如果是 '('
            }else if(ch == '('){
                // 根据数学计算规则,需要先计算括号里面的数字
                // 而什么时候计算呢?
                // 遇到 ) 为止
                // 所以,在遇到 ) 之前需要把之前计算好的结果存储起来再计算
                // ( ) 直接的计算规则和一开始是一样的

                // 1、先把 ( 之前的结果存放到栈中
                st.push(res);

                // 2、重新初始化 res 为 0
                res = 0;

                // 3、把 ( 左边的操作符号存放到栈中
                // 比如如果是 5 - ( 2 + 3 ) ,那么就是把 -1 存放进去
                // 比如如果是 5 +( 2 + 3 ) ,那么就是把 1 存放进去
                st.push(sign);
                
                // 4、为了方便计算,所有的操作都视为加法操作
                // 那么原先的减法操作就相当于是加一个负数
                // 默认都是正数
                sign = 1;

            // 如果是 ')'
            }else if(ch == ')'){
                // 那么就需要把栈中存放的元素取出来了
                // 在 ch == '(' 这个判断语句中,每次都会往栈中存放两个元素
                // 1、先存放左括号外面的结果
                // 2、再存放左括号外面的符号

                // 1、先获取栈顶元素,即左括号外面的符号,查看是 + 还是 -
                int formerSign = st.top();

                // 把栈顶元素弹出
                st.pop();

                // 2、再获取栈顶元素,即左括号结果
                int formerRes = st.top();

                // 把栈顶元素弹出
                st.pop();

                // 那结果就是括号外面的结果 + 括号里面的结果,至于是加正数还是负数,取决于左括号外面的符号
                res = formerRes +formerSign*res;
            }
        }

        // 返回计算好的结果
        return res;
    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者:程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# 基本计算器( LeetCode 224 ):https://leetcode-cn.com/problems/basic-calculator
class Solution:
    def calculate(self, s: str) -> int:

        # 使用栈来储存字符串表达式中的数字
        stack = list()

        # 为了方便计算,所有的操作都视为加法操作
        # 那么原先的减法操作就相当于是加一个负数
        # 默认都是正数
        sign = 1

        # 保存计算的结果
        res = 0

        # 获取字符串的长度,然后获取里面的每个字符
        length = len(s)

        # 从 0 开始访问字符串中的每个字符
        i = 0

        # 获取字符串里面的每个字符
        while i < length:
            # 获取此时的字符
            ch = s[i]

            if ch == ' ' :
                i += 1
            # 如果当前字符是数字的话
            elif ch.isdigit() :
                # 那么把获取到的数累加到结果 res 上
                value = 0

                # 去查看当前字符的后一位是否存在
                # 如果操作并且后一位依旧是数字,那么就需要把后面的数字累加上来
                while i < length and s[i].isdigit():
                    value = value * 10 + ord(s[i]) - ord('0')
                    i += 1
                
                # 那么把获取到的数累加到结果 res 上
                res += value * sign

              # 如果是 '+'
            elif ch == '+' :
                # 那么说明直接加一个正数
                sign = 1

                i += 1

              # 如果是 '-'
            elif ch == '-' :

                # 那么说明加一个负数
                sign = -1

                i += 1

              # 如果是 '('
            elif ch == '(' :
                # 根据数学计算规则,需要先计算括号里面的数字
                # 而什么时候计算呢?
                # 遇到 ) 为止
                # 所以,在遇到 ) 之前需要把之前计算好的结果存储起来再计算
                # ( ) 直接的计算规则和一开始是一样的

                # 1、先把 ( 之前的结果存放到栈中
                stack.append(res)

                # 2、重新初始化 res 为 0
                res = 0
                # 3、把 ( 左边的操作符号存放到栈中
                # 比如如果是 5 - ( 2 + 3 ) ,那么就是把 -1 存放进去
                # 比如如果是 5 +( 2 + 3 ) ,那么就是把 1 存放进去
                stack.append(sign)

                # 4、为了方便计算,所有的操作都视为加法操作
                # 那么原先的减法操作就相当于是加一个负数
                # 默认都是正数
                sign = 1

                i += 1

                # 如果是 ')'
            elif ch == ')' :
                
                # 那么就需要把栈中存放的元素取出来了
                # 在 ch == '(' 这个判断语句中,每次都会往栈中存放两个元素
                # 1、先存放左括号外面的结果
                # 2、再存放左括号外面的符号

                # 1、先获取栈顶元素,即左括号外面的符号,查看是 + 还是 -
                # 把栈顶元素弹出
                formerSign = stack.pop()

                # 2、再获取栈顶元素,即左括号结果
                # 把栈顶元素弹出
                formerRes = stack.pop()

                # 那结果就是括号外面的结果 + 括号里面的结果,至于是加正数还是负数,取决于左括号外面的符号
                res = formerRes +  formerSign * res 

                i += 1
             

        # 返回计算好的结果
        return res

四、复杂度分析

时间复杂度:O(n),其中 n 为字符串 s 的长度。需要遍历字符串 s 一次,计算表达式的值。

空间复杂度:O(n),其中 n 为字符串 s 的长度。空间复杂度主要取决于栈的空间,栈中的元素数量不超过 n。

--- EOF ---


推荐↓↓↓


网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复