[LeetCode] 20.Valid Parentheses
【题目】
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.
【分析】
这是栈的应用。
注意一下情况:
(1)[]) 左右括号数目不匹配,左括号少,右括号多,因此出栈时需判断栈是否空if(!brackets.empty())
(2) (( 左右括号数目不匹配,左括号多,右括号少,因此遍历完后 需判断栈是否空
【代码】
/*********************************
* 日期:2015-01-23
* 作者:SJF0115
* 题目: 20.Valid Parentheses
* 网址:https://oj.leetcode.com/problems/valid-parentheses/
* 结果:AC
* 来源:LeetCode
* 博客:
**********************************/
#include <iostream>
#include <stack>
using namespace std;
class Solution {
public:
bool isValid(string s) {
bool result = false;
int len = s.length();
if(len <= 1){
return result;
}//if
stack<char> brackets;
for(int i = 0;i < len;++i){
// '(' '[' '{' 进栈
if(s[i] == '(' || s[i] == '[' || s[i] == '{'){
brackets.push(s[i]);
continue;
}//if
// 否则出栈,比较
if(!brackets.empty()){
char bracket = brackets.top();
brackets.pop();
if(s[i] == ')' && bracket != '('){
return false;
}//if
if(s[i] == ']' && bracket != '['){
return false;
}//if
if(s[i] == '}' && bracket != '{'){
return false;
}//if
}//if
// 数目不匹配
else{
return false;
}
}//for
if(!brackets.empty()){
return false;
}//if
return true;
}
};
int main(){
Solution solution;
string s = "((";
bool result = solution.isValid(s);
// 输出
cout<<result<<endl;
return 0;
}