【LeetCode: 224. 基本计算器 + 模拟 + 栈】

2024-03-21 10:44

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

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持,因为它具有很高的价值,算法就是这样✨
🌲 作者简介:硕风和炜,CSDN-Java领域优质创作者🏆,保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋,我愿为卒,行动虽慢,可谁曾见我后退一步?🎯🎯

🚀 算法题 🚀

在这里插入图片描述

在这里插入图片描述

🍔 目录

    • 🚩 题目链接
    • ⛲ 题目描述
    • 🌟 求解思路&实现代码&运行结果
      • ⚡ 模拟 + 栈
        • 🥦 求解思路
        • 🥦 实现代码
        • 🥦 运行结果
    • 💬 共勉

🚩 题目链接

  • 224. 基本计算器

⛲ 题目描述

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

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

示例 1:

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

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

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

提示:

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

🌟 求解思路&实现代码&运行结果


⚡ 模拟 + 栈

🥦 求解思路
  1. 参考双栈解法题解
  2. 通过俩个栈来实现基本计算器的功能,一个栈用来存储数字,另外一个栈用来存储操作数,主要包括(、)、+、-。
  3. 主要思路:从前向后遍历,对遍历到的字符做分情况讨论
  4. 如果遇到空格直接跳过;如果是左括号加入操作数栈中,等到与右括号匹配;如果遇到右括号,使用现有的数字栈和操作数栈进行计算,直到遇到左边最近的一个左括号为止,计算结果放到数字栈中;如果遇到数字,从当前位置开始继续往后取,将整一个连续数字整体取出,加入到数字栈中;如果遇到加号或者减号,将操作放入 操作栈中,在放入之前把栈内的都先计算,计算结果放到数字栈中,操作最后加入操作栈中。
  5. 有了基本的思路,接下来我们就来通过代码来实现一下。
🥦 实现代码
class Solution {public int calculate(String s) {Deque<Integer> nums = new ArrayDeque<>();Deque<Character> ops = new ArrayDeque<>();nums.addLast(0);s = s.replaceAll(" ", "");int n = s.length();char[] cs = s.toCharArray();for (int i = 0; i < n; i++) {char c = cs[i];if (c == '(') {ops.addLast(c);} else if (c == ')') {while (!ops.isEmpty()) {char op = ops.peekLast();if (op != '(') {calc(nums, ops);} else {ops.pollLast();break;}}} else {if (Character.isDigit(c)) {int num = 0;int j = i;while (j < n && Character.isDigit(cs[j]))num = num * 10 + (int) (cs[j++] - '0');nums.addLast(num);i = j - 1;} else {if (i > 0 && (cs[i - 1] == '(' || cs[i - 1] == '+' || cs[i - 1] == '-')) {nums.addLast(0);}while (!ops.isEmpty() && ops.peekLast() != '(')calc(nums, ops);ops.addLast(c);}}}while (!ops.isEmpty())calc(nums, ops);return nums.peekLast();}public void calc(Deque<Integer> nums, Deque<Character> ops) {if (nums.isEmpty() || nums.size() < 2)return;if (ops.isEmpty())return;int b = nums.pollLast(), a = nums.pollLast();char op = ops.pollLast();nums.addLast(op == '+' ? a + b : a - b);}}
🥦 运行结果

在这里插入图片描述


💬 共勉

最后,我想和大家分享一句一直激励我的座右铭,希望可以与大家共勉!

在这里插入图片描述

在这里插入图片描述

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



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

相关文章

哈希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

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

usaco 1.2 Transformations(模拟)

我的做法就是一个一个情况枚举出来 注意计算公式: ( 变换后的矩阵记为C) 顺时针旋转90°:C[i] [j]=A[n-j-1] [i] (旋转180°和270° 可以多转几个九十度来推) 对称:C[i] [n-j-1]=A[i] [j] 代码有点长 。。。 /*ID: who jayLANG: C++TASK: transform*/#include<

【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),来控制你的设备呢?@智能家居 @万物互联

hdu4431麻将模拟

给13张牌。问增加哪些牌可以胡牌。 胡牌有以下几种情况: 1、一个对子 + 4组 3个相同的牌或者顺子。 2、7个不同的对子。 3、13幺 贪心的思想: 对于某张牌>=3个,先减去3个相同,再组合顺子。 import java.io.BufferedInputStream;import java.io.BufferedReader;import java.io.IOExcepti

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,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点