【栈】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

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

基本知识点

1、c++的输入加上ios::sync_with_stdio(false);  等价于 c的输入,读取速度会加快(但是在字符串的题里面和容易出现问题) 2、lower_bound()和upper_bound() iterator lower_bound( const key_type &key ): 返回一个迭代器,指向键值>= key的第一个元素。 iterator upper_bou

【IPV6从入门到起飞】5-1 IPV6+Home Assistant(搭建基本环境)

【IPV6从入门到起飞】5-1 IPV6+Home Assistant #搭建基本环境 1 背景2 docker下载 hass3 创建容器4 浏览器访问 hass5 手机APP远程访问hass6 更多玩法 1 背景 既然电脑可以IPV6入站,手机流量可以访问IPV6网络的服务,为什么不在电脑搭建Home Assistant(hass),来控制你的设备呢?@智能家居 @万物互联

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

C 语言的基本数据类型

C 语言的基本数据类型 注:本文面向 C 语言初学者,如果你是熟手,那就不用看了。 有人问我,char、short、int、long、float、double 等这些关键字到底是什么意思,如果说他们是数据类型的话,那么为啥有这么多数据类型呢? 如果写了一句: int a; 那么执行的时候在内存中会有什么变化呢? 橡皮泥大家都玩过吧,一般你买橡皮泥的时候,店家会赠送一些模板。 上

FreeRTOS-基本介绍和移植STM32

FreeRTOS-基本介绍和STM32移植 一、裸机开发和操作系统开发介绍二、任务调度和任务状态介绍2.1 任务调度2.1.1 抢占式调度2.1.2 时间片调度 2.2 任务状态 三、FreeRTOS源码和移植STM323.1 FreeRTOS源码3.2 FreeRTOS移植STM323.2.1 代码移植3.2.2 时钟中断配置 一、裸机开发和操作系统开发介绍 裸机:前后台系