学校联系我们网站制作营销培训师

学校联系我们网站制作,营销培训师,wordpress 伪静态 效果,lnmp 安装 wordpresscsp信奥赛C标准模板库STL案例应用13 stack实践 题目描述 假设一个表达式有英文字母#xff08;小写#xff09;、运算符#xff08;、-、*、/#xff09;和左右小#xff08;圆#xff09;括号构成#xff0c;以 作为表达式的结束符。请编写一个程序检查表达式中的左…csp信奥赛C标准模板库STL案例应用13stack实践题目描述假设一个表达式有英文字母小写、运算符、-、*、/和左右小圆括号构成以作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配若匹配则输出YES否则输出NO。表达式长度小于255 255255左圆括号少于20 2020个。输入格式一行表达式。输出格式一行YES或NO。输入输出样例 1输入 12*(xy)/(1-x)输出 1YES输入输出样例 2输入 2(25x)*(a*(abb)输出 2NO说明/提示表达式长度小于255 255255左圆括号少于20 2020个。解题思路这是一个经典的括号匹配问题使用栈Stack数据结构来解决核心算法遍历表达式中的每个字符遇到左括号(就压入栈遇到右括号)就从栈中弹出一个左括号匹配规则当遇到右括号时如果栈为空没有左括号与之匹配则括号不匹配遍历结束后如果栈不为空还有左括号没被匹配则括号不匹配终止条件表达式以结尾所以只需处理之前的所有字符代码实现#includebits/stdc.husingnamespacestd;string s;// 存储输入的表达式stackintst;// 使用栈来跟踪左括号的数量这里用int存储字符的ASCII码intmain(){cins;// 读取表达式直到遇到空白符// 由于表达式以结尾我们需要找到的位置// 注意size()返回字符串长度索引从0开始// 例如字符串abc的长度为4索引为0,1,2,3intns.size()-2;// 计算需要处理的字符的最大索引的前一个字符// 遍历所有有效字符即之前的所有字符for(inti0;in;i){if(s[i](){// 遇到左括号压入栈中st.push(s[i]);}elseif(s[i])){// 遇到右括号if(st.empty()){// 栈为空说明没有匹配的左括号coutNO;return0;// 提前结束程序}else{st.pop();// 弹出栈顶的左括号}}}// 检查栈是否为空若空则所有括号匹配否则不匹配if(st.empty()){coutYES;}else{coutNO;}return0;}功能分析输入处理使用cin s读取表达式字符串读取会持续直到遇到空白符表达式以字符结束这是一个终止标志核心逻辑栈的使用利用栈的先进后出LIFO特性确保每个右括号都能匹配最近未匹配的左括号边界条件检查遇到右括号时栈为空 → 右括号多余 → 输出NO遍历结束后栈不为空 → 左括号多余 → 输出NO所有括号都正确匹配 → 栈最终为空 → 输出YES时间复杂度时间复杂度O(n)其中 n 是表达式长度255每个字符最多被处理一次空间复杂度O(k)其中 k 是左括号数量20栈的最大深度不超过左括号数量测试用例验证测试用例12*(xy)/(1-x)遍历过程遇到’(‘压栈遇到’)弹栈最终栈为空输出YES测试用例2(25x)*(a*(abb)遍历过程遇到多个’(‘压栈遇到’)弹栈但最终栈中还有未匹配的左括号输出NO边界测试空表达式→ 栈为空 →YES只有左括号((( → 栈不为空 →NO只有右括号))) → 遇到右括号时栈为空 →NO交替括号()()() → 每次匹配成功 →YES嵌套括号((())) → 完全匹配 →YES各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}