力扣:基本计算器

基本计算器:
224. 基本计算器 - 力扣(LeetCode)

本体思路为,将中缀表达式转为后缀表达式,通过后缀表达式进行运算。

中缀表达式:

我们日常生活中熟知的表达式如1+2-3=0 就是一个中缀表达式。

后缀表达式:
150. 逆波兰表达式求值 - 力扣(LeetCode)

后缀表达式(Postfix Expression),也称为逆波兰表示法(Reverse Polish Notation, RPN),是一种数学表达式的表示方法。在这种表示法中,运算符紧跟在操作数之后,而不是像中缀表达式(如 3 + 4)那样将运算符放在操作数中间。

中缀表达式:常规的数学表达式,如 3 + 4 * 2。

后缀表达式:运算符放在操作数之后,如 3 4 2 * +。

后缀表达式运算:

后缀表达式运算思想为,遇到操作数,入栈,遇到操作符,则弹出栈顶的两个元素,进行操作符匹配运算,当表达式结束后,留在栈顶的操作数就是最后的值。

这里将元素弹出时候,需要进行左元素与右元素区分,因为如果是+*则左元素与右元素没区别,但如果是-/,谁在左,谁在右,区别就很大。

中缀转后缀:

中缀想要转成后缀需要把握两个思想

  1. 遇到操作数载入容器
  2. 遇到操作数,判断操作数的优先级,进行入栈
    1. 如果栈里没有操作符,则直接入栈
    2. 如果栈顶操作符优先级比当前操作符优先级低,则当前操作符入栈
    3. 如果比当前栈顶操作符优先级低或相等,这表示前面的操作符可以进行运算,弹出当前栈顶操作符,载入容器。将当前操作符继续入栈。

如果遇到,(  ),我们可以将它看作为一个子表达式,进行递归运算。

以下是代码实现:

#include<iostream>
#include<map>
#include<vector>
#include<stack>
#include<functional>
#include<algorithm>
#include<string>
using namespace std;class Solution
{
public:void TrunSuffix(string& s, size_t& i, vector<string>& ret){stack<char> st;map<char, int> mp{ {'+',1},{'-',1} ,{'*',2} ,{'/',2} };while (i < s.size()){if (isdigit(s[i])){string num;for (; i < s.size(); i++){if (isdigit(s[i])){num += s[i];}else{break;}}ret.push_back(num);}else if (s[i] == '('){TrunSuffix(s, ++i, ret);}else if (s[i] == ')'){++i;while (!st.empty()){char ch = st.top();st.pop();ret.push_back(string(1, ch));}return;}else{if (st.empty() || mp[st.top()] < mp[s[i]]){st.push(s[i++]);}else{char ch = st.top();st.pop();ret.push_back(string(1, ch));st.push(s[i++]);}}}while (!st.empty()){char ch = st.top();st.pop();ret.push_back(string(1, ch));}}int Suffix(vector<string>& ret){map<string, function<int(int, int)>>mp ={{"+", [](int a, int b) {return a + b; }},{ "-", [](int a, int b) {return a - b; } },{ "*", [](int a, int b) {return a * b; } },{"/", [](int a, int b) {return a / b; }}};stack<int> st;for (auto& e : ret){if (mp.count(e)){int right = st.top();st.pop();int left = st.top();st.pop();int r = mp[e](left, right);st.push(r);}else{st.push(stoi(e));}}return st.top();}int calculate(string s){//1+2-(3*4)string news;for (size_t j = 0; j < s.size(); j++){if (s[j] != ' '){news += s[j];}}s.swap(news);news = "";for (size_t j = 0; j < s.size(); j++){if (s[j] == '-' && (j == 0 || (!isdigit(s[j - 1]) && s[j - 1] != ')'))){news += "0-";}else{news += s[j];}}s.swap(news);news = "";int flag = 0;for (int i = 0; i < s.size(); i++){if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/')flag = 1;}if (!flag){string news;for (auto& e : s){if (isdigit(e)){news += e;}}return stoi(news);}vector<string> ret;size_t i = 0;TrunSuffix(s, i, ret);return Suffix(ret);}
};int main()
{int n=  Solution().calculate(  "(1+(4+5+2)-3)+(6+8)"   );cout << n << endl;return 0;
}

说一下我在写这题的坑:

  1. 这题力扣一开始会给出 “1 + 2 +( 4 - 5)”类似这种带空格的表达式,所以在一开始的时候就需要先过滤一遍表达式,将删除空格。

  1. 我们还需要确认,是负数还是减号,如果是负号,妥妥的会坑。

    所以,我们还需要在” - ” 加以判断,如果-前面是操作数,则是正常-号。如果是操作符表示是一个负数,所以我们在直接添加 ”-0”

    添加成  0-   就更好的进行运算。
    这里还有一个特殊案例

    -号前面是 ) 而我们代码会识别成这是一个负数,就会变成

    所以还需要特殊判断,如果是 ) 则不进行添加 “0-”

  2.  力扣给的测试用例里会有(1231231)类似这种。如果不特殊判断,则会直接取到1,及栈顶元素。所以我们在修正完字符串后进行检查,如果没有操作符直接进行返回。



最后,我们可能会在调试期间,进行输出打印。所以在提交答案时候,请将输出打印注释,否则在最后几个测试用例里会有非常长的表达式,会导致超出运行时间,过不了。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.pswp.cn/pingmian/84715.shtml

如若内容造成侵权/违法违规/事实不符,请联系多彩编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

《AI日报 · 0613|ChatGPT支持导出、Manus免费开放、GCP全球宕机》

AI 资讯 1️⃣ OpenAI ChatGPT Canvas新增多格式导出功能 OpenAI终于为ChatGPT Canvas推出了用户期待已久的导出功能。现在,用户可以将创作内容导出为多种格式:文档类支持PDF、docx和markdown格式,代码文件则可直接保存为对应扩展名的源文件(如.py、.js、.sql等)。这一功…

C++中的零拷贝技术

一、C中零拷贝技术的核心概念 零拷贝&#xff08;Zero-copy&#xff09;是一种重要的优化技术&#xff0c;旨在减少数据在内存中的不必要复制&#xff0c;从而提高程序性能、降低内存使用并减少CPU消耗。在C中&#xff0c;零拷贝技术通过多种方式实现&#xff0c;包括引用语义…

RT_Thread内核源码分析(五)——内存管理@小堆内存管理算法

目录 1、内存堆控制 1.1 内存堆控制器 1.2 内存块节点 1.3 内存堆管理 2、内存堆初始化 2.1 初始化接口 2.2 初始化示例 2.3 源码分析 3、内存堆操作 3.1 内存块申请 3.1.1 相关接口 3.1.2 原理分析 3.1.3 示例分析 3.1.4 代码分析 3.2 内存块伸缩 3.2.1 相关…

MyBatis-Plus 混合使用 XML 和注解

mybatisplus代码生成器&#xff1a; 版本匹配是个比较麻烦的问题&#xff0c;这是我的配置&#xff1a; <dependency><groupId>com.baomidou</groupId><artifactId>mybatis-plus-boot-starter</artifactId><version>3.5.2</version>…

基于ssm的教学质量评估系统

博主介绍&#xff1a;java高级开发&#xff0c;从事互联网行业六年&#xff0c;熟悉各种主流语言&#xff0c;精通java、python、php、爬虫、web开发&#xff0c;已经做了六年的毕业设计程序开发&#xff0c;开发过上千套毕业设计程序&#xff0c;没有什么华丽的语言&#xff0…

【STM32】G030单片机开启超过8个ADC通道的方法

如图所示通道数量已经超过8个&#xff0c;按照之前博客的办法已经行不通了 CubeMX配置STM32F103C8T6多路ADC配合DMA采集_stm32f103c8t6的adc采样率-CSDN博客 这里笔者开了10个channel&#xff0c;注意切换为不完全配置&#xff0c;否则的话最多只有8个rank 开DMA&#xff0c;…

不同网络I/O模型的原理

目录 1、I/O的介绍 1.1、I/O 操作分类 1.2、I/O操作流程阶段 1.3、I/O分类 2、同步I/O 2.1、阻塞I/O 2.2、非阻塞I/O 2.3、I/O复用 2.4、信号驱动式I/O 3、异步I/O 前言 在网络I/O之中&#xff0c;I/O操作往往会涉及到两个系统对象&#xff0c;一个是用户空间调用I/O…

在正则表达式中语法 (?P<名字>内容)

&#x1f3af; 重点解释&#xff1a;?P<xxx> 是什么语法&#xff1f; 这一整段&#xff1a; (?P<xxx>...)是 Python 正则表达式中 “命名捕获组” 的语法。 咱们现在一个字一个字来解释&#xff1a; ✅ (?...) 是干啥的&#xff1f; 这是一个捕获组&#xff…

中兴B860AV1.1_MSO9280_降级后开ADB-免刷机破解教程(非刷机)

中兴B860AV1.1江苏移动-自动降级包 关于中兴b860av1.1顽固盒子降级教程终极版 将附件解压好以后&#xff0c;准备一个8G以下的U盘重新格式化为FAT32格式后&#xff0c;并插入电脑 将以下文件及文件夹一同复制到优盘主目录下&#xff08;见下图&#xff09; 全选并复制到U盘主目…

2025-06-13【视频处理】基于视频内容转场进行分割

问题&#xff1a;从网上下载的视频文件&#xff0c;是由很多个各种不同的场景视频片段合并而成。现在要求精确的把各个视频片段从大视频里分割出来。 效果如图&#xff1a;已分割出来的小片段 思考过程 难点在于检测场景变化。为什么呢&#xff1f;因为不同的视频情况各异&am…

ReentrantLock和RLock

文章目录 前言一、 ReentrantLock&#xff08;单机锁&#xff0c;Java 内置&#xff09;示例&#xff1a;方法详解 二、RLock&#xff08;分布式锁&#xff0c;Redisson 提供&#xff09;示例:方法详解 三、 对比总结:四、 如何选择&#xff1f; 前言 ReentrantLock 和 RLock 都…

thinkphp ThinkPHP3.2.3完全开发手册

惯例配置 应用设定 APP_USE_NAMESPACE > true, // 应用类库是否使用命名空间 3.2.1新增 APP_SUB_DOMAIN_DEPLOY > false, // 是否开启子域名部署 APP_SUB_DOMAIN_RULES > array(), // 子域名部署规则 APP_DOMAIN_SUFFIX > , // 域名后缀 如果是…

Python Day50 学习(仍为日志Day19的内容复习)

补充&#xff1a;梳理超参数调整流程&#xff08;逻辑&#xff09; 超参数调节的流程逻辑可以总结为以下几个步骤&#xff1a; 1. 明确目标 确定你要优化的模型和评估指标&#xff08;如准确率、F1值、AUC等&#xff09;。 2. 选择要调节的超参数 列出模型中影响较大的超参数…

公司网络变差的解决方法(固定IP地址冲突)

问题描述 最近公司网络变差&#xff0c;不知道为什么。&#xff08;别的同事反馈的&#xff0c;本人没有感觉变差&#xff0c;也是比较奇怪的现象&#xff09; 现象有视频会议变卡等。 调查过程 1.领导给网络公司打电话沟通&#xff0c;对面远程看了下&#xff0c;不是设备问…

使用Prometheus+Grafana+Alertmanager+Webhook-dingtalk搭建监控平台

一、监控平台介绍 1.监控平台简述普罗米修斯四件套,分别为Prometheus、Grafana、Alertmanager、Webhook-DingTalk。Prometheus一套开源的监控&报警&时间序列数据库的组合,由SoundCloud公司开发,广泛用于云原生环境和容器化应用的监控和性能分析。其提供了通用的数据…

UR机器人解锁关节扭矩控制:利用英伟达Isaac Lab框架,推动装配自动化的Sim2Real迁移

在工业制造领域&#xff0c;机器人装配长期依赖固定自动化模式&#xff0c;面临部署成本高、适配性差等挑战。多部件装配是制造业、汽车及航空航天等行业中的核心环节。传统装配系统通常针对特定任务设计&#xff0c;依赖大量人工工程部署&#xff0c;灵活性不足&#xff0c;难…

ABB 605系列

系列概述 ABB Relion605系列是专为配电网设计的保护继电器产品系列&#xff0c;代表了中低压电力系统保护领域的技术基准。基于ABB在电力保护领域数十年的经验&#xff0c;该系列集成了最新的数字信号处理技术和网络通信能力&#xff0c;为变电站自动化提供了完整的解决方案。…

Python|GIF 解析与构建(6):手搓 tk 录制工具

目录 Python&#xff5c;GIF 解析与构建&#xff08;6&#xff09;&#xff1a;手搓 tk 录制工具 一、工具功能概览 二、核心架构设计 1. 帧率控制模块 2. 屏幕捕获模块 3. 主应用模块 三、关键技术解析 1. 屏幕捕获技术 2. 帧率控制原理 3. 透明窗口实现 四、使用指…

在VBA中,提取word表格的文本时,通常有什么干扰符号,需要清除

标题 在VBA中&#xff0c;提取word表格的文本时&#xff0c;通常有什么干扰符号,需要清除 正文 解决问题提取word表格的文本时&#xff0c;通常有什么干扰符号,需要清除 在VBA中提取Word表格文本时&#xff0c;常见的干扰符号及其清除方法如下&#xff1a; ⚠️ 一、主要干扰符…

C++基础学习:深入理解类中的构造函数、析构函数、this指针与new关键字

前言 在C面向对象编程中&#xff0c;类是构建复杂程序的基本单元。今天&#xff0c;我们将深入探讨类中的几个核心概念&#xff1a;构造函数、析构函数、this指针以及new关键字。这些概念对于理解C对象生命周期和内存管理至关重要。 1. 构造函数 构造函数是类的一个特殊成员…