题一：有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 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”说明为NULL if (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”说明为NULL if (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; }
