Question

数据结构(C)实现括号匹配程序的问题

#include<stdio.h>
#include<stdlib.h>

#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define TRUE 1
#define FALSE 0
#define STACK_INIT_SIZE 100
#define STACKINCREAMENT 10
typedef int SElemType;
typedef int Status;
typedef char String[100];
typedef struct {
SElemType * base;
SElemType * top;
int stacksize;
}SqStack;
Status InitStack(SqStack &S);
Status Push(SqStack &S,SElemType e);
Status Pop(SqStack &S,SElemType &e);
Status StackEmpty(SqStack S);
Status Length(String &exp);
Status matching(SqStack &S,String &exp);
int main(){
SqStack S;
InitStack(S);
int i;
String exp[100];
printf("请输入符号： ");
for(i=0;i<100;i++)
scanf("%s",&exp[i]);
matching(S,exp[i]);

return 0;
}

/*栈的初始化*/
Status InitStack( SqStack &S){
S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
if(!S.base) exit (OVERFLOW);
S.top = S.base;
S.stacksize= STACK_INIT_SIZE;
return OK;
}

/*插入e为栈顶的新元素*/
Status Push(SqStack &S,SElemType e){
if(S.top-S.base>=S.stacksize){
S.base=(SElemType *)realloc(S.base,(S.stacksize+STACKINCREAMENT)* sizeof(SElemType));
if(!S.base)return (OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREAMENT;
}
*S.top++=e;
return OK;
}
/*栈顶元素的返回*/
Status GetTop(SqStack &S,SElemType &e){
if(S.top==S.base) return ERROR;
e=*(S.top-1);
return OK;
}
/*删除栈顶元素*/
Status Pop(SqStack &S,SElemType &e){
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}
/*检查栈是否为空？*/
Status StackEmpty(SqStack S){
if(S.top==S.base) return TRUE;
else return FALSE;
}
/*计算栈的长度*/
Status Length(String &exp){
int i=0;
do{i++;}
while(exp[i]=='\0');
return(i);
}
/*括号匹配*/
Status matching(SqStack &S,String &exp) {
int i,state = 1;
SElemType e;

while (i<=Length(exp) && state) {
switch (exp[i]) {

case '(':{Push(S,exp[i]); i++; break;}
case ')': {
if(!StackEmpty(S)&&GetTop(S,e)=='(')
{Pop(S,e); i++; }
else {state = 0; }
break; }
}
if (StackEmpty(S)&&state)
printf("匹配！！");
else printf("不匹配！！");
return OK;}}

调试没错，但是运行不出来，各位帮我看看吧！！万分感谢！！

Answer 1

/*这是我以前写的与你分享吧嘻嘻
2013年3月26日 15:06:12
目的：通过栈检验括号是否匹配
*/
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#include "Common_Stack.cpp"

extern void Init_Stack(pSTACK S);
extern void De_Stack(pSTACK S);
extern void Push(pSTACK S);
extern bool Empty(pSTACK S);
extern bool Pop(pSTACK S);
int main(void)
{
char * pch = NULL;
char ch;
STACK S;
Init_Stack(&S);
ch = getchar();
printf("请输入带括号的程序段并以“#”未结束符\n");
while ('#' != ch)
{

if ('[' == ch || '(' == ch || '<' == ch)
{
Push(&S, ch);
printf("%c进栈\n", ch);
pch = S.pTop-1;

}
else if (']' == ch || ')' == ch || '>' == ch)
{
while (S.pTop != pch)/* 出栈括号*/
{
S.pTop--;
printf("出栈%c\n", *(S.pTop));
}
pch = S.pTop-1;
/*找到下一个左括号的位置赋值给pch*/
while ('[' != *(pch)&&'(' != *(pch)&&'<' != *(pch))/*这里的关系连接符是&&不是||哦在分析一下*/
{
pch--;
}
}
else
{
Push(&S, ch);
printf("%c进栈\n", ch);
}
ch = getchar();
}
Pop(&S);
De_Stack(&S);
return 0;
}
/*
一》程序设计思路：
将栈顶元素与待进栈的括号字符比较1.如果不匹配成功则符号进栈2.如果匹配成功则栈顶元素出栈
二》步骤：1.初始化栈2.输入程序段3.逻辑匹配（1）成功符号出栈栈顶指针下移，令定义追踪指针指向宅内已有括号元素（2）
匹配不成功(1)是括号字符进栈栈顶指针上移，追踪指针等于栈顶指针减一（以为栈顶指针总指向有效数据下一个位置）
(2)不是括号元素入栈栈顶指针上移，追踪指针不改变
三》具体实现：1.以‘#’字符作为输入结束符2.(1)是左括号元素压栈并追踪指针标记(2)是右括号则出栈(3)以上都不是直接压栈
(4)再次获取键入值
*/

Answer 2

下面这段代码存在逻辑错误。
for(i=0;i<100;i++)
scanf("%s",&exp[i]);
matching(S,exp[i]);

for循环仅对这里的scanf有效，循环完毕，i=100，故后面的maching调用因为下标越界发生错误。

建议修改为：
for(i=0;i<100;i++) {
Stack S;
scanf("%s",&exp[i]);
InitStack(S);
matching(S,exp[i]);
}
这里有应该每次匹配之前都要初始化一个新的栈（或者将栈清空）。