括号匹配(栈和队列)

时间: 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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。