题目链接
https://leetcode-cn.com/problems/valid-parentheses/
一、题目
给定一个只包括 ‘(’,’)’,’{’,’}’,’[’,’]’ 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: “()”
输出: true
示例 2:
输入: “()[]{}”
输出: true
示例 3:
输入: “(]”
输出: false
示例 4:
输入: “([)]”
输出: false
示例 5:
输入: “{[]}”
输出: true
二、分析与代码
1.分析
先判断是否为左括号,然后用新定义的字符数组存对应的右括号,当遍历到右括号时,若不能与新定义的字符数组中存的右括号相匹配或者新定义的字符数组没有存右括号,则判为false,若匹配成功,则将新定义的字符数组长度减一。最后,当新定义的字符数组的长度仍为初始长度时即为true。
2.代码
代码如下(示例):
bool isValid(char * s){
int len = strlen(s);
int top=-1;
char stack[len+1];
for(int i = 0;i<len;i++){
if(s[i]=='(') stack[++top]=')';
else if(s[i]=='[') stack[++top]=']';
else if(s[i]=='{') stack[++top]='}';
else if(top==-1||stack[top]!=s[i]) return false;//不是左括号那就只有右括号了,栈空或不匹配则非法
else
top--;
}
bool t=false;
if(top==-1)
t=true;
return t;
}