C语言实现 数据结构-栈-括号匹配

题目描述

输入

输出

样例输入

((1+b)-(a+3))*

样例输出

YES

样例输入

(25+x)*(a*(a+b+b)@

样例输出

NO算法实现：1.利用栈来实现只需要考虑输入的是不是左括号‘(‘ ，右括号‘)‘　　　　　2.当是左括号时 就让‘(‘进栈 ,当遇到右括号是‘)‘就出栈。p.s 这里栈我用的静态栈比较简单~　　　　　3.考虑栈里‘(‘多余了，则用top判断，如果完全匹配那么栈里的top应该为初始值为等于-1，输出YES，否则输出NO 　　　　　4.考虑栈元素下溢的问题，比如先输入了一个右括号‘)‘，那么我们直接判断他为NO，P.s：一开始我想如果表达式无所谓输入格式，先输入‘)‘那不是下溢了嘛，后面在输入‘(‘，感觉栈就不太管用了emmm，是我多虑了或者审题不清

#include <stdio.h>
#define maxsize 260
typedef struct stack
{
int top ;
char arr[maxsize];
}STACK ;
void init(STACK * ps);
bool push(STACK * ps ,char val);
void show_stack(STACK * ps);
// char pop(STACK * ps );
bool Match_Brackets(STACK * ps);
bool pop(STACK * ps );
int main()
{
int i,val;
STACK st ;
init(&st);
if(Match_Brackets(&st))
{
printf("YES\n");
}
else
{
printf("NO\n");
}

}

void init(STACK * ps)
{
ps->top = -1;
}
bool Match_Brackets(STACK * ps)
{
char ch,x ;
int flag = 0 ;
while(1)
{
scanf("%c",&ch);
if(ch == ‘@‘)
{
break ;
}
else if(ch==‘(‘)
{
push(ps,ch);
// show_stack(ps);
}
else if(ch==‘)‘)
{
if(pop(ps))
{
// show_stack(ps) ;
}
else
{
return false ;
}
}

}
if(ps->top == -1)
{
return true ;
}
else return false ;
}
bool push(STACK * ps ,char val)
{
if(ps->top == maxsize-1)
{
// printf("栈已满\n");
return false ;
}
ps->arr[++ps->top]=val;
return true ;
}
void show_stack(STACK * ps)
{
int i = ps->top;
while(i!= -1)
{
printf("%c ",ps->arr[i--]);
}
printf("\n");

}
bool pop(STACK * ps )
{
char ch ;
if(ps->top == -1)
{
// printf("栈为空\n");
return false ;
}
else
{
ps->arr[ps->top--] ;
return true ;
}
}