18-有效的括号（栈）

有效的括号

• 1. 题目
• 2.思路
• 3. 代码实现
• • 3.1 C++实现
  • 3.2 C实现

1. 题目

LeetCode题目链接

2.思路

由于栈结构的特殊性，非常适合做对称匹配类的题目。

首先要弄清楚，字符串里的括号不匹配有几种情况。

建议要写代码之前要分析好有哪几种不匹配的情况，如果不动手之前分析好，写出的代码也会有很多问题。

先来分析一下 这里有三种不匹配的情况，

1）第一种情况，字符串里左方向的括号多余了 ，所以不匹配。

2）第二种情况，括号没有多余，但是 括号的类型没有匹配上。

3）第三种情况，字符串里右方向的括号多余了，所以不匹配。

第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false

第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。

所以return false

第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false

那么什么时候说明左括号和右括号全都匹配了呢，就是字符串遍历完之后，栈是空的，就说明全都匹配了。

分析完之后，代码其实就比较好写了，

3. 代码实现 3.1 C++实现

但还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！

class Solution {
public:
    bool isValid(string s) {
        stack<int> st;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') st.push(')');
            else if (s[i] == '{') st.push('}');
            else if (s[i] == '[') st.push(']');
            // 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
            // 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。

所以return false
            else if (st.empty() || st.top() != s[i]) return false;
            else st.pop(); // st.top() 与 s[i]相等，栈d出元素
        }
        // 第一种情况：此时我们已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false，否则就return true
        return st.empty();
    }
};

3.2 C实现

//辅助函数：判断栈顶元素与输入的括号是否为一对。

若不是，则返回False
int notMatch(char par, char* stack, int stackTop) {
    switch(par) {
        case ']':
            return stack[stackTop - 1] != '[';
        case ')':
            return stack[stackTop - 1] != '(';
        case '}':
            return stack[stackTop - 1] != '{';
    }
    return 0;
}

bool isValid(char * s){
    int strLen = strlen(s);
    //开辟栈空间
    char stack[5000];
    int stackTop = 0;

    //遍历字符串
    int i;
    for(i = 0; i < strLen; i++) {
        //取出当前下标所对应字符
        char tempChar = s[i];
        //若当前字符为左括号，则入栈
        if(tempChar == '(' || tempChar == '[' || tempChar == '{')
            stack[stackTop++] = tempChar;
        //若当前字符为右括号，且栈中无元素或右括号与栈顶元素不符，返回False
        else if(stackTop == 0 || notMatch(tempChar, stack, stackTop))
            return 0;
        //当前字符与栈顶元素为一对括号，将栈顶元素出栈
        else
            stackTop--;
    }
    //若栈中有元素，返回False。

若没有元素（stackTop为0），返回True
    return !stackTop;
}