假设一个算数表达式中包含原括弧、方括弧和花括弧三种类型的括弧

答：用堆栈st进行判定，将 ( 、 [ 或 { 入栈，当遇到 }  、 ]  或 ) 时，检查当前栈顶元素是否是对应的( 、 [ 或 {，若是则退栈，否则返回表示不配对。当整个算术表达式检查完毕时，若栈为空表示括号正确配对，否则不配对。

编程后的整个函数如下（李书P31—32）

#define m0 100     /*m0为算术表达式中最多字符个数*/
correct(exp,tag)
char exp[m0];
int tag;
{char st[m0];
int top=0, i=1;
tag=1;
while (i<=m0 && tag)
{if (exp[i]= = ‘(‘||exp[i]= =’[‘||exp[i]= =’{‘）   /*遇到‘(‘、’[‘或’{‘，则将其入栈*/
{top++;
st[top]=exp[i];
}
if (exp[i]= =’)’ )   /*遇到’)’ ，若栈顶是‘(‘，则继续处理，否则以不配对返回*/
  if(st[top]= =‘(‘ ) top--;
else tag=0;
if (exp[i]= =’ )’ )   /*遇到’ ]’ ，若栈顶是‘[‘，则继续处理，否则以不配对返回*/
  if(st[top]= =‘[ ‘]  top--;
else tag=0;
if (exp[i]= =’)’ )   /*遇到’ }’ ，若栈顶是‘{‘，则继续处理，否则以不配对返回*/
  if(st[top]= =‘{‘ top--;
else tag=0;
i++;
}
if(top>0)tag=0;  /*若栈不空，则不配对*/
}

严题集对应答案：

***

Status AllBrackets_Test(char *str)//判别表达式中三种括号是否匹配

{
  InitStack(s);
  for(p=str;*p;p++)
  {
    if(*p=='('||*p=='['||*p=='{') push(s,*p);
    else if(*p==')'||*p==']'||*p=='}')
    {
      if(StackEmpty(s)) return ERROR;
      pop(s,c);
      if(*p==')'&&c!='(') return ERROR;
      if(*p==']'&&c!='[') return ERROR;
      if(*p=='}'&&c!='{') return ERROR; //必须与当前栈顶括号匹配
    }
  }//for
  if(!StackEmpty(s)) return ERROR;
  return OK;
}//AllBrackets_Test

2001级通信6班张沐同学答案（已上机通过）

#include<stdio.h>
#include<stdlib.h>
void push(char x);
void pop();
void correct(enum Boolean &tag);
//原来的定义是void correct(struct Stack* head,enum Boolean &tag);
 
typedef struct Stack
{
char data;
struct Stack *next;
};
 
struct Stack *head,*p;
enum Boolean{FALSE,TRUE}tag;
 
 
void main()
{
head=(struct Stack*)malloc(sizeof(struct Stack));
head->data='S';
head->next=NULL;
// head's data has not been initialized!!
correct(tag);
if(tag)
printf("Right!");
else
printf("Wrong!");
}
 
void push(char x)
{
p=(struct Stack*)malloc(sizeof(struct Stack));
if(!p)
printf("There's no space.\n");
else
{
p->data=x;
p->next=head;
head=p;
}
}
// if you define the "Correct" function like that
//Debug will show that the Push action doesn’t take effection
 
void pop()
{
if(head->next==NULL)
printf("The stack is empty.\n");
else
{
p=head;
head=head->next;
free(p);
}
}
 
//void correct(struct Stack* head,enum Boolean &tag)
void correct(enum Boolean &tag)
{
int i;
char y;
 
printf("Please enter a bds:");
for(i=0;y!='\n';i++)
{
scanf("%c",&y);
if((y==')'&&head->data=='(')||(y==']'&&head->data=='[')||(y=='}'&&head->data=='{'))
pop();
else if((y=='(')||(y=='[')||(y=='{'))
push(y);
/*调试程序显示，y并没有被推入堆栈中。即head->data的值在Push中显示为y的值，但是出Push函数。马上变成Null。*/
else
continue;
}
 
if(head->next==NULL)       //原来的程序是if(head ==NULL)	tag=TRUE;
tag=TRUE;
else
tag=FALSE;
}

/*总结： 由于head为全局变量，所以不应该将其再次作为函数的变量。因为C语言的函数变量是传值机制，所以在函数中对参数进行了拷贝复本，所以不能改变head的数值。*/