[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;
}