Is Valid Parentheses

发表于 | 分类于

Valid Parentheses(括号构成的字符串有效)

题目描述：

给定一个字符串由括号构成；判断其是否有效。

例子：

解题思路：

对于这种题目；主要利用栈的数据结构来判断。我们可以将碰到左括号的字符全部入栈；然后一旦碰到右括号；就从栈顶弹出字符，并且判断这两个字符是否能够构成合法的字符串直到栈为空。需要注意的是，假设字符前部的字符都有效，但是末尾是一个左括号，这样需要在函数末尾判断当前栈是否为空，不为空的情况也是不合法的字符串。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    bool isValid(string s) {
        if (s.size() <= 1) return false;
        stack<char> stk;//定义栈用于保存数据
        stk.push(s[0]);//先将首字符入栈
        int cur = 1; //记录当前遍历字符的位置
        while(cur < s.size()){
            if (s[cur] == '(' || s[cur] == '{' || s[cur] == '['){
                stk.push(s[cur]);
                cur++;
                //左括号入栈
            }else{
                if (stk.empty()||(s[cur] == ')' && stk.top() != '(') || (s[cur] == ']' && stk.top() != '[') || (s[cur] == '}' && stk.top() != '{'))//右括号判断三种不同的情况和空栈的情况
                    return false;
                else{
                    cur++;
                    stk.pop();
                }
            }
        }
        if (stk.empty()) return true;
        //需要在最后判断是否是空栈的情况
        else return false;
        
    }
};