LeetCode20 有效的括号
https://leetcode.cn/problems/valid-parentheses/submissions/
流程为遍历每一个字符并判断是否为左括号还是有括号,若为左括号则放入栈中,若为有括号则判断栈是否为空,若不为空则检查当前字符是否匹配栈顶元素,若匹配则栈顶元素出栈,若不匹配则返回false,最终遍历完成后若栈不为空则返回false,若栈为空返回true
class Solution { public: bool isValid(string s) { int a=0; int b=0; int c=0; stack<char>st; for(int i=0;i<s.size();i++){ if(s[i]=='('||s[i]=='['||s[i]=='{')st.push(s[i]); else if((s[i]==')')||(s[i]==']')||(s[i]=='}')){ if(st.empty())return 0; else if((s[i]==')'&&st.top()=='(')||(s[i]==']'&&st.top()=='[')||(s[i]=='}'&&st.top()=='{')){ st.pop(); } else return 0; } }return st.empty(); } };
下面是另一种题解,遍历字符串,判断各种情况,当字符为左括号时,栈中放入相应的右括号,接下来进行匹配,先进判断栈是否为空,若为空则直接返回false,再进行匹配,若不匹配则也是直接返回false,则剩余情况是匹配成功进行出栈操作,最后遍历完成后检查栈是否为空。注意可以先进行剪枝操作,若字符串size为奇数则返回false。
class Solution { public: bool isValid(string s) { stack<char>st; if(s.size()%2!=0)return 0; for(int i=0;i<s.size();i++){ if(s[i]=='(')st.push(')'); else if(s[i]=='[')st.push(']'); else if(s[i]=='{')st.push('}'); else if(st.empty()||st.top()!=s[i])return 0; else st.pop(); } return st.empty(); } };
1047. 删除字符串中的所有相邻重复项
https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/
class Solution { public: string removeDuplicates(string s) { stack<char>st; st.push(s[0]); for (int i = 1; i < s.size(); ++i) { if(st.empty())st.push(s[i]); else if(s[i]==st.top())st.pop(); else st.push(s[i]); } s.clear(); while(!st.empty()){ s+=st.top(); st.pop(); } reverse(s.begin(),s.end()); return s; } };
150. 逆波兰表达式求值
https://leetcode.cn/problems/evaluate-reverse-polish-notation/
注意第一个if需要判断运算符号,不能用于判断是否为数字,因为运算符号在string中也会被看成数字。
class Solution { public: int evalRPN(vector<string>& tokens) { stack<long long>st; for(int i=0;i<tokens.size();i++){ if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"|| tokens[i]=="/"){ long long num1,num2; num1=st.top(); st.pop(); num2=st.top(); st.pop(); if(tokens[i]=="+"){ st.push(num1+num2); } else if(tokens[i]=="-"){ st.push(num2-num1); } else if(tokens[i]=="*"){ st.push( num1*num2); } else if(tokens[i]=="/"){ st.push(num2/num1); } } else st.push(stoll(tokens[i])); } int result=st.top(); st.pop(); return result; } };
标签:1047,string,匹配,int,随想录,st,括号,day10,false From: https://www.cnblogs.com/zhishikele/p/17033110.html