csp信奥赛C++标准模板库STL案例应用13-编程阁

csp信奥赛C++标准模板库STL案例应用13

stack实践

题目描述

假设一个表达式有英文字母（小写）、运算符（+、-、*、/）和左右小（圆）括号构成，以@作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则输出YES；否则输出NO。表达式长度小于255 255255，左圆括号少于20 2020个。

输入格式

一行：表达式。

输出格式

一行：YES或NO。

输入输出样例 1

输入 1

2*(x+y)/(1-x)@

输出 1

YES

输入输出样例 2

输入 2

(25+x)*(a*(a+b+b)@

输出 2

NO

说明/提示

表达式长度小于255 255255，左圆括号少于20 2020个。

解题思路

这是一个经典的括号匹配问题，使用栈（Stack）数据结构来解决：

核心算法：遍历表达式中的每个字符，遇到左括号'('就压入栈，遇到右括号')'就从栈中弹出一个左括号
匹配规则：
- 当遇到右括号时，如果栈为空（没有左括号与之匹配），则括号不匹配
- 遍历结束后，如果栈不为空（还有左括号没被匹配），则括号不匹配
终止条件：表达式以@结尾，所以只需处理@之前的所有字符

代码实现

#include<bits/stdc++.h>usingnamespacestd;string s;// 存储输入的表达式stack<int>st;// 使用栈来跟踪左括号的数量（这里用int存储字符的ASCII码）intmain(){cin>>s;// 读取表达式，直到遇到空白符// 由于表达式以@结尾，我们需要找到@的位置// 注意：size()返回字符串长度，索引从0开始// 例如：字符串"abc@"的长度为4，索引为0,1,2,3intn=s.size()-2;// 计算需要处理的字符的最大索引（@的前一个字符）// 遍历所有有效字符（即@之前的所有字符）for(inti=0;i<=n;i++){if(s[i]=='('){// 遇到左括号，压入栈中st.push(s[i]);}elseif(s[i]==')'){// 遇到右括号if(st.empty()){// 栈为空，说明没有匹配的左括号cout<<"NO";return0;// 提前结束程序}else{st.pop();// 弹出栈顶的左括号}}}// 检查栈是否为空，若空则所有括号匹配，否则不匹配if(st.empty()){cout<<"YES";}else{cout<<"NO";}return0;}

功能分析

输入处理

使用cin >> s读取表达式字符串，读取会持续直到遇到空白符
表达式以@字符结束，这是一个终止标志

核心逻辑

栈的使用：利用栈的先进后出（LIFO）特性，确保每个右括号都能匹配最近未匹配的左括号
边界条件检查：
- 遇到右括号时栈为空 → 右括号多余 → 输出NO
- 遍历结束后栈不为空 → 左括号多余 → 输出NO
- 所有括号都正确匹配 → 栈最终为空 → 输出YES

时间复杂度

时间复杂度：O(n)，其中 n 是表达式长度（<255），每个字符最多被处理一次
空间复杂度：O(k)，其中 k 是左括号数量（<20），栈的最大深度不超过左括号数量

测试用例验证

测试用例1：`2*(x+y)/(1-x)@`

遍历过程：遇到’(‘压栈，遇到’)'弹栈，最终栈为空
输出：YES

测试用例2：`(25+x)(a(a+b+b)@`

遍历过程：遇到多个’(‘压栈，遇到’)'弹栈，但最终栈中还有未匹配的左括号
输出：NO

边界测试

空表达式：@→ 栈为空 →YES
只有左括号：((( @→ 栈不为空 →NO
只有右括号：))) @→ 遇到右括号时栈为空 →NO
交替括号：()()() @→ 每次匹配成功 →YES
嵌套括号：((())) @→ 完全匹配 →YES

各种学习资料，助力大家一站式学习和提升！！！

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}

一、CSP信奥赛C++通关学习视频课：
- C++语法基础
- C++语法进阶
- C++算法
- C++数据结构
- CSP信奥赛数学
- CSP信奥赛STL
二、CSP信奥赛C++竞赛拿奖视频课：
- 信奥赛csp-j初赛高频考点解析
- CSP信奥赛C++复赛集训课（12大高频考点专题集训）
三、考级、竞赛刷题题单及题解：
- GESP C++考级真题题解
- CSP信奥赛C++初赛及复赛高频考点真题解析
- CSP信奥赛C++一等奖通关刷题题单及题解

详细内容：

1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：

https://edu.csdn.net/lecturer/7901 点击跳转

2、CSP信奥赛C++竞赛拿奖视频课：

https://edu.csdn.net/course/detail/40437 点击跳转

3、csp信奥赛冲刺一等奖有效刷题题解：

CSP信奥赛C++初赛及复赛高频考点真题解析（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

2025 csp-j 复赛真题及答案解析（最新更新）
2025 csp-x(山东) 复赛真题及答案解析（最新更新）
2025 csp-x(河南) 复赛真题及答案解析（最新更新）
2025 csp-x(辽宁) 复赛真题及答案解析（最新更新）
2025 csp-x(江西) 复赛真题及答案解析（最新更新）
2025 csp-x(广西) 复赛真题及答案解析（最新更新）
2020 ~ 2024 csp 复赛真题题单及题解
2019 ~ 2022 csp-j 初赛高频考点真题分类解析
2021 ~ 2024 csp-s 初赛高频考点解析
2023 ~ 2024 csp-x (山东)初赛真题及答案解析
2024 csp-j 初赛真题及答案解析
2025 csp-j 初赛真题及答案解析（最新更新）
2025 csp-s 初赛真题及答案解析（最新更新）
2025 csp-x (山东)初赛真题及答案解析(最新更新)
2025 csp-x (江西)初赛真题及答案解析(最新更新)
2025 csp-x (辽宁)初赛真题及答案解析(最新更新)

CSP信奥赛C++一等奖通关刷题题单及题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转

129 道刷题练习和详细题解，涉及：模拟算法、数学思维、二分算法、前缀和、差分、深搜、广搜、DP专题、树和图

4、GESP C++考级真题题解：

GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转

GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转

· 文末祝福 ·

#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}

csp信奥赛C++标准模板库STL案例应用13