数据结构中经典习题：括号检验

分手后的思念是犯贱 2022-04-17 00:14 166阅读 0赞

\#define TRUE 1  
\#define FALSE 0  
\#define OK 1  
\#define ERROR 0  
\#define INFEASIBLE -1  
\#define OVERFLOW -2  
\#define STACK\_INIT\_SIZE 100  
\#define STACKINCREMENT 10  
\#include<stdio.h>  
\#include<stdlib.h>  
\#include<malloc.h>  
typedef char SElemtype;  
typedef struct\{  
SElemtype \*base;  
SElemtype \*top;  
int stacksize;  
\}SqStack;  
int InitStack(SqStack \*S)\{ //构造一个空栈S  
(\*S).base=(SElemtype *)malloc(STACK\_INIT\_SIZE*sizeof(SElemtype));  
if(!(\*S).base)\{  
exit(OVERFLOW); //存储分配失败  
\}  
else (\*S).top=(\*S).base;  
(\*S).stacksize=STACK\_INIT\_SIZE;  
return OK;  
\}  
int GetTop(SqStack S,SElemtype \*e)\{ //若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR  
if(S.baseS.top)\{  
return ERROR;  
\}  
else *e=*(S.top-1);  
return OK;  
\}  
int Push(SqStack \*S,SElemtype e)\{ // 插入元素e为新的栈顶元素  
if((\*S).top-(\*S).base>=(\*S).stacksize)\{ //栈满，追加存储空间  
(\*S).base=(SElemtype \*)realloc((\*S).base,((\*S).stacksize+STACKINCREMENT)\*sizeof(SElemtype));  
if(!(\*S).base)\{  
exit(OVERFLOW); //存储分配失败  
\}  
(\*S).top=(\*S).base+(\*S).stacksize;  
(\*S).stacksize+=STACKINCREMENT;  
\}  
\*((\*S).top)++=e;  
return OK;  
\}  
int Pop(SqStack \*S,SElemtype \*e)\{ //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR  
if((\*S).top(\*S).base)\{  
return ERROR;  
\}  
*e=*–(*S).top;  
return OK;  
\}  
int StackLength(SqStack S)\{ //返回S的元素个数，即栈的长度  
return S.top-S.base;  
\}  
int VisitStack(SqStack S)\{ //从栈底到栈顶依次对栈中每个元素遍历  
for(int i=1;i<=StackLength(S);i++)\{  
printf("%d \\n",*(S.base));  
S.base++;  
\}  
return OK;  
\}  
int ClearStack(SqStack \*S)\{ //把S置为空栈  
(\*S).base=(\*S).top;  
\}  
int DestroyStack(SqStack \*S)\{ //销毁栈S，S不再存在  
free((\*S).base);  
(\*S).base=(\*S).top=NULL;  
(\*S).stacksize=0;  
return OK;  
\}  
int EmptyStack(SqStack S)\{ //若栈S为空栈，则返回TRUE，否则返回FALSE  
if(S.baseS.top)\{  
return TRUE;  
\}  
else return FALSE;  
\}  
void check()\{  
SqStack S;  
SElemtype ch\[80\],\*p,e;  
if(InitStack(&S))\{  
printf(“请输入表达式:\\n”);  
gets(ch);  
p=ch;  
while(\*p)\{  
switch(\*p)\{  
case ‘(’:  
case ‘\[’:Push(&S,\*p);  
p++;  
break;  
case ‘)’:  
case ‘\]’:if(!EmptyStack(S))\{  
Pop(&S,&e);  
if(\*p’)’&&e!=’(’||\*p==’\]’&&e!=’\[’)\{  
printf(“左右括号不匹配\\n”);  
exit(ERROR);  
\}  
else \{  
p++;  
break;  
\}  
\}  
else \{  
printf(“缺乏左括号\\n”);  
exit(ERROR);  
\}  
default:p++;  
\}  
if(EmptyStack(S))\{  
printf(“括号匹配\\n”);  
\}  
else \{  
printf(“缺乏左括号\\n”);  
\}  
\}  
\}  
\}  
void main()  
\{  
check();  
\}![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmcxMzU2Mzc1ODEyOA_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lhbmcxMzU2Mzc1ODEyOA_size_16_color_FFFFFF_t_70]: /images/20220417/6e69cc97c51348daa7c04c71c8c1c9cf.png