20. 有效的括号 - 力扣LeetCode20. 有效的括号 - 给定一个只包括 (){}[] 的字符串 s 判断字符串是否有效。有效字符串需满足 1. 左括号必须用相同类型的右括号闭合。 2. 左括号必须以正确的顺序闭合。 3. 每个右括号都有一个对应的相同类型的左括号。 示例 1输入s ()输出true示例 2输入s ()[]{}输出true示例 3输入s (]输出false示例 4输入s ([])输出true示例 5输入s ([)]输出false 提示 * 1 s.length 104 * s 仅由括号 ()[]{} 组成https://leetcode.cn/problems/valid-parentheses/1.题目描述题目给定一个只包括(){}[]的字符串s判断字符串是否有效。 有效字符串需要满足左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。思路分析括号匹配是栈的经典应用场景。 栈的特点后进先出。最后出现的左括号要最先被对应的右括号抵消。算法流程遍历字符串每一个字符遇到左括号( { [直接压入栈中保存遇到右括号) } ]如果栈为空没有左括号与之匹配直接返回 false判断栈顶的左括号和当前右括号是否配对不匹配直接返回 false匹配成功弹出栈顶元素循环结束栈必须为空。如果栈里面还有残留左括号说明括号没有闭合返回 false。class Solution { public: bool isValid(string s) { stackchar st; for(auto e:s) { if(e[||e{||e() st.push(e); else { if(st.empty()) return false; if((st.top()!(e))|| (st.top()![e])|| (st.top()!{e})) return false; st.pop(); } } return st.empty(); } };946. 验证栈序列 - 力扣LeetCode946. 验证栈序列 - 给定 pushed 和 popped 两个序列每个序列中的 值都不重复只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时返回 true否则返回 false 。 示例 1输入pushed [1,2,3,4,5], popped [4,5,3,2,1]输出true解释我们可以按以下顺序执行push(1), push(2), push(3), push(4), pop() - 4,push(5), pop() - 5, pop() - 3, pop() - 2, pop() - 1示例 2输入pushed [1,2,3,4,5], popped [4,3,5,1,2]输出false解释1 不能在 2 之前弹出。 提示 * 1 pushed.length 1000 * 0 pushed[i] 1000 * pushed 的所有元素 互不相同 * popped.length pushed.length * popped 是 pushed 的一个排列https://leetcode.cn/problems/validate-stack-sequences/2.题目描述给定两个整数数组pushed和popped其中pushed是元素入栈顺序popped是元素出栈顺序。请你判断该出栈序列是否可以由合法的栈操作得到。栈合法规则入栈必须严格按照pushed顺序出栈只能弹出当前栈顶入栈、出栈可以穿插进行解题核心思路这道题是栈最经典的模拟贪心题核心口诀按顺序入栈能弹出就立刻弹出完整流程遍历pushed逐个将元素压入模拟栈每压入一个元素后立刻检查栈不为空 amp;amp; 栈顶 当前待出栈元素满足条件就持续弹出并向后移动popped下标遍历结束后栈为空则序列合法否则非法class Solution { public: bool validateStackSequences(vectorint pushed, vectorint popped) { stackint st; int npushed.size(); for(int i0,j0;in;i) { st.push(pushed[i]); while(!st.empty()st.top()popped[j]) { st.pop(); j; } } return st.empty(); } };LCR 036. 逆波兰表达式求值 - 力扣LeetCodeLCR 036. 逆波兰表达式求值 - 根据 逆波兰表示法 [https://baike.baidu.com/item/%E9%80%86%E6%B3%A2%E5%85%B0%E5%BC%8F/128437]求该后缀表达式的计算结果。有效的算符包括 、-、*、/ 。每个运算对象可以是整数也可以是另一个逆波兰表达式。 说明 * 整数除法只保留整数部分。 * 给定逆波兰表达式总是有效的。换句话说表达式总会得出有效数值且不存在除数为 0 的情况。 示例 1输入tokens [2,1,,3,*]输出9解释该算式转化为常见的中缀算术表达式为((2 1) * 3) 9示例 2输入tokens [4,13,5,/,]输出6解释该算式转化为常见的中缀算术表达式为(4 (13 / 5)) 6示例 3输入tokens [10,6,9,3,,-11,*,/,*,17,,5,]输出22解释该算式转化为常见的中缀算术表达式为 ((10 * (6 / ((9 3) * -11))) 17) 5 ((10 * (6 / (12 * -11))) 17) 5 ((10 * (6 / -132)) 17) 5 ((10 * 0) 17) 5 (0 17) 5 17 5 22 提示 * 1 tokens.length 104 * tokens[i] 要么是一个算符、-、* 或 /要么是一个在范围 [-200, 200] 内的整数 逆波兰表达式逆波兰表达式是一种后缀表达式所谓后缀就是指算符写在后面。 * 平常使用的算式则是一种中缀表达式如 ( 1 2 ) * ( 3 4 ) 。 * 该算式的逆波兰表达式写法为 ( ( 1 2 ) ( 3 4 ) * ) 。逆波兰表达式主要有以下两个优点 * 去掉括号后表达式无歧义上式即便写成 1 2 3 4 * 也可以依据次序计算出正确结果。 * 适合用栈操作运算遇到数字则入栈遇到算符则取出栈顶两个数字进行计算并将结果压入栈中。 注意本题与主站 150 题相同 https://leetcode.cn/problems/evaluate-reverse-polish-notation/ [https://leetcode.cn/problems/evaluate-reverse-polish-notation/]https://leetcode.cn/problems/8Zf90G/3.题目描述给你一个字符串数组表示一个逆波兰表达式计算该表达式的值。有效的算符包括、-、*、/。每个运算对象可以是整数也可以是另一个逆波兰表达式。逆波兰表达式后缀表达式运算符放在数字后面。 示例[2,1,,3,*]等价于(21)*3 9注意整数除法只保留整数部分。算法思路栈逆波兰表达式的经典解法就是栈遍历每一个 token如果是数字直接压入栈如果是运算符先弹出栈顶元素作为右操作数 right再弹出栈顶元素作为左操作数 left执行运算把运算结果重新压回栈中遍历结束栈里面剩下唯一元素就是答案class Solution { public: int evalRPN(vectorstring tokens) { stackint st; for (auto e : tokens) { if (e ! e ! - e ! * e ! /) { st.push(stoi(e)); } else { string op e; int right st.top(); st.pop(); int left st.top(); st.pop(); int ret 0; switch (e[0]) { case : ret left right; break; case -: ret left - right; break; case *: ret left * right; break; case /: ret left / right; break; } st.push(ret); } } return st.top(); } };