LeetCode 题解 | 224.基本计算器(基本运算器)
ztj100 2024-10-27 18:32 26 浏览 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 的情况,这是不正确的。减法即不遵循结合律也不遵循交换律。
这个问题很容易解决,我们通过反转字符串,然后再按需添加到栈中,我们将字符串从右到左放入栈中,并从左到右正确的计算表达式。
算法:
- 按逆序迭代字符串。
- 操作数可以由多个字符组成,字符串 "123" 表示数字 123,它可以被构造为:123 >> 120 + 3 >> 100 + 20 + 3。如果我们读取的字符是一个数字,则我们要将读取的数字乘以 10 的幂并将当前数字相加,形成操作数。因为我们是按逆序处理字符串。
- 操作数由多个字符组成,一旦我们遇到的字符不是数字,则我们将操作数添加到栈上。
- 当我们遇到最括号 (,这意味这遇到了一个子表达式结束。由于我们是逆序,所以开括号成了表达式的结尾。则需要从栈中弹出操作数和运算发来计算表达式,直到弹出相应的右括号。子表达式的最终结果最终添加到栈上。
- 将非数字字符添加到栈上。
- 这个做直到我们得到最终的结果。可能我们没有更多的字符要处理,但是栈仍然是非空的。当主表达式没有用括号括起来时,就会发生这种情况。因此,在完成对整个表达式求值之后,我们将检查栈是否非空。如果是的话,我们将栈中的元素作为最终表达式处理,并像遇到左括号时那样对其求值。我们还可以用一组括号覆盖原表达式,以此避免额外调用。
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 关联起来。
/ 我们可以通过遵循前面的基本练习并将符号与其右侧的表达式关联来解决此问题。然而,我们将采用的方法有一个小的转折,因为我们将在运行中评估大多数表达式。这减少了推送和弹出操作的数量。
算法:
- 正序迭代字符串。
- 操作数可以由多个字符组成,字符串 "123" 表示数字 123,它可以被构造为:123 >> 120 + 3 >> 100 + 20 + 3。如果我们读取的字符是一个数字,则我们要将先前形成的操作数乘以 10 并于读取的数字相加,形成操作数。
- 每当我们遇到 + 或 - 运算符时,我们首先将表达式求值到左边,然后将正负符号保存到下一次求值。
- 如果字符是左括号 (,我们将迄今为止计算的结果和符号添加到栈上,然后重新开始进行计算,就像计算一个新的表达式一样。
- 如果字符是右括号 ),则首先计算左侧的表达式。则产生的结果就是刚刚结束的子表达式的结果。如果栈顶部有符号,则将此结果与符号相乘。
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 指的是字符串的长度。
本文作者:力扣
声明:本文归“力扣”版权所有,如需转载请联系。
相关推荐
- Python 操作excel的坑__真实的行和列
-
大佬给的建议__如何快速处理excelopenpyxl库操作excel的时候,单个表的数据量大一些处理速度还能接受,如果涉及多个表甚至多个excel文件的时候速度会很慢,还是建议用pandas来处理,...
- Python os.path模块使用指南:轻松处理文件路径
-
前言在Python编程中,文件和目录的操作是非常重要的一部分。为了方便用户进行文件和目录的操作,Python标准库提供了os模块。其中,os.path子模块提供了一些处理文件路径的函数和方法。本文主要...
- Python常用内置模块介绍——文件与系统操作详解
-
Python提供了多个强大的内置模块用于文件和系统操作,下面我将详细介绍最常用的几个模块及其核心功能。1.os模块-操作系统交互...
- Python Flask 建站框架实操教程(flask框架网页)
-
下面我将带您从零开始构建一个完整的Flask网站,包含用户认证、数据库操作和前端模板等核心功能。##第一部分:基础项目搭建###1.创建项目环境```bash...
- 为你的python程序上锁:软件序列号生成器
-
序列号很多同学可能开发了非常多的程序了,并且进行了...
- PO设计模式全攻略,在 UI 自动化中的实践总结(以企业微信为例)
-
一、什么是PO设计模式?PO(PageObject)设计模式将某个页面的所有元素对象定位和对元素对象的操作封装成一个Page类,即一个py文件,并以页面为单位来写测试用例,实现页面对象和测试用例的...
- 这种小工具居然也能在某鱼卖钱?我用Python一天能写...
-
前两天在某鱼闲逛,本来想找个二手机械键盘,结果刷着刷着突然看到有人在卖——Word批量转PDF小工具...
- python打包成exe,程序有图标,但是任务栏和窗口都没有显示图标
-
代码中指定图标信息#设置应用ID,确保任务栏图标正确显示ifsys.platform=="win32":importctypesapp_id=...
- 使用Python构建电影推荐系统(用python做推荐系统)
-
在日常数据挖掘工作中,除了会涉及到使用Python处理分类或预测任务,有时候还会涉及推荐系统相关任务。...
- python爬取并分析淘宝商品信息(python爬取淘宝商品数据)
-
python爬取并分析淘宝商品信息背景介绍一、模拟登陆二、爬取商品信息1.定义相关参数2.分析并定义正则3.数据爬取三、简单数据分析1.导入库2.中文显示3.读取数据4.分析价格分布5.分析销售...
- OpenCV入门学习基础教程(从小白变大神)
-
Opencv是用于快速处理图像处理、计算机视觉问题的工具,支持多种语言进行开发如c++、python、java等,下面这篇文章主要给大家介绍了关于openCV入门学习基础教程的相关资料,需要的朋友可以...
- python图像处理-一行代码实现灰度图抠图
-
抠图是ps的最基本技能,利用python可以实现用一行代码实现灰度图抠图。基础算法是...
- 从头开始学python:如何用Matplotlib绘图表
-
Matplotlib是一个用于绘制图表的库。如果你有用过python处理数据,那Matplotlib可以更直观的帮你把数据展示出来。直接上代码看例子:importmatplotlib.pyplot...
- Python爬取爱奇艺腾讯视频 250,000 条数据分析为什么李诞不值得了
-
在《Python爬取爱奇艺52432条数据分析谁才是《奇葩说》的焦点人物?》这篇文章中,我们从爱奇艺爬取了5万多条评论数据,并对一些关键数据进行了分析,由此总结出了一些明面上看不到的数据,并...
- Python Matplotlib 库使用基本指南
-
简介Matplotlib是一个广泛使用的Python数据可视化库,它可以创建各种类型的图表、图形和可视化效果。无论是简单的折线图还是复杂的热力图,Matplotlib提供了丰富的功能来满足我们...
你 发表评论:
欢迎- 一周热门
- 最近发表
-
- Python 操作excel的坑__真实的行和列
- Python os.path模块使用指南:轻松处理文件路径
- Python常用内置模块介绍——文件与系统操作详解
- Python Flask 建站框架实操教程(flask框架网页)
- 为你的python程序上锁:软件序列号生成器
- PO设计模式全攻略,在 UI 自动化中的实践总结(以企业微信为例)
- 这种小工具居然也能在某鱼卖钱?我用Python一天能写...
- python打包成exe,程序有图标,但是任务栏和窗口都没有显示图标
- 使用Python构建电影推荐系统(用python做推荐系统)
- python爬取并分析淘宝商品信息(python爬取淘宝商品数据)
- 标签列表
-
- idea eval reset (50)
- vue dispatch (70)
- update canceled (42)
- order by asc (53)
- spring gateway (67)
- 简单代码编程 贪吃蛇 (40)
- transforms.resize (33)
- redisson trylock (35)
- 卸载node (35)
- np.reshape (33)
- torch.arange (34)
- npm 源 (35)
- vue3 deep (35)
- win10 ssh (35)
- vue foreach (34)
- idea设置编码为utf8 (35)
- vue 数组添加元素 (34)
- std find (34)
- tablefield注解用途 (35)
- python str转json (34)
- java websocket客户端 (34)
- tensor.view (34)
- java jackson (34)
- vmware17pro最新密钥 (34)
- mysql单表最大数据量 (35)