括号匹配(栈和队列)
时间: 1ms 内存:128M
描述:
假设一个表达式中只允许包含三种括号:圆括号“(”和“)”,方括号“[”和“]”和花括号“{”和“}”,且这三种括号可按任意的次序嵌套使用如:(…[…{… …[…]…}…[…]…(…)…]…)。设计一个算法,判断表达式中的括号是否正确配对。输出结果为Yes或者No。
顺序栈的定义为
typedef struct{char date[Max];int top;} Spstack;需编写的算法为int solve(char *a,Spstack *st);可使用的函数有:1、bool Pop(Spstack *&s,char &e); //出栈2、bool GetTop(Spstack *s,char &e); //取栈顶元素3、bool Push(Spstack *&s,char e); //入栈4、bool StackEmpty(Spstack *s); //判断是否为空栈括号匹配正确返回1,否则返回0。其中a为该表达式,st为一个空栈。
输入:
{[][]()([])}[]()
输出:
Yes
示例输入:
{[()[]][}]
示例输出:
No
提示:
参考答案(内存最优[0]):
#include <stdio.h>
#define Max 105
typedef struct
{
char date[Max];
int top;
} Spstack;
void InitStack(Spstack *&s)
{
s= new Spstack;
s->top=-1;
}
bool StackEmpty(Spstack *s)
{
return(s->top==-1);
}
bool Push(Spstack *&s,char e)
{
if(s->top==Max-1)return false;
s->top++;
s->date[s->top]=e;
return true;
}
bool GetTop(Spstack *s,char &e)
{
if(s->top==-1)return false;
e=s->date[s->top];
return true;
}
bool Pop(Spstack *&s,char &e)
{
if(s->top==-1)return false;
e=s->date[s->top];
s->top--;
return true;
}
void DestroyStack(Spstack * &s)
{
delete(s);
}int solve(char *a,Spstack *st)
{
int i=0,match=1;
char e;
while(a[i]!='\0'&&match)
{
if(a[i]=='('||a[i]=='{'||a[i]=='[')Push(st,a[i]);
else if(a[i]==')'||a[i]=='}'||a[i]==']')
{
if(a[i]==')'&&GetTop(st,e)==true)
{
if(e!='(') match=false;
else Pop(st,e);
}
else if(a[i]=='}'&&GetTop(st,e)==true)
{
if(e!='{') match=false;
else Pop(st,e);
}
else if(a[i]==']'&&GetTop(st,e)==true)
{
if(e!='[') match=false;
else Pop(st,e);
}
else match=false;
}
i++;
}
if(!StackEmpty(st))match=false;
return match;
}
int main()
{
char a[100];
bool match;
Spstack *st;
InitStack(st);
gets(a);
match=solve(a,st);
DestroyStack(st);
if(match)printf("Yes\n");
else printf("No\n");
return 0;
}
参考答案(时间最优[0]):
#include <stdio.h>
#define Max 105
typedef struct
{
char date[Max];
int top;
} Spstack;
void InitStack(Spstack *&s)
{
s= new Spstack;
s->top=-1;
}
bool StackEmpty(Spstack *s)
{
return(s->top==-1);
}
bool Push(Spstack *&s,char e)
{
if(s->top==Max-1)return false;
s->top++;
s->date[s->top]=e;
return true;
}
bool GetTop(Spstack *s,char &e)
{
if(s->top==-1)return false;
e=s->date[s->top];
return true;
}
bool Pop(Spstack *&s,char &e)
{
if(s->top==-1)return false;
e=s->date[s->top];
s->top--;
return true;
}
void DestroyStack(Spstack * &s)
{
delete(s);
}int solve(char *a,Spstack *st)
{
int i=0,match=1;
char e;
while(a[i]!='\0'&&match)
{
if(a[i]=='('||a[i]=='{'||a[i]=='[')Push(st,a[i]);
else if(a[i]==')'||a[i]=='}'||a[i]==']')
{
if(a[i]==')'&&GetTop(st,e)==true)
{
if(e!='(') match=false;
else Pop(st,e);
}
else if(a[i]=='}'&&GetTop(st,e)==true)
{
if(e!='{') match=false;
else Pop(st,e);
}
else if(a[i]==']'&&GetTop(st,e)==true)
{
if(e!='[') match=false;
else Pop(st,e);
}
else match=false;
}
i++;
}
if(!StackEmpty(st))match=false;
return match;
}
int main()
{
char a[100];
bool match;
Spstack *st;
InitStack(st);
gets(a);
match=solve(a,st);
DestroyStack(st);
if(match)printf("Yes\n");
else printf("No\n");
return 0;
}
题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。