Problem C: 括號匹配（棧和隊列）
Time Limit: 1 Sec??Memory Limit: 128 MBSubmit: 76??Solved: 18
[Submit][Status][Web Board]
Description
假設一個表達式中只允許包含三種括號：圓括號“(”和“)”，方括號“[”和“]”和花括號“{”和“}”，且這三種括號可按任意的次序嵌套使用如：（…[…{… …[…]…}…[…]…(…)…]…)。設計一個算法，判斷表達式中的括號是否正確配對。輸出結果為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為一個空棧。
Input
{[][]()([])}[]()
Output
Yes
Sample Input
{[()[]][}] Sample Output
No HINT
1、注意括號匹配問題
2、只需提交你所編寫的算法
#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;
}
)
)