题一:有效的括号
给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
-
示例 2:
输入:s = "()[]{}" 输出:true
思路一:
第一步:写出数组栈的结构体,然后分别写出栈的初始化,入栈,出栈,获取栈顶元素,销毁栈,检验栈是否为空的函数;
第二步:创建一个结构体变量,初始化,while(*s)决定是否继续循环,用switch找到对应的前置符号将他们入栈,如果是后置符号,则先判断ps中是否为空,然后再判断是否有对应的前置符合,没有:直接结束,有:继续循环;
第三步:创建相应的bool型变量记录SLEmpty()函数的返回值,销毁创建空间。
注意:OJ题不会判断代码开辟动态内存空间,所以在OJ题,不销毁开辟的动态内存也正确。
//约定类型方便更改类型
typedef char STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}SL;
//初始化
void SLInit(SL* ps)
{assert(ps);ps->a = NULL;ps->capacity = ps->top = 0;
}//入栈
void SLPush(SL* ps, STDataType x)
{assert(ps);//栈顶=容量说明需要扩容if (ps->capacity == ps->top){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->capacity = newcapacity;ps->a = tmp;}ps->a[ps->top] = x;//后缀++方便下一次入栈和打印栈顶ps->top++;
}//出栈
void SLPop(SL* ps)
{assert(ps);//为空情况“0”assert(ps->top > 0);//--ps->top;
}//获得栈顶元素
STDataType SLTTop(SL* ps)
{assert(ps);//为空情况“0”assert(ps->top > 0);int n = (ps->top) - 1;return ps->a[n];
}//获取栈中有效元素个数
int SLSize(SL* ps)
{assert(ps);return ps->top;
}//销毁栈
void SLDestroy(SL* ps)
{assert(ps);//开辟数组优势:一次全部释放free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
bool SLEmpty(SL* ps)
{assert(ps);//为“0”说明为NULLif (ps->top == 0){return true;}return false;
}//思路一:使用switch
bool isValid(char * s)
{SL ps;char val;//初始化SLInit(&ps);while (*s){switch (*s){case '(':case '[':case '{'://入栈SLPush(&ps, *s);break;case ')':case '}':case ']'://判断栈是否为空if (SLEmpty(&ps)){//销毁开辟的动态内存SLDestroy(&ps);return false;}//栈顶值val = SLTTop(&ps);//出栈SLPop(&ps);if (*s == ')' && val != '(' ||*s == ']' && val != '[' ||*s == '}' && val != '{'){SLDestroy(&ps);return false;}break;}s++;}bool ret = SLEmpty(&ps);SLDestroy(&ps);return ret;
}
改进简化:
原理同上,要实现的内容也同上,不过简化了switch()语句造成的多次调用,以及步骤上的增加,改用if----else语句后,代码更加的简洁清晰,不需要考虑每种后置符号的操作,if一次性全部解决了。总体上减少了三分之一的代码量。
//约定类型方便更改类型
typedef char STDataType;
typedef struct Stack
{STDataType* a;int top;int capacity;
}SL;
//初始化
void SLInit(SL* ps)
{assert(ps);ps->a = NULL;ps->capacity = ps->top = 0;
}//入栈
void SLPush(SL* ps, STDataType x)
{assert(ps);//栈顶=容量说明需要扩容if (ps->capacity == ps->top){int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;STDataType* tmp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newcapacity);if (tmp == NULL){perror("realloc fail");exit(-1);}ps->capacity = newcapacity;ps->a = tmp;}ps->a[ps->top] = x;//后缀++方便下一次入栈和打印栈顶ps->top++;
}//出栈
void SLPop(SL* ps)
{assert(ps);//为空情况“0”assert(ps->top > 0);//--ps->top;
}//获得栈顶元素
STDataType SLTTop(SL* ps)
{assert(ps);//为空情况“0”assert(ps->top > 0);int n = (ps->top) - 1;return ps->a[n];
}//销毁栈
void SLDestroy(SL* ps)
{assert(ps);//开辟数组优势:一次全部释放free(ps->a);ps->a = NULL;ps->capacity = ps->top = 0;
}// 检测栈是否为空,如果为空返回非零结果,如果不为空返回0
bool SLEmpty(SL* ps)
{assert(ps);//为“0”说明为NULLif (ps->top == 0){return true;}return false;
}//改进简化内容if——else
bool isValid(char * s)
{SL ps;char val;//初始化SLInit(&ps);while (*s){if(*s == '(' || *s == '{' || *s == '['){//入栈SLPush(&ps, *s);}else{//判断栈是否为空if (SLEmpty(&ps)){//销毁开辟的动态内存SLDestroy(&ps);return false;}//栈顶值val = SLTTop(&ps);//出栈SLPop(&ps);if (*s == ')' && val != '(' ||*s == ']' && val != '[' ||*s == '}' && val != '{'){SLDestroy(&ps);return false;}}s++;}bool ret = SLEmpty(&ps);SLDestroy(&ps);return ret;
}