算法——逆波兰式

news/2024/5/20 21:19:20

http://t.csdnimg.cn/Wg8vu

逆波兰式思路:

对于每个元素,它检查是否是一个操作符(“+”、“-”、“*” 或 “/”)。如果是,它就从栈中弹出两个元素,执行相应的操作,然后将结果推回到栈中。如果元素是一个数字,它就将其推到栈中。

在处理所有元素后,栈顶的元素就是表达式的结果。

进阶:. - 力扣(LeetCode)

给定一个经过编码的字符串,返回它解码后的字符串。

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。

思路:

数字存放在数字栈,字符串存放在字符串栈,遇到右括号时候弹出一个数字栈,字母栈弹到左括号为止。与逆波兰式思路类似。

class Solution {
public:string decodeString(string s) {stack<int> num_stk;//数字栈stack<string> str_stk;//字符串栈string str;//当前正在累积的字符串for(int i=0;i<s.size();++i){if(isdigit(s[i])){//遇到数字int n=s[i]-'0';while(isdigit(s[++i])){//数字可能有多位n=10*n+s[i]-'0';}num_stk.push(n);//加入数字栈--i;//往后退一步(for循环处有自增操作)}else if(s[i]=='['){//遇到左括号str_stk.push(str);//将当前累积的字符串入栈str="";//开始记录新的一段字符串}else if(s[i]==']'){//遇到右括号string tmp;//将当前字符串按数字栈栈顶元素为倍数进行扩展for(int i=0;i<num_stk.top();++i){tmp+=str;}str=tmp;num_stk.pop();//数字栈栈顶元素弹出//字符串栈栈顶元素弹出来并与当前字符串拼接,作为新的当前正在累积的字符串str=str_stk.top()+str;str_stk.pop();}else{str+=s[i];//当前字符串继续累积}}return str;}
};


https://www.xjx100.cn/news/3366017.html

相关文章

day 1 将go基础知识复习一下

本文章主要是写自己在做这个项目时候遇到的一些困难&#xff0c;如果都是做这个项目的&#xff08;后端&#xff09;&#xff0c;可以看看 这个是项目网址 gin-vue-admin : https://github.com/flipped-aurora/gin-vue-admin 在此表示对大神奇淼的敬佩 首先&#xff0c;我们…

hibernate OID映射对象标识符

OID映射对象标识符 OID存在的意义 关系型数据库通过主键来区分同一张表的不同数据&#xff0c;java语言使用内存地址来区分同一类的不同对象&#xff0c;hibernate则使用OID来同一两者之间的矛盾&#xff0c;在运行时&#xff0c;hibernate通过OID来维持java对象和数据库表中记…

解决Toad for Oracle显示乱中文码问题

更多ruoyi-nbcio功能请看演示系统 gitee源代码地址 前后端代码&#xff1a; https://gitee.com/nbacheng/ruoyi-nbcio 演示地址&#xff1a;RuoYi-Nbcio后台管理系统 http://122.227.135.243:9666/ 更多nbcio-boot功能请看演示系统 gitee源代码地址 后端代码&#xff1a…

debian的使用笔记

1. XP风格任务栏 安装 debian-live-12.5.0-amd64-xfce.iso 后&#xff0c;把下面的任务栏删除&#xff0c;把上面的任务栏移到下面&#xff0c;然后设置如下选项 2. 命令自动补全 sudo apt install bash-completion 3. 找不到命令 sudo apt install command-not-found sudo…

WebKit内核架构深度解析:核心技术与工作机制

WebKit是一种开源的网页浏览器引擎&#xff0c;广泛应用于苹果Safari、谷歌Chrome&#xff08;早期版本&#xff09;以及其他诸多第三方浏览器中。其卓越的性能和跨平台特性使之在全球范围内具有广泛的影响力。本文将对WebKit的核心结构进行详尽的介绍&#xff0c;以便于读者深…

OSCP系列靶场-Esay-SunsetDecoy

总结 getwebshell : 发现zip文件 → zip存在密码 → john爆破zip密码 → 发现passwd与shadow文件 → 爆破shadow密码 → ssh登录 提 权 思 路 : 发现后台运行程序 → 上传pspy64查看 → 发现chkrootkit → chkrootkit提权 准备工作 启动VPN 获取攻击机IP → 192.168.45.194 …

C语言运算符和表达式——赋值中的自动类型转换(精度损失问题)

目录 自动类型转换 数值精度损失 自动类型转换 在不同类型数据间赋值时&#xff0c;会发生自动类型转换 *取值范围大的类型 → 取值范围小的类型&#xff0c;通常是不安全的 *数值溢出&#xff08;Overflow&#xff09; *反之&#xff0c;一定都是安全的吗&#xff1f;…

idea端口占用

报错&#xff1a;Verify the connector‘s configuration, identify and stop any process that‘s listening on port XXXX 翻译&#xff1a; 原因&#xff1a; 解决&#xff1a; 一、重启大法 二、手动关闭 启动spring项目是控制台报错&#xff0c;详细信息如下&#xff…