台州网站制作咨询薇,专题网站模板,个人网站搭建软件,产品营销推广一、题目链接
https://leetcode.cn/problems/valid-parentheses/submissions/538110206 二、题目思路
利用栈的性质#xff0c;后进先出
1.依次读取字符串#xff0c;判断是否为左括号#xff0c;如果是#xff0c;就将其入栈。
2.如果读取的不是左括号#xff0c;就说…一、题目链接
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;
}
