给定一个只包括?'('
,')'
,'{'
,'}'
,'['
,']'
?的字符串?s
?,判断字符串是否有效。
有效字符串需满足:
示例 1:
输入:s = "()" 输出:true
示例?2:
输入:s = "()[]{}" 输出:true
示例?3:
输入:s = "(]" 输出:false
提示:
1 <= s.length <= 104
s
?仅由括号?'()[]{}'
?组成栈(后进先出)?
?这是由于创建栈错误而引发的报错。
初始化:
void StackInit(ST* ps)
{
assert(ps);
ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
if (ps->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
ps->capacity = 4;
ps->top = 0;
}
创建栈:
ST st;
ps是一个指针变量接收的是st的地址。
使用c语言实现:
typedef char STDataType;
typedef struct Stack {
STDataType* a;
int top;
int capacity;
}ST;
void StackInit(ST* ps);
void StackDestory(ST* ps);
// //入栈
void StackPush(ST* ps, STDataType x);
// //出栈
void StackPop(ST* ps);
// //返回栈顶元素
STDataType StackTop(ST* ps);
int StackSize(ST* ps);
bool StackEmpty(ST* ps);
void StackInit(ST* ps)
{
assert(ps);
ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
if (ps->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
ps->capacity = 4;
ps->top = 0;
}
void StackDestory(ST* ps) {
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
//入栈
void StackPush(ST* ps, STDataType x) {
assert(ps);
if (ps->top == ps->capacity) {
STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
if (tmp == NULL) {
printf("realloc fail\n");
exit(-1);
}
else {
ps->a = tmp;
ps->capacity *= 2;
}
}
ps->a[ps->top] = x;
ps->top++;
}
//出栈
void StackPop(ST* ps) {
assert(ps);
//防止栈空,栈空时应终止程序
assert(ps->top > 0);
ps->top--;
}
//返回栈顶元素
STDataType StackTop(ST* ps) {
assert(ps);
//防止栈空,栈空时应终止程序
assert(ps->top > 0);
return ps->a[ps->top - 1];
}
//返回栈中的数据个数
int StackSize(ST* ps) {
assert(ps);
return ps->top;
}
bool StackEmpty(ST* ps) {
assert(ps);
return ps->top == 0;
}
bool isValid(char* s) {
ST st;
StackInit(&st);
while(*s ){
switch(*s){
case '[':
case'{':
case'(':
{
StackPush(&st,*s);
++s;
break;
}
case']':
case'}':
case')':
{
if(StackEmpty(&st)){
StackDestory(&st);
return false;
}
char top=StackTop(&st);
StackPop(&st);
if(*s==']'&&top!='['||
*s=='}'&&top!='{'||
*s==')'&&top!='('){
StackDestory(&st);
return false;
}
else{
++s;
}
break;
}
default:
break;
}
}
bool ret =StackEmpty(&st);
StackDestory(&st);
return ret;
}
注意栈的销毁,否则容易内存泄漏。
最优写法(c++):
class Solution {
public:
bool isValid(string s) {
stack<int> st;
for (int i = 0; i < s.size(); i++) {
if (s[i] == '(' || s[i] == '[' || s[i] == '{') st.push(i);
else {
if (st.empty()) return false;
if (s[i] == ')' && s[st.top()] != '(') return false;
if (s[i] == '}' && s[st.top()] != '{') return false;
if (s[i] == ']' && s[st.top()] != '[') return false;
st.pop();
}
}
return st.empty();
}
};