数据oj题——有效的括号

好了，上一篇我们写过栈的实现的文章了，此外，我们现在来利用栈来写一道OJ题

20. 有效的括号 - 力扣（LeetCode）

这道题呢，由于还没有学到c++，我们还是使用c语言的形来写，而c语言有没有栈的库，所以就得我们亲自手搓一个。即我们上一篇写过的栈的实现。

注意的是：

上一篇我们写的栈的实现是使用的是int，而括号是属于char类型的，所以我们得改一下。

这里我们只需要改一下下面那个就行了

typedef char StDatatype;

通过这个，我们可以一下子可以明白了，为什么之前无论是单链表，顺序表等等都要使用这个代替类型了吧。如果改变了类型，我们只需要改一下这里就行，但是，试想如果没有这代码，是不是得改栈里面的很多地方？这就非常的麻烦了，这里就显得非常牛的了。

现在开始写另外的这道题目的正文

bool isValid(char* s) {
    ST st;
    STInit(&st);
    while(*s)
    {
        if(*s=='(' ||*s=='{' ||*s=='[')
        {
            STPush(&st,*s);
        }
        else
        {
            if(STEmpty(&st))
                return false;

            char top=STTop(&st);
            STPop(&st);
            if((*s==')' && top !='(')||
            (*s=='}' &&top !='{') ||
            (*s==']' &&top !='['))
            {
                return false;
            }
        }
        s++;

    }
    bool ret=STEmpty(&st);
    Destory(&st);
    return ret;

}

解释：

我们这里分为两个部分：左括号和右括号。

如果是左括号eg：（，{ , [ 的话就先插入，不是的话就出栈。

此时，还要注意top的变化，

出栈时，如果进栈的左括号与出栈的右括号不匹配的话，就可以直接返回判断它错误就行，

匹配的话，就让他继续出栈即s++。

注意的是：这里不要写成

if((*s=='(' && top !=')')||
            (*s=='{' &&top !='}') ||
            (*s=='[' &&top !=']'))
            {
                return false;
            }

*s是右括号， 满足 == 任意一个左括号 (  [ { 
都是不等于的，所以直接是假。
条件为真才会进入if语句呢
别忘了上面是else！！！！！

此外，我们还得还要考虑这么一种情况：

当直到出栈完了为空后，还没找到匹配，也就直接返回判断错误就行了

最后不要忘了还要释放空间。！

现在来附上代码

typedef char StDatatype;
typedef struct Stack
{
	StDatatype* a ;
	int top;
	int capacity;

}ST;

//初始化
void STInit(ST* ps);
void Destory(ST* ps);
void STPush(ST* ps,StDatatype x);
void STPop(ST* ps);
int size(ST* ps);
bool STEmpty(ST* ps);
StDatatype STTop(ST* ps);

void STInit(ST* ps)
{
	assert(ps);
	ps->a = (StDatatype*)malloc(sizeof(StDatatype) * 4);
	if (ps->a == NULL)
	{
		perror("malloc fail");
		return;
	}
	ps->top = 0;
	ps->capacity = 4;
}

void Destory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->capacity = 0;
	ps->top = 0;
}
void  STPush(ST* ps,StDatatype x)
{
	if (ps->top == ps->capacity)
	{
		StDatatype* temp =(StDatatype*) realloc(ps->a, sizeof(StDatatype) * ps->capacity * 2);
		if (temp == NULL)
		{
			perror("realloc fail");
			return ;
		}
		ps->a = temp;
		ps->capacity *= 2;
	}
	ps->a[ps->top] = x;
	ps->top++;
}
void STPop(ST* ps)
{
	assert(ps);
	assert(!STEmpty(ps));
	ps->top--;
}
int size(ST* ps)
{
	assert(ps);
	return ps->top;
}
bool STEmpty(ST* ps)
{
	assert(ps);
	return ps->top == 0;
}
StDatatype STTop(ST* ps)
{
	assert(ps);
    assert(!STEmpty(ps));
	return ps->a[ps->top-1];
}

bool isValid(char* s) {
    ST st;
    STInit(&st);
    while(*s)
    {
        if(*s=='(' ||*s=='{' ||*s=='[')
        {
            STPush(&st,*s);
        }
        else
        {
            if(STEmpty(&st))
                return false;

            char top=STTop(&st);
            STPop(&st);
            if((*s==')' && top !='(')||
            (*s=='}' &&top !='{') ||
            (*s==']' &&top !='['))
            {
                return false;
            }
        }
        s++;

    }
    bool ret=STEmpty(&st);
    Destory(&st);
    return ret;

}

到了这里，就结束了。

今次鸡汤：

坚持住，勇敢闯出那一步！