设字符串仅由圆括号“（”和“）”，方括号“[”和“]”，花括号“{ ”和“}”组成，利用链栈的操作编写一个检查括号是否正确配对的算法：int Matcher(LstackTP *ls)。例如[{ { （）}[ ]}（）{[ ]}]是正确的，而{ （{ （）[ ]}）}]）}则不正确。设链栈定义如下：（6分）
typedef struct node
{ char data;
struct node * next;
} LStackTp；
// Stack.cpp : Defines the entry point for the console application. // #include " stdafx.h " #include " stdlib.h " typedef struct node { char data; struct node * next; }LStackTp; void InitStack(LStackTp **ls) { *ls=NULL; } void Push(LStackTp **ls, char x) { LStackTp *p; p=(LStackTp *)malloc( sizeof(LStackTp)); p->data=x; p->next=*ls; *ls=p; } int Pop(LStackTp **ls, char *x) { LStackTp *p; if (*ls!=NULL) { p=*ls; *x=p->data; *ls=p->next; free(p); return 1; } return 0; } int EmptyStack(LStackTp *ls) { return (ls==NULL); } char GetStackTop(LStackTp *ls) { if (ls) return ls->data; else return ' \0 '; } void PrintStack(LStackTp **ls) { LStackTp *p; p=*ls; while (p) { printf( " %c \n ",p->data); p=p->next; } } int MyMatcher( char ch1, char ch2) { if ((ch1== ' ( ') && (ch2== ' ) ')) return 1; if ((ch1== ' [ ') && (ch2== ' ] ')) return 1; if ((ch1== ' { ') && (ch2== ' } ')) return 1; return 0; } int Matcher(LStackTp **ls, char *p) { char ch; char *x=&ch; while (*p) { if ( MyMatcher(GetStackTop(*ls),(*p) )) { Pop(ls,x); } else { Push(ls,*p); } p++; } return EmptyStack(*ls); } int main( int argc, char* argv[]) { LStackTp *S; InitStack(&S); char *p= " (()){}[]{ {}({})}({[()]}) "; if (Matcher(&S,p)) printf( " 这是一个合法的括号序列！ "); else printf( " 这是一个不合法的括号序列！ "); printf( " \n\n\n\n\n "); return 0;
} 