当前位置: 首页 > news >正文

【算法题解】实现一个包含“正负数和括号”的基本计算器

这是一道 困难 题。

题目来自:leetcode

题目

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

注意: 不允许使用任何将字符串作为数学表达式计算的内置函数,比如 eval() 。

提示:

  • s 由数字、‘+’、‘-’、‘(’、‘)’、和 ’ ’ 组成
  • s 表示一个有效的表达式
  • +’ 不能用作一元运算(例如, “+1” 和 “+(2 + 3)” 无效)
  • 输入中不存在两个连续的操作符
  • 每个数字和运行的计算将适合于一个有符号的 32位 整数

示例 1:

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

示例 2:

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

示例 3:

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

解题思路

这道题是 实现一个包含“加减乘除”的基本计算器 的扩展,在表达式中增加了 括号 “(”, “)”正负数,但是删除了 “*” 和 “/”。

在原来的解题方法中补充以下几点:

  1. 括号的处理:
    • 如果遇到左括号:直接压入操作符栈。
    • 如果遇到右括号:将操作符栈中左括号后面的所有操作符出栈,并与数字栈进行计算合并。
  2. 正负数的处理:
    • 可以使用 补0 的思路,在正负数前面加一个“0”,将表达式转换为没有正负号的式子。

那么如何确定“+”和“-”是代表算符还是正负号呢?

  1. 如果 “+”和“-” 是第一个非空字符,那么代表是正负号。
  2. 如果 “+”和“-” 的前一个非空字符也是“+”或者“-”,那么代表是正负号。
  3. 如果 “+”和“-” 的前一个非空字符是 左括号 ,那么代表是正负号。

:补0的思路只能用于加减法.

代码实现


class Solution {private Deque<Integer> numStack = new LinkedList<>();private Deque<Character> optStack = new LinkedList<>();public int calculate(String s) {int n = s.length();boolean needZero = true;for(int i = 0; i < n; i++){char ch = s.charAt(i);if(this.isNumber(ch)){int num = 0;needZero = false;while(i < n && this.isNumber(s.charAt(i))){num = num * 10 + s.charAt(i) - '0';i++;}numStack.push(num);i--;}else if(ch == ' '){continue;}else if(ch == '('){optStack.push('(');needZero = true;continue;}else if(ch == ')'){while(optStack.peek() != '('){this.calc(numStack, optStack);}// 删除左括号optStack.pop();needZero = false;}else{if(needZero){numStack.push(0);}while(!optStack.isEmpty() && optStack.peek() != '('){this.calc(numStack, optStack);}optStack.push(ch);needZero = true;}}while(!optStack.isEmpty()){this.calc(numStack, optStack);}return numStack.pop();}private boolean isNumber(char ch){return ch >= '0' && ch <= '9';}private void calc(Deque<Integer> numStack, Deque<Character> optStack){int num2 = numStack.pop();int num1 = numStack.pop();char opt = optStack.pop();if(opt == '+'){  numStack.push(num1 + num2);}else{numStack.push(num1 - num2);}}}

复杂度分析

时间复杂度:O(N)O(N)O(N),N 为字符串长度。

空间复杂度:O(N)O(N)O(N),N 为字符串长度。

相关文章:

【算法题解】实现一个包含“正负数和括号”的基本计算器

这是一道 困难 题。 题目来自&#xff1a;leetcode 题目 给你一个字符串表达式 s &#xff0c;请你实现一个基本计算器来计算并返回它的值。 注意: 不允许使用任何将字符串作为数学表达式计算的内置函数&#xff0c;比如 eval() 。 提示&#xff1a; s 由数字、‘’、‘-’…...

网站服务器如何防护攻击?网站服务器被挂马如何检测

网站服务器是指安装在互联网上的服务器&#xff0c;主要用于提供网站服务。由于网站服务器的重要性&#xff0c;它也是攻击者的活动焦点&#xff0c;因此如何防护攻击就显得尤为重要。本文将分析网站服务器是如何被攻击的以及如何防护攻击。 网站服务器是怎么被攻击的? 网站…...

JavaSE16-面向对象-接口

文章目录一、概念二、格式1.使用interface来定义接口2.implements实现接口三、接口中的成员1.常用成员2.新增成员&#xff08;不重要&#xff09;2.1 默认方法2.2 静态方法2.3 私有方法四、继承关系 & 实现关系五、抽象类和接口的使用区别一、概念 接口就是规范\规则&…...

安卓设备蓝牙键盘快捷键

安卓设备蓝牙键盘快捷键前言注意鼠标按键系统快捷键桌面快捷键输入法快捷键其它快捷键旧快捷键&#xff08;已失效&#xff09;前言 安卓设备可以通过蓝牙或有线外接键盘&#xff0c;值得一提的是&#xff0c;安卓平板连接蓝牙键盘和蓝牙鼠标是一个不错的组合。本文以鸿蒙3.0平…...

Puppeteer项目结构梳理

最近接触了一个个人感觉很奈斯的项目&#xff0c;故记录思路如下&#xff1a; puppeteer项目梳理&#xff1a; 入口文件 run.js 入口命令 node run.js YourConfig.json 1、我们可以在自己的config.json里面设置好 ①、登录的用户名密码;aws或其它服务器的access等id,accessKey…...

(02)Unity HDRP Volume 详解

1.概述这篇文章主要针对HDRP中的Volume和Volume Post-processing进行解释&#xff0c;针对于各个组件只能进行部分参数的解释&#xff0c;具体的信息可参考官方资料&#xff0c;这里只是对官方文档的图片效果补充以及笔者自己的理解。看到这里进入正文&#xff0c;请确保你的Un…...

拒绝B站邀约,从月薪3k到年薪47W,我的经验值得每一个测试人借鉴

有时候&#xff0c;大佬们总是会特立独行。因为像我这样的常人总是想不通&#xff0c;究竟是怎样的情境&#xff0c;连B站这样的大厂面试都可以推掉&#xff1f; 缘起一通电话&#xff0c;踏出了改变人生轨迹的第一步 我是小瑾&#xff0c;今年28岁&#xff0c;2016年毕业于陕…...

分享一种实用redis原子锁的方式

1. setnx(lockkey, 当前时间过期超时时间) &#xff0c;如果返回1&#xff0c;则获取锁成功&#xff1b;如果返回0则没有获取到锁&#xff0c;转向2。2. get(lockkey)获取值oldExpireTime &#xff0c;并将这个value值与当前的系统时间进行比较&#xff0c;如果小于当前系统时间…...

【华为OD机试】 字符串解密(C++ Java JavaScript Python)

题目描述 给定两个字符串string1和string2。 string1是一个被加扰的字符串。 string1由小写英文字母(’a’’z’)和数字字符(’0’’9’)组成,而加扰字符串由’0’’9’、’a’’f’组成。 string1里面可能包含0个或多个加扰子串,剩下可能有0个或多个有效子串,这些有…...

金三银四,助力你的大厂梦,2023年软件测试经典面试真题(1)(共3篇)

前言 金三银四即将到来&#xff0c;相信很多小伙伴要面临面试&#xff0c;一直想着说分享一些软件测试的面试题&#xff0c;这段时间做了一些收集和整理&#xff0c;下面共有三篇经典面试题&#xff0c;大家可以试着做一下&#xff0c;答案附在后面&#xff0c;希望能帮助到大…...

假如面试官要你手写一个promise

promise 在开发中&#xff0c;经常需要用到promise&#xff0c;promise具有很多特性&#xff0c;这一次将对promise特性进行总结&#xff0c;并从零写一个promise。 步骤一 Promise特点 1&#xff0c;创建时需要传递一个函数&#xff0c;否则会报错2&#xff0c;会给传入的函…...

【leetcode】寻找重复数

题目链接&#xff1a;寻找重复数https://leetcode.cn/problems/find-the-duplicate-number/ 方法一&#xff1a;快慢指针 因为只有一个数字是重复的&#xff0c;且一个数字正好对应一个唯一的下标&#xff0c;所以可以将数组抽象为一个链表&#xff0c;假定数组为{1,2,3,4,5,…...

LeetCode 1247. Minimum Swaps to Make Strings Equal【数学,贪心,字符串】

本文属于「征服LeetCode」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…...

pid控制加热算法,附代码仓库

1、该项目层次化结构清晰&#xff0c;代码框架耦合度低&#xff0c;可复用性、可移植性强。 2、功能代码与底层硬件无直接关联&#xff0c;无需更改上层应用逻辑&#xff0c;只需更改接口文件&#xff0c;即可移植到不同的硬件平台&#xff1b; 3、使用lwrb开源组件、pid开源算…...

一文看懂预训练和自训练模型

说到预训练模型&#xff0c;不得不提迁移学习了&#xff0c;由于很多数据不是标签数据&#xff0c;人工标注非常耗时&#xff0c;神经网络在很多场景下受到了限制。但是迁移学习和自学习的出现&#xff0c;在一定程度上缓解甚至解决了这个问题。我们可以在标签丰富的场景下进行…...

(五十四)大白话索引的页存储物理结构,是如何用B+树来实现的?.md

上一次我们给大家说了主键索引的目录结构&#xff0c;只要在一个主键索引里包含每个数据页跟他最小主键值&#xff0c;就可以组成一个索引目录&#xff0c;然后后续你查询主键值&#xff0c;就可以在目录里二分查找直接定位到那条数据所属的数据页&#xff0c;接着到数据页里二…...

前端Vue代码风格指南

一、命名规范 市面上常用的命名规范&#xff1a; camelCase&#xff08;小驼峰式命名法 —— 首字母小写&#xff09; PascalCase&#xff08;大驼峰式命名法 —— 首字母大写&#xff09; kebab-case&#xff08;短横线连接式&#xff09; Snake&#xff08;下划线连接式&…...

「TCG 规范解读」基础设施架构和协议 (2)

可信计算组织&#xff08;Ttrusted Computing Group,TCG&#xff09;是一个非盈利的工业标准组织&#xff0c;它的宗旨是加强在相异计算机平台上的计算环境的安全性。TCG于2003年春成立&#xff0c;并采纳了由可信计算平台联盟&#xff08;the Trusted Computing Platform Alli…...

NodeJs 中的 HTML 模板

&#x1f482; 个人网站:【海拥】【摸鱼游戏】【神级源码资源网】&#x1f91f; 前端学习课程&#xff1a;&#x1f449;【28个案例趣学前端】【400个JS面试题】&#x1f485; 想寻找共同学习交流、摸鱼划水的小伙伴&#xff0c;请点击【摸鱼学习交流群】 HTML 模板是一种允许我…...

3.ffmpeg命令行环境搭建、ffmpeg命令行初步了解

在上章,我们讲过: ffmpeg.exe: 主要用于转码或者剪切的应用程序, 也可以从url/现场音频/视频源抓取输入源ffplay.exe: 主要用于播放视频的应用程序,该应用程序源码是开源的,我们后面章节会去源码分析ffprobe.exe: 主要用于分析视频码流的应用程序, 可以获取媒体文件的详细信息,…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

React Native 导航系统实战(React Navigation)

导航系统实战&#xff08;React Navigation&#xff09; React Navigation 是 React Native 应用中最常用的导航库之一&#xff0c;它提供了多种导航模式&#xff0c;如堆栈导航&#xff08;Stack Navigator&#xff09;、标签导航&#xff08;Tab Navigator&#xff09;和抽屉…...

模型参数、模型存储精度、参数与显存

模型参数量衡量单位 M&#xff1a;百万&#xff08;Million&#xff09; B&#xff1a;十亿&#xff08;Billion&#xff09; 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的&#xff0c;但是一个参数所表示多少字节不一定&#xff0c;需要看这个参数以什么…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

R语言速释制剂QBD解决方案之三

本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

[USACO23FEB] Bakery S

题目描述 Bessie 开了一家面包店! 在她的面包店里&#xff0c;Bessie 有一个烤箱&#xff0c;可以在 t C t_C tC​ 的时间内生产一块饼干或在 t M t_M tM​ 单位时间内生产一块松糕。 ( 1 ≤ t C , t M ≤ 10 9 ) (1 \le t_C,t_M \le 10^9) (1≤tC​,tM​≤109)。由于空间…...

客户案例 | 短视频点播企业海外视频加速与成本优化:MediaPackage+Cloudfront 技术重构实践

01技术背景与业务挑战 某短视频点播企业深耕国内用户市场&#xff0c;但其后台应用系统部署于东南亚印尼 IDC 机房。 随着业务规模扩大&#xff0c;传统架构已较难满足当前企业发展的需求&#xff0c;企业面临着三重挑战&#xff1a; ① 业务&#xff1a;国内用户访问海外服…...

python基础语法Ⅰ

python基础语法Ⅰ 常量和表达式变量是什么变量的语法1.定义变量使用变量 变量的类型1.整数2.浮点数(小数)3.字符串4.布尔5.其他 动态类型特征注释注释是什么注释的语法1.行注释2.文档字符串 注释的规范 常量和表达式 我们可以把python当作一个计算器&#xff0c;来进行一些算术…...

OpenHarmony标准系统-HDF框架之I2C驱动开发

文章目录 引言I2C基础知识概念和特性协议&#xff0c;四种信号组合 I2C调试手段硬件软件 HDF框架下的I2C设备驱动案例描述驱动Dispatch驱动读写 总结 引言 I2C基础知识 概念和特性 集成电路总线&#xff0c;由串网12C(1C、12C、Inter-Integrated Circuit BUS)行数据线SDA和串…...