求助 括号匹配问题源代码
括号匹配问题<在vc++环境>
问假设一个算术表达式种可包含三种括号:
圆括号,方括号和花括号且三种括号可按任意次序嵌套使用.
试利用栈的运算编写判别给定表达中所含括号是否正确匹配对出现的算法,并能指示出错的位置.
请高手帮帮忙啊!下星期就交了.
typedef char SElemType;
#include<string.h>
#include<ctype.h>
#include<malloc.h> /* malloc()等 */
#include<limits.h> /* INT_MAX等 */
#include<stdio.h> /* EOF(=^Z或F6),NULL */
#include<stdlib.h> /* atoi() */
#include<io.h> /* eof() */
#include<math.h> /* floor(),ceil(),abs() */
#include<process.h> /* exit() */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
/* #define OVERFLOW -2 因为在math.h中已定义OVERFLOW的值为3,故去掉此行 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
typedef int Boolean; /* Boolean是布尔类型,其值是TRUE或FALSE */
#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
#define STACK_INCREMENT 2 /* 存储空间分配增量 */
typedef struct SqStack
{
SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */
SElemType *top; /* 栈顶指针 */
int stacksize; /* 当前已分配的存储空间，以元素为单位 */
}SqStack; /* 顺序栈 */
void InitStack(SqStack *S)
{ /* 构造一个空栈S */
(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base;
(*S).stacksize=STACK_INIT_SIZE;
}
void DestroyStack(SqStack *S)
{ /* 销毁栈S，S不再存在 */
free((*S).base);
(*S).base=NULL;
(*S).top=NULL;
(*S).stacksize=0;
}
void ClearStack(SqStack *S)
{ /* 把S置为空栈 */
(*S).top=(*S).base;
}
Status StackEmpty(SqStack S)
{ /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
if(S.top==S.base)
return TRUE;
else
return FALSE;
}
int StackLength(SqStack S)
{ /* 返回S的元素个数，即栈的长度 */
return S.top-S.base;
}
Status GetTop(SqStack S,SElemType *e)
{ /* 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERROR */
if(S.top>S.base)
{
*e=*(S.top-1);
return OK;
}
else
return ERROR;
}
void Push(SqStack *S,SElemType e)
{ /* 插入元素e为新的栈顶元素 */
if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */
{
(*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACK_INCREMENT)*sizeof(SElemType));
if(!(*S).base)
exit(OVERFLOW); /* 存储分配失败 */
(*S).top=(*S).base+(*S).stacksize;
(*S).stacksize+=STACK_INCREMENT;
}
*((*S).top)++=e;
}
Status Pop(SqStack *S,SElemType *e)
{ /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
if((*S).top==(*S).base)
return ERROR;
*e=*--(*S).top;
return OK;
}
void StackTraverse(SqStack S,void(*visit)(SElemType))
{ /* 从栈底到栈顶依次对栈中每个元素调用函数visit() */
while(S.top>S.base)
visit(*S.base++);
printf("\n");
}
void check()
{ /* 对于输入的任意一个字符串，检验括号是否配对 */
SqStack s;
SElemType ch[80],*p,e;
InitStack(&s); /* 初始化栈成功 */
printf("Please putinto your（()、[]和{}）biaodashi\n");
gets(ch);
p=ch; /* p指向字符串的首字符 */
while(*p) /* 没到串尾 */
switch(*p)
{
case '(':
case '[':
case '{':Push(&s,*p++); /* 左括号入栈，且p++ */
break;
case ')':
case ']':
case '}':if(!StackEmpty(s)) /* 栈不空 */
{
Pop(&s,&e); /* 弹出栈顶元素 */
if(!(e=='('&&*p==')'||e=='['&&*p==']'||e=='{'&&*p=='}'))
{ /* 出现3种匹配情况之外的情况 */
printf("left kuohao!=right\n");
exit(ERROR);
}
}
else /* 栈空 */
{
printf("lose left's kuohao\n");
exit(ERROR);
}
default: p++; /* 其它字符不处理，指针向后移 */
}
if(StackEmpty(s)) /* 字符串结束时栈空 */
printf("right!\n");
else
printf("Sorry,it's wrong!\n");
}
void main()
{
check();
}
