leetcode 题解 || Valid Parentheses 问题

时间:2025-03-16 00:04:07

problem:

Given a string containing just the characters '(', ')', '{', '}', '[' and ']',
determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are
all valid but "(]" and "([)]" are not.

输入一个包括上述六种括号的字符串,检查括号是否能成功匹配

thinking:

(1)这是简化的表达式解析,匹配的方法是:

从低位到高位遍历字符串。出现左側括号('('、’[‘、’{‘)则入栈,出现右側括号('('\、'['、'{')则从栈中取出一个符号与之配对。

当出现:要从栈取字符时而栈为空、字符串遍历完而栈不为空   这 两种情况时,匹配失败。

(2)string s="abcd",最低位是a。别犯低级错误!

!!!

code:

class Solution {
protected:
bool check(char a,char b)
{
cout<<"a: "<<a<<"b: "<<b<<endl;
bool flag = false;
if(a=='(')
{
if(b==')')
flag=true;
}
else if(a=='[')
{
if(b==']')
flag=true;
}
else
{
if(b=='}')
flag=true;
}
return flag; }
public:
bool isValid(string s) {
string str=s;
bool result=true;
int length = str.size();
stack<char> mystack;
for(int i=0;i<length;i++)
{
cout<<"i="<<i<<"s[i]="<<str.at(i)<<endl;
if(str.at(i)=='('||str.at(i)=='[' || str.at(i)=='{')
{
cout<<"this"<<endl;
mystack.push(str.at(i));
}
else
{
cout<<" here"<<endl;
if(mystack.empty())
return false;
char tmp = mystack.top();
mystack.pop();
result=check(tmp,str.at(i));
if(!result)
return false;
}//else
}//for
if(mystack.size()!=0)
return false;
else
return true; }
private:
string str;
};