有效的括号（oj题）

一、题目链接

http://leetcode.cn/problems/valid-parentheses/submissions/538110206

二、题目思路

利用栈的性质，后进先出

1.依次读取字符串，判断是否为左括号，如果是，就将其入栈。

2.如果读取的不是左括号，就说明是右括号了。这时要在栈不为空的情况下，去取栈的栈顶元素，判断栈顶元素是否和此时读取的右括号之间是否配对。

3.如果配对，就让栈顶的左括号出栈

4.重复循环，直至字符串读取完，或者在读完之前，就直接就判断出了匹配错误的结果

6.最后要判断是否栈是否为空栈，如果是空栈，就说明所有扩号是匹配成功的，就返回true 

如果不为空，就返回false

注意：如果字符串都是右括号，这样就没有元素入栈，最后判断栈为空，得到了错误的结果

所以:

要在取栈顶元素判断之前，要判断栈是否为空，为空，就说明第一个字符是右括号，就直接代表匹配失败，直接返回false

三、题解代码

typedef char StackDataType;
typedef struct stack {
    StackDataType* data;
    int size;
    int capacity;
} Stack;
void stackInit(Stack* pst);
void stackDestroy(Stack* pst);
void checkCapacity(Stack* pst);
int stackIsEmpty(Stack* pst);
void stackFush(Stack* pst, StackDataType data);
void stackPop(Stack* pst);
StackDataType stackTop(Stack* pst);
int stackSize(Stack* pst);
void stackInit(Stack* pst) {
    pst->data = NULL;
    pst->size = 0;
    pst->capacity = 0;
}
void stackDestroy(Stack* pst) {
    free(pst->data);
    pst->data = NULL;
    pst->capacity = 0;
    pst->size = 0;
}
void checkCapacity(Stack* pst) {
    if (pst->size == pst->capacity) {
       int newcapacity = pst->capacity == 0 ? 4 : 2 * pst->capacity;
        StackDataType* p = (StackDataType*)realloc(pst->data,
            sizeof(StackDataType) * newcapacity);
        if (p == NULL) {
            perror("realloc fail");
            return;
        }
        pst->data = p;
        pst->capacity = newcapacity;
    }
}
int stackIsEmpty(Stack* pst) {
    if (pst->size == 0)
        return 1;
    else
        return 0;
}
void stackFush(Stack* pst, StackDataType data) {
    checkCapacity(pst);
    pst->data[pst->size] = data;
    pst->size++;
}
void stackPop(Stack* pst) {
    pst->size--;
}
StackDataType stackTop(Stack* pst) {
    return pst->data[pst->size - 1];
}
int stackSize(Stack* pst) {
    return pst->size;
}
bool isValid(char* s) {
    // write code here
    Stack sta;
    stackInit(&sta);
    while (*s) {
        if (*s == '(' || *s == '[' || *s == '{')//读入左括号
            stackFush(&sta, *s);//左括号入栈
        else {
            
        //     //如果第一个是右括号，进不了栈，说明栈为空，直接返回false
            if(stackIsEmpty(&sta))
               return false;

            if (!stackIsEmpty(&sta)) {
                StackDataType temp = stackTop(&sta);//取栈顶元素

                //如果栈顶元素无法与之匹配，就说明失败了
                if (*s == ')' && temp != '(')
                    return false;
                else if (*s == ']' && temp != '[')
                    return false;
                else if (*s == '}' && temp != '{')
                    return false;
                else
                    stackPop(&sta);  //出栈，更新栈顶元素
            }
        } 
        s++;//移动字符指针
    }
    if (stackIsEmpty(&sta))
        return true;  //如果最后栈为空，就说明成功
    else
        return false;
}