//---------------------------------------------------------------------------
#include
#include
#define MEM_ERR "malloc() error!"
#define EMPTY_ERR "stack is empty!"
typedef struct node{
char oper;
struct node *next;
}node;
typedef struct{
node *head;
unsigned int size;
}stack;
void error_exit(const char *msg)
{
fprintf(stderr,"%s\n",msg);
exit(-1);
}
int isempty(stack *stk)
{
return stk->size?0:1;
}
stack *init(void)
{
stack *rt=(stack*)malloc(sizeof(stack));
if (rt==NULL) error_exit(MEM_ERR);
rt->head=NULL;
rt->size=0;
return rt;
}
void push(stack *stk,char op)
{
node *tp=(node*)malloc(sizeof(node));
if (tp==NULL) error_exit(MEM_ERR);
tp->oper=op;
tp->next=stk->head;
stk->head=tp;
++stk->size;
}
char pop(stack *stk)
{
char op;
node *tmp;
if (isempty(stk)) {
error_exit(EMPTY_ERR);
}
op=stk->head->oper;
tmp=stk->head;
stk->head=tmp->next;
--stk->size;
free(tmp);
return op;
}
char top(stack *stk)
{
if (isempty(stk)) {
error_exit(EMPTY_ERR);
}
return stk->head->oper;
}
void del_stk(stack *stk)
{
node *t;
while (stk->head)
{
t=stk->head;
stk->head=t->next;
free(t);
}
free(stk);
}
int islr(const char a)
{
return a=='('||a=='['||a=='{';
}
int isrr(const char a)
{
return a==')'||a==']'||a=='}';
}
int match(const char a,const char b)
{
int t;
switch (a) {
case '(':t=b==')';break;
case '[':t=b==']';break;
case '{':t=b=='}';break;
}
return t;
}
int main(int argc,char* argv[])
{
char a;
stack *stk=init();
while ((a=getchar())!='\n')
{
if (islr(a)) {
push(stk,a);
}
else if (isrr(a)) {
if (!isempty(stk)&&match(top(stk),a)) pop(stk);
else break;
}
}
if (!isempty(stk)) {
printf("Unmatched!\n");
del_stk(stk);
}
else printf("Matched!\n");
return 0;
}
//---------------------------------------------------------------------------
