文章目录
- （1）题目描述
- （2）解题思路
（1）题目描述
给定一个只包括
'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：
1、左括号必须用相同类型的右括号闭合。
2、左括号必须以正确的顺序闭合。
示例1：
输入：s = “( )”
输出：true
示例2：
输入：s = “( ) [ ] { }”
输出：true
示例3：
输入：s = “( ]”
输出：false
示例4：
输入：s = “( [ ) ]”
输出：false
示例5：
输入：s = “{ [ ] }”
输出：true
（2）解题思路
-
利用栈的性质解决此题
-
首先实现一个栈
-
然后遍历字符串，如果遇到左括号（
'('，'{'，'['），将其压入栈中，如果遇到右括号（'）'，'}'，']'），将当前栈顶的左括号出栈，与其匹配，看是否是一对，若匹配失败，则返回false，匹配成功，则继续遍历字符串后面的字符。 -
两种特殊情况：
-
（1）字符串中全是左括号，全部入栈了，遍历结束后，需要对栈判空一下，若不为空，返回false
-
（2）字符串中全是右括号，没有左括号则栈为空，所以在遍历字符串遇到右括号时需要判断一下当前栈是否为空，若为空，返回false
-
图解算法（示例2）：
- 图解算法（示例5）：
- 代码如下
首先实现一个栈：
//定义可以动态增长的栈
typedef struct Stack
{
char* a;
int top;
int capacity;
}Stack;
//初始化栈
void StackInit(Stack *ps)
{
assert(ps);
ps->a = NULL;
ps->top = -1;
ps->capacity = 0;
}
//销毁栈
void StackDestroy(Stack *ps)
{
assert(ps);
if(ps->a)
{
free(ps->a);
}
ps->a = NULL;
ps->top = -1;
ps->capacity = 0;
}
//入栈
void StackPush(Stack *ps, char x)
{
assert(ps);
if(ps->top == ps->capacity - 1) //检查栈的容量是否已满
{
//扩容
int newcapacity = (ps->capacity == 0) ? 4 : 2 * (ps->capacity);
char* temp = realloc(ps->a, newcapacity * sizeof(char));
if(temp == NULL)
{
perror("realloc");
exit(-1);
}
ps->a = temp;
ps->capacity = newcapacity; //更新容量
}
ps->top++;
ps->a[ps->top] = x;
}
//出栈
void StackPop(Stack *ps)
{
assert(ps);
assert(ps->top != -1); //栈不能为空
ps->top--;
}
//获取栈顶元素
char StackTop(Stack *ps)
{
assert(ps);
return ps->a[ps->top];
}
//检查栈是否为空
bool StackEmpty(Stack *ps)
{
assert(ps);
return ps->top == -1;
}
核心代码：
bool isValid(char *s){
Stack s1;
StackInit(&s1);
while(*s)
{
if(*s == '(' || *s == '[' || *s == '{') //当前字符为左括号
{
StackPush(&s1, *s); //入栈
}
else //当前字符为右括号
{
if(StackEmpty(&s1)) //如果栈为空，说明没有左括号，则返回false
{
return false;
}
char ch = StackTop(&s1); //获取栈顶元素
StackPop(&s1); //栈顶元素出栈
if((*s == ')' && ch != '(') //当前字符与栈顶元素未匹配成功，返回false
|| (*s == ']' && ch != '[')
|| (*s == '}' && ch != '{'))
{
return false;
}
}
s++;
}
//有可能字符串中全是左括号，全部入栈了，所以需要判空一下，若不为空返回false
return StackEmpty(&s1); //检测栈是否为空
}
上面核心代码，有一个小小的问题，没有销毁栈，可能会造成内存泄漏。
我们来改进一下：用一个布尔变量 match 来记录下返回值 true / false，最后先销毁栈，再返回值。
bool isValid(char *s){
Stack s1;
StackInit(&s1);
bool match = true; //记录函数返回值
while(*s)
{
if(*s == '(' || *s == '[' || *s == '{') //当前字符为左括号
{
StackPush(&s1, *s); //入栈
}
else //当前字符为右括号
{
if(StackEmpty(&s1)) //如果栈为空，说明没有左括号，则返回false
{
match = false;
break;
}
char ch = StackTop(&s1); //获取栈顶元素
StackPop(&s1); //栈顶元素出栈
if((*s == ')' && ch != '(') //当前字符与栈顶元素未匹配成功，返回false
|| (*s == ']' && ch != '[')
|| (*s == '}' && ch != '{'))
{
match = false;
break;
}
}
s++;
}
//match为true，有可能因为字符串中全是左括号，全部入栈了，所以需要判空一下，若不为空返回false
if(match == true)
{
match = StackEmpty(&s1);
}
StackDestroy(&s1); //销毁栈
return match;
}
大家快去动手练习一下吧！