C语言实现 数据结构-栈-括号匹配
题目描述
假设一个表达式有英文字母（小写）、运算符（+，—，*，/）和左右小（圆）括号构成，以“@”作为表达式的结束符。请编写一个程序检查表达式中的左右圆括号是否匹配，若匹配，则返回“YES”；否则返回“NO”。假设表达式长度小于255，左圆括号少于20个。
输入
输出
样例输入
((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 ;
}
}