【栈】Leetcode 224. 基本计算器【困难】

2024-05-24 13:04

本文主要是介绍【栈】Leetcode 224. 基本计算器【困难】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

基本计算器

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

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

示例 1:

输入:s = “1 + 1”
输出:2

示例 2:

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

示例 3:

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

解题思路

  • 要实现一个基本计算器(只有加减法和括号)来计算给定的字符串表达式,
  • 可以使用栈来处理括号和运算优先级问题(类似 逆波兰表达式,只不过多了一些判断)。

Java实现

public class BasicCalculator {public int calculate(String s) {Stack<Integer> stack = new Stack<>();int result = 0;int num = 0;int sign = 1; // 1 表示正号, -1 表示负号for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (Character.isDigit(c)) {//数字转换num = num * 10 + (c - '0');} else if (c == '+') {//计算要加得数字result += sign * num;num = 0;sign = 1;} else if (c == '-') {//计算要减的数字result += sign * num;num = 0;sign = -1;} else if (c == '(') {// 将当前的结果和符号压入栈stack.push(result);stack.push(sign);// 重置结果和符号result = 0;sign = 1;} else if (c == ')') {// 先将当前 num 加到 resultresult += sign * num;num = 0;// 弹出栈顶符号并与当前结果相乘result *= stack.pop();// 弹出栈顶的之前的结果并相加result += stack.pop();}}// 最后一次操作后的结果if (num != 0) {result += sign * num;}return result;}public static void main(String[] args) {BasicCalculator calculator = new BasicCalculator();System.out.println(calculator.calculate("1 + 1")); // 输出: 2System.out.println(calculator.calculate(" 2-1 + 2 ")); // 输出: 3System.out.println(calculator.calculate("(1+(4+5+2)-3)+(6+8)")); // 输出: 23}
}

时间空间复杂度

  • 时间复杂度: O(n),其中 n 是字符串的长度。每个字符只处理一次。
  • 空间复杂度: O(n),用于存储栈的空间,最坏情况下栈的深度与字符串长度成正比

这篇关于【栈】Leetcode 224. 基本计算器【困难】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/998485

相关文章

MySQL 中的 LIMIT 语句及基本用法

《MySQL中的LIMIT语句及基本用法》LIMIT语句用于限制查询返回的行数,常用于分页查询或取部分数据,提高查询效率,:本文主要介绍MySQL中的LIMIT语句,需要的朋友可以参考下... 目录mysql 中的 LIMIT 语句1. LIMIT 语法2. LIMIT 基本用法(1) 获取前 N 行数据(

Python Faker库基本用法详解

《PythonFaker库基本用法详解》Faker是一个非常强大的库,适用于生成各种类型的伪随机数据,可以帮助开发者在测试、数据生成、或其他需要随机数据的场景中提高效率,本文给大家介绍PythonF... 目录安装基本用法主要功能示例代码语言和地区生成多条假数据自定义字段小结Faker 是一个 python

用js控制视频播放进度基本示例代码

《用js控制视频播放进度基本示例代码》写前端的时候,很多的时候是需要支持要网页视频播放的功能,下面这篇文章主要给大家介绍了关于用js控制视频播放进度的相关资料,文中通过代码介绍的非常详细,需要的朋友可... 目录前言html部分:JavaScript部分:注意:总结前言在javascript中控制视频播放

SpringBoot整合MybatisPlus的基本应用指南

《SpringBoot整合MybatisPlus的基本应用指南》MyBatis-Plus,简称MP,是一个MyBatis的增强工具,在MyBatis的基础上只做增强不做改变,下面小编就来和大家介绍一下... 目录一、MyBATisPlus简介二、SpringBoot整合MybatisPlus1、创建数据库和

Python中多线程和多进程的基本用法详解

《Python中多线程和多进程的基本用法详解》这篇文章介绍了Python中多线程和多进程的相关知识,包括并发编程的优势,多线程和多进程的概念、适用场景、示例代码,线程池和进程池的使用,以及如何选择合适... 目录引言一、并发编程的主要优势二、python的多线程(Threading)1. 什么是多线程?2.

MyBatis-Flex BaseMapper的接口基本用法小结

《MyBatis-FlexBaseMapper的接口基本用法小结》本文主要介绍了MyBatis-FlexBaseMapper的接口基本用法小结,文中通过示例代码介绍的非常详细,对大家的学习或者工作具... 目录MyBATis-Flex简单介绍特性基础方法INSERT① insert② insertSelec

JAVA调用Deepseek的api完成基本对话简单代码示例

《JAVA调用Deepseek的api完成基本对话简单代码示例》:本文主要介绍JAVA调用Deepseek的api完成基本对话的相关资料,文中详细讲解了如何获取DeepSeekAPI密钥、添加H... 获取API密钥首先,从DeepSeek平台获取API密钥,用于身份验证。添加HTTP客户端依赖使用Jav

C++中使用vector存储并遍历数据的基本步骤

《C++中使用vector存储并遍历数据的基本步骤》C++标准模板库(STL)提供了多种容器类型,包括顺序容器、关联容器、无序关联容器和容器适配器,每种容器都有其特定的用途和特性,:本文主要介绍C... 目录(1)容器及简要描述‌php顺序容器‌‌关联容器‌‌无序关联容器‌(基于哈希表):‌容器适配器‌:(

使用Python进行文件读写操作的基本方法

《使用Python进行文件读写操作的基本方法》今天的内容来介绍Python中进行文件读写操作的方法,这在学习Python时是必不可少的技术点,希望可以帮助到正在学习python的小伙伴,以下是Pyth... 目录一、文件读取:二、文件写入:三、文件追加:四、文件读写的二进制模式:五、使用 json 模块读写

用Java打造简易计算器的实现步骤

《用Java打造简易计算器的实现步骤》:本文主要介绍如何设计和实现一个简单的Java命令行计算器程序,该程序能够执行基本的数学运算(加、减、乘、除),文中通过代码介绍的非常详细,需要的朋友可以参考... 目录目标:一、项目概述与功能规划二、代码实现步骤三、测试与优化四、总结与收获总结目标:简单计算器,设计