原题链接:https://leetcode.cn/problems/valid-parentheses/
目录
1. 题目描述
2. 思路分析
3. 代码实现
1. 题目描述
2. 思路分析
这道题目主要考查了栈的特性:
题目的意思主要是要做到3点匹配:类型、顺序、数量。
题目给的例子是比较简单的情况,可能还有如下较为复杂的情况:
循环遍历字符串s中的字符,逐个取到每个括号,如果该括号是:
1. 左括号,入栈
2. 右括号,出栈顶括号,进行匹配。
如果不匹配,直接返回false。否则继续循环。
循环结束后,如果栈空则匹配,否则左括号比右括号多肯定不匹配。
3. 代码实现
typedef char STDataType;
#define INIT_CAPACITY 4
typedef struct Stack
{STDataType* a;int top; //栈顶int capacity; //容量
}ST;//初始化栈
void STInit(ST* ps);
//入栈
void STPush(ST* ps, STDataType x);
//出栈
void STPop(ST* ps);
//获取栈顶元素
STDataType STTop(ST* ps);
//获取栈中有效元素个数
int STSize(ST* ps);
//检测栈是否为空
bool STEmpty(ST* ps);
//销毁栈
void STDestroy(ST* ps);void STInit(ST* ps)
{assert(ps);ps->a = NULL;ps->top = 0;ps->capacity = 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);if (ps->top == ps->capacity){int newCapacity = ps->capacity == 0 ? INIT_CAPACITY : ps->capacity * 2;STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newCapacity);if (tmp == NULL){perror("realloc failed");exit(-1);}ps->a = tmp;ps->capacity = newCapacity;}ps->a[ps->top] = x;ps->top++;
}void STPop(ST* ps)
{assert(ps);//空assert(ps->a > 0);--ps->top;
}STDataType STTop(ST* ps)
{assert(ps);//空assert(ps->a > 0);return ps->a[ps->top - 1];
}int STSize(ST* ps)
{assert(ps);return ps->top;
}bool STEmpty(ST* ps)
{assert(ps);return ps->top == 0;
}void STDestroy(ST* ps)
{assert(ps);ps->a = NULL;ps->top = ps->capacity = 0;
}bool isValid(char * s){ST st;STInit(&st);char topVal;while(*s){if(*s=='('||*s=='{'||*s=='['){STPush(&st,*s);}else{if(STEmpty(&st)){STDestroy(&st);return false;}topVal=STTop(&st);if(*s==')'&&topVal!='('||*s=='}'&&topVal!='{'||*s==']'&&topVal!='['){STDestroy(&st);return false;}else{STPop(&st);}}++s;}bool ret=STEmpty(&st);STDestroy(&st);return ret;
}