数据结构实验之栈四：括号匹配

sin(20+10)

{[}]

yes

no

#include<bits/stdc++.h> using namespace std; #define STACK_INIT_SZIE 100//每次分配的空间个数 #define STACK_INCREMENT 10//每次追加的空间个数 #define OK 1; #define ERROR 0; typedef char ElemType; typedef struct { ElemType *top; ElemType *base; int stacksize; }mystack; void Initialstack(mystack &s)//栈的初始化 { s.base = (ElemType *)malloc(STACK_INIT_SZIE*sizeof(ElemType)); if(!s.base) { exit(OVERFLOW); } s.top = s.base; s.stacksize = STACK_INIT_SZIE; } void Push(mystack &s, ElemType &e)//入栈 { if(s.top - s.base == s.stacksize)//栈满 { s.base = (ElemType *)realloc(s.base,(s.stacksize + STACK_INCREMENT)*sizeof(ElemType)); if(!s.base) { exit(OVERFLOW); } s.top = s.base + s.stacksize; s.stacksize += STACK_INCREMENT; } *(s.top)++ = e; } int Pop(mystack &s)//出栈 { if(s.top == s.base)//空栈 { return ERROR; } else s.top--; return OK; } int Top(mystack &s, ElemType &e)//访问栈顶元素 { if(s.top == s.base)//空栈 { return ERROR; } else e = *(--s.top); s.top++; return OK; } int main() { char str[100]; ElemType e; int n, i, f; while(gets(str)) { mystack s; Initialstack(s); n = strlen(str); f = 1; for(i = 0; i < n; i++) { if(str[i] == '('|| str[i] == '[' || str[i] == '{' || str[i] == '}' || str[i] == ']' || str[i] == ')') { if(str[i] == '('|| str[i] == '[' || str[i] == '{' ) { Push(s,str[i]); } else { if(str[i] == ')') { if(!Top(s, e)) { f = 0; break; } if(e!='(') { f = 0; break; } else Pop(s); } else if(str[i] == '}') { if(!Top(s, e)) { f = 0; break; } if(e!='{') { f = 0; break; } else Pop(s); } else if(str[i] == ']') { if(!Top(s, e)) { f = 0; break; } if(e!='[') { f = 0; break; } Pop(s); } } } } if(f) { if(!Top(s,e)) f = 1; else f = 0; } if(f) printf("yes\n"); else printf("no\n"); } return 0; }