网站建设对称对比型工商企业网

一、题目链接

https://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;elsereturn 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 hereStack sta;stackInit(&sta);while (*s) {if (*s == '(' || *s == '[' || *s == '{')//读入左括号stackFush(&sta, *s);//左括号入栈else {//     //如果第一个是右括号，进不了栈，说明栈为空，直接返回falseif(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;elsestackPop(&sta);  //出栈，更新栈顶元素}} s++;//移动字符指针}if (stackIsEmpty(&sta))return true;  //如果最后栈为空，就说明成功elsereturn false;
}