百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 技术分类 > 正文

LeetCode 题解 | 224.基本计算器(基本运算器)

ztj100 2024-10-27 18:32 31 浏览 0 评论


力扣 224.基本计算器 点击查看题目


题目描述


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

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


示例 1:

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

示例 2:

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

示例 3:

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


说明

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


解决方案

概述

解决这个问题需要理解以下内容:

  • 输入始终包含有效的字符串。
  • 加减法规则。
  • 括号中的优先含义。
  • 空格不影响输入表达式的计算。


方法一:栈和反转字符串

这个问题适合用栈来解决,因为表达式中包含括号,我们可以使用栈来查找每个子表达式的值。本质上,我们需要延迟处理主表达式,直到完成对括号种的中间子表达式的求值,我们使用栈来解决它。

我们将表达式的元素一个接一个的添加到栈上,直到我们遇到一个右括号 )。然后逐个弹出栈中的元素,在运行时对子表达式进行求值,直到遇到左括号 ( 为止。

我们需要理解 + 和 - 的区别。+ 遵循结合律。例如 A + B + C,等价于(A + B )+ C = A +(B + C)。然后 - 不遵循这个一规则,这是该方法中所有问题的根本原因。

如果我们使用栈并从左到右读取表达式的元素,则最终我们会从右到左计算表达式。就会出现 (A -B)- C 等于(C - B)- A 的情况,这是不正确的。减法即不遵循结合律也不遵循交换律。

这个问题很容易解决,我们通过反转字符串,然后再按需添加到栈中,我们将字符串从右到左放入栈中,并从左到右正确的计算表达式。


算法

  1. 按逆序迭代字符串。
  2. 操作数可以由多个字符组成,字符串 "123" 表示数字 123,它可以被构造为:123 >> 120 + 3 >> 100 + 20 + 3。如果我们读取的字符是一个数字,则我们要将读取的数字乘以 10 的幂并将当前数字相加,形成操作数。因为我们是按逆序处理字符串。
  3. 操作数由多个字符组成,一旦我们遇到的字符不是数字,则我们将操作数添加到栈上。
  4. 当我们遇到最括号 (,这意味这遇到了一个子表达式结束。由于我们是逆序,所以开括号成了表达式的结尾。则需要从栈中弹出操作数和运算发来计算表达式,直到弹出相应的右括号。子表达式的最终结果最终添加到栈上。
  5. 将非数字字符添加到栈上。
  6. 这个做直到我们得到最终的结果。可能我们没有更多的字符要处理,但是栈仍然是非空的。当主表达式没有用括号括起来时,就会发生这种情况。因此,在完成对整个表达式求值之后,我们将检查栈是否非空。如果是的话,我们将栈中的元素作为最终表达式处理,并像遇到左括号时那样对其求值。我们还可以用一组括号覆盖原表达式,以此避免额外调用。


Python 实现(电脑端查看代码)

class Solution:

    def evaluate_expr(self, stack):
        res = stack.pop() if stack else 0

        # Evaluate the expression till we get corresponding ')'
        while stack and stack[-1] != ')':
            sign = stack.pop()
            if sign == '+':
                res += stack.pop()
            else:
                res -= stack.pop()
        return res

    def calculate(self, s: str) -> int:

        stack = []
        n, operand = 0, 0

        for i in range(len(s) - 1, -1, -1):
            ch = s[i]

            if ch.isdigit():

                # Forming the operand - in reverse order.
                operand = (10**n * int(ch)) + operand
                n += 1

            elif ch != " ":
                if n:
                    # Save the operand on the stack
                    # As we encounter some non-digit.
                    stack.append(operand)
                    n, operand = 0, 0

                if ch == '(':         
                    res = self.evaluate_expr(stack)
                    stack.pop()

                    # Append the evaluated result to the stack.
                    # This result could be of a sub-expression within the parenthesis.
                    stack.append(res)

                # For other non-digits just push onto the stack.
                else:
                    stack.append(ch)

        # Push the last operand to stack, if any.
        if n:
            stack.append(operand)

        # Evaluate any left overs in the stack.
        return self.evaluate_expr(stack)


Java 实现(电脑端查看代码)

class Solution {

    public int evaluateExpr(Stack<Object> stack) {

        int res = 0;

        if (!stack.empty()) {
            res = (int) stack.pop();
        }

        // Evaluate the expression till we get corresponding ')'
        while (!stack.empty() && !((char) stack.peek() == ')')) {

            char sign = (char) stack.pop();

            if (sign == '+') {
                res += (int) stack.pop();
            } else {
                res -= (int) stack.pop();
            }
        }
        return res;
    }

    public int calculate(String s) {

        int operand = 0;
        int n = 0;
        Stack<Object> stack = new Stack<Object>();

        for (int i = s.length() - 1; i >= 0; i--) {

            char ch = s.charAt(i);

            if (Character.isDigit(ch)) {

                // Forming the operand - in reverse order.
                operand = (int) Math.pow(10, n) * (int) (ch - '0') + operand;
                n += 1;

            } else if (ch != ' ') {
                if (n != 0) {

                    // Save the operand on the stack
                    // As we encounter some non-digit.
                    stack.push(operand);
                    n = 0;
                    operand = 0;

                }
                if (ch == '(') {

                    int res = evaluateExpr(stack);
                    stack.pop();

                    // Append the evaluated result to the stack.
                    // This result could be of a sub-expression within the parenthesis.
                    stack.push(res);

                } else {
                    // For other non-digits just push onto the stack.
                    stack.push(ch);
                }
            }
        }

        //Push the last operand to stack, if any.
        if (n != 0) {
            stack.push(operand);
        }

        // Evaluate any left overs in the stack.
        return evaluateExpr(stack);
    }
}


复杂度分析

时间复杂度:O(N),其中 N 指的是字符串的长度。

空间复杂度:O(N),其中 N 指的是字符串的长度。


方法二:栈和不反转字符串

解决 - 结合律的问题的一个分厂简单的方法就是使将 - 运算符看作右侧操作数的大小。一旦我们将 - 看作操作数的大小,则表达式将只剩下一个操作符。就是 + 运算符,而 + 是遵循结合律的。

例如,A - B - C 等于 A +(-B)+(-C)。

重写以后的表达式将遵循结合律,所以我们从左或从右计算表达式都是正确的。

我们需要注意的是给定的表达式会很复杂,即会有嵌套在其他表达式的表达式。即 (A - (B - C),我们需要 B-C 外面的 - 号与 B-C 关联起来,而不是仅仅与 B 关联起来。

/ 我们可以通过遵循前面的基本练习并将符号与其右侧的表达式关联来解决此问题。然而,我们将采用的方法有一个小的转折,因为我们将在运行中评估大多数表达式。这减少了推送和弹出操作的数量。


算法

  1. 正序迭代字符串。
  2. 操作数可以由多个字符组成,字符串 "123" 表示数字 123,它可以被构造为:123 >> 120 + 3 >> 100 + 20 + 3。如果我们读取的字符是一个数字,则我们要将先前形成的操作数乘以 10 并于读取的数字相加,形成操作数。
  3. 每当我们遇到 + 或 - 运算符时,我们首先将表达式求值到左边,然后将正负符号保存到下一次求值。
  4. 如果字符是左括号 (,我们将迄今为止计算的结果和符号添加到栈上,然后重新开始进行计算,就像计算一个新的表达式一样。
  5. 如果字符是右括号 ),则首先计算左侧的表达式。则产生的结果就是刚刚结束的子表达式的结果。如果栈顶部有符号,则将此结果与符号相乘。


Python 实现(电脑端查看代码)

class Solution:
    def calculate(self, s: str) -> int:

        stack = []
        operand = 0
        res = 0 # For the on-going result
        sign = 1 # 1 means positive, -1 means negative  

        for ch in s:
            if ch.isdigit():

                # Forming operand, since it could be more than one digit
                operand = (operand * 10) + int(ch)

            elif ch == '+':

                # Evaluate the expression to the left,
                # with result, sign, operand
                res += sign * operand

                # Save the recently encountered '+' sign
                sign = 1

                # Reset operand
                operand = 0

            elif ch == '-':

                res += sign * operand
                sign = -1
                operand = 0

            elif ch == '(':

                # Push the result and sign on to the stack, for later
                # We push the result first, then sign
                stack.append(res)
                stack.append(sign)

                # Reset operand and result, as if new evaluation begins for the new sub-expression
                sign = 1
                res = 0

            elif ch == ')':

                # Evaluate the expression to the left
                # with result, sign and operand
                res += sign * operand

                # ')' marks end of expression within a set of parenthesis
                # Its result is multiplied with sign on top of stack
                # as stack.pop() is the sign before the parenthesis
                res *= stack.pop() # stack pop 1, sign

                # Then add to the next operand on the top.
                # as stack.pop() is the result calculated before this parenthesis
                # (operand on stack) + (sign on stack * (result from parenthesis))
                res += stack.pop() # stack pop 2, operand

                # Reset the operand
                operand = 0

        return res + sign * operand


Java 实现(电脑端查看代码)


class Solution {
    public int calculate(String s) {

        Stack<Integer> stack = new Stack<Integer>();
        int operand = 0;
        int result = 0; // For the on-going result
        int sign = 1;  // 1 means positive, -1 means negative

        for (int i = 0; i < s.length(); i++) {

            char ch = s.charAt(i);
            if (Character.isDigit(ch)) {

                // Forming operand, since it could be more than one digit
                operand = 10 * operand + (int) (ch - '0');

            } else if (ch == '+') {

                // Evaluate the expression to the left,
                // with result, sign, operand
                result += sign * operand;

                // Save the recently encountered '+' sign
                sign = 1;

                // Reset operand
                operand = 0;

            } else if (ch == '-') {

                result += sign * operand;
                sign = -1;
                operand = 0;

            } else if (ch == '(') {

                // Push the result and sign on to the stack, for later
                // We push the result first, then sign
                stack.push(result);
                stack.push(sign);

                // Reset operand and result, as if new evaluation begins for the new sub-expression
                sign = 1;
                result = 0;

            } else if (ch == ')') {

                // Evaluate the expression to the left
                // with result, sign and operand
                result += sign * operand;

                // ')' marks end of expression within a set of parenthesis
                // Its result is multiplied with sign on top of stack
                // as stack.pop() is the sign before the parenthesis
                result *= stack.pop();

                // Then add to the next operand on the top.
                // as stack.pop() is the result calculated before this parenthesis
                // (operand on stack) + (sign on stack * (result from parenthesis))
                result += stack.pop();

                // Reset the operand
                operand = 0;
            }
        }
        return result + (sign * operand);
    }
}


复杂度分析

时间复杂度:O(N),其中 N 指的是字符串的长度。这种方法与前一种方法的区别在于,这种方法的每个字符都将被精确的处理一次。但是前面的方法中,每个字符可能被处理两次,一次是被添加到栈上,另一次是被弹出处理最终结果。这就是为什么这种方法更快的原因。

空间复杂度:O(N),其中 N 指的是字符串的长度。


本文作者:力扣

声明:本文归“力扣”版权所有,如需转载请联系。

相关推荐

sharding-jdbc实现`分库分表`与`读写分离`

一、前言本文将基于以下环境整合...

三分钟了解mysql中主键、外键、非空、唯一、默认约束是什么

在数据库中,数据表是数据库中最重要、最基本的操作对象,是数据存储的基本单位。数据表被定义为列的集合,数据在表中是按照行和列的格式来存储的。每一行代表一条唯一的记录,每一列代表记录中的一个域。...

MySQL8行级锁_mysql如何加行级锁

MySQL8行级锁版本:8.0.34基本概念...

mysql使用小技巧_mysql使用入门

1、MySQL中有许多很实用的函数,好好利用它们可以省去很多时间:group_concat()将取到的值用逗号连接,可以这么用:selectgroup_concat(distinctid)fr...

MySQL/MariaDB中如何支持全部的Unicode?

永远不要在MySQL中使用utf8,并且始终使用utf8mb4。utf8mb4介绍MySQL/MariaDB中,utf8字符集并不是对Unicode的真正实现,即不是真正的UTF-8编码,因...

聊聊 MySQL Server 可执行注释,你懂了吗?

前言MySQLServer当前支持如下3种注释风格:...

MySQL系列-源码编译安装(v5.7.34)

一、系统环境要求...

MySQL的锁就锁住我啦!与腾讯大佬的技术交谈,是我小看它了

对酒当歌,人生几何!朝朝暮暮,唯有己脱。苦苦寻觅找工作之间,殊不知今日之事乃我心之痛,难道是我不配拥有工作嘛。自面试后他所谓的等待都过去一段时日,可惜在下京东上的小金库都要见低啦。每每想到不由心中一...

MySQL字符问题_mysql中字符串的位置

中文写入乱码问题:我输入的中文编码是urf8的,建的库是urf8的,但是插入mysql总是乱码,一堆"???????????????????????"我用的是ibatis,终于找到原因了,我是这么解决...

深圳尚学堂:mysql基本sql语句大全(三)

数据开发-经典1.按姓氏笔画排序:Select*FromTableNameOrderByCustomerNameCollateChinese_PRC_Stroke_ci_as//从少...

MySQL进行行级锁的?一会next-key锁,一会间隙锁,一会记录锁?

大家好,是不是很多人都对MySQL加行级锁的规则搞的迷迷糊糊,一会是next-key锁,一会是间隙锁,一会又是记录锁。坦白说,确实还挺复杂的,但是好在我找点了点规律,也知道如何如何用命令分析加...

一文讲清怎么利用Python Django实现Excel数据表的导入导出功能

摘要:Python作为一门简单易学且功能强大的编程语言,广受程序员、数据分析师和AI工程师的青睐。本文系统讲解了如何使用Python的Django框架结合openpyxl库实现Excel...

用DataX实现两个MySQL实例间的数据同步

DataXDataX使用Java实现。如果可以实现数据库实例之间准实时的...

MySQL数据库知识_mysql数据库基础知识

MySQL是一种关系型数据库管理系统;那废话不多说,直接上自己以前学习整理文档:查看数据库命令:(1).查看存储过程状态:showprocedurestatus;(2).显示系统变量:show...

如何为MySQL中的JSON字段设置索引

背景MySQL在2015年中发布的5.7.8版本中首次引入了JSON数据类型。自此,它成了一种逃离严格列定义的方式,可以存储各种形状和大小的JSON文档,例如审计日志、配置信息、第三方数据包、用户自定...

取消回复欢迎 发表评论: