每日一道算法题（Leetcode 20）

What's past is prologue. 凡是过去，皆为序章。

题目

分析

1. 我们可以用栈的结构来解决这道题。

2. 我们使用while循环，每次读取字符串中一个元素进行操作，直到最后读取到 '\0'为止。

3. 如果遇见 '(', '[' ,'{' 这三种左括号，则把该左括号入栈；如果遇见 ')', ']' ,'}' 这三种右括号，则出栈一个栈中的元素。

4. 如果出栈的元素与右括号不匹配，则返回 false;如果匹配,则继续进行下一步。比如：这种情况 " ()[} "。

5. 读取到右括号时，先判断栈中是否还有元素，如果没有元素出来匹配，则说明右括号存在不能匹配情况，则直接返回 false。比如：这种情况 '' ()) "。

6. 对子字符串的遍历结束之后，需要再去判断栈中是否还有元素，如果有说明左括号存在不能匹配情况，则直接返回 false。比如：这种情况 '' (() "。

代码实现

bool isValid(char* s) 
{typedef struct Stack {char* arr;int capacity;int top;} Stack;void InitStack(Stack * ps) {assert(ps);ps->arr = NULL;ps->capacity = ps->top = 0;}void PushStack(Stack* ps,char x){assert(ps);if(ps->capacity == ps->top){int newcapacity=ps->capacity==0?4:2*ps->capacity;char* tmp=(char*)realloc(ps->arr,sizeof(char)*newcapacity);if(tmp==NULL){perror("realloc fail");exit(1);}ps->arr=tmp;ps->capacity=newcapacity;}      ps->arr[ps->top++]=x;}void PopStack(Stack * ps){assert(ps);assert(ps->top!=0);ps->top--;}char TopStack(Stack * ps){assert(ps);assert(ps->top!=0);return ps->arr[ps->top-1];}void DestroyStack(Stack * ps){assert(ps);if (ps->arr){free(ps->arr);//释放动态数组空间}ps->arr = NULL;ps->capacity = ps->top = 0;}Stack stack;InitStack(&stack);while(*s!='\0'){if(*s=='('||*s=='['||*s=='{'){PushStack(&stack,*s);}else{if(stack.top==0){DestroyStack(&stack);return false;}char ch=TopStack(&stack);if((ch=='('&&*s==')')||(ch=='['&&*s==']')||(ch=='{'&&*s=='}')){PopStack(&stack);}else{DestroyStack(&stack);return false;}}s++;}if(stack.top!=0){DestroyStack(&stack);return false;}DestroyStack(&stack);return true;
}