Question

假设表达式中允许包括1种括号，方括号。编写一个算法，判断表达式中的括号是否正确配对

#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int ElemType;
typedef struct
{
ElemType data[MaxSize];
int top;
} SqStack;
void InitStack(SqStack *&s)
{ s=(SqStack *)malloc(sizeof(SqStack));
s->top=-1;
}
int Push(SqStack *&s,ElemType e)
{ if(s->top==MaxSize-1)
return 0;
s->top++;
s->data[s->top]=e;
return 1;
}
int GetTop(SqStack *s,ElemType e)
{ if(s->top==-1)
return 0;
e=s->data[s->top];
return 1;
}
int Pop(SqStack *&s,ElemType e)
{ if(s->top==-1)
return 0;
e=s->data[s->top];
return 1;
}
int StackEmpty(SqStack *s)
{ return(s->top==-1);
}
int Match(char exp[],int n)
{ int i=0;
char e;
SqStack *st;
InitStack(st);
while(i<n)
{ if(exp[i]=='(')
Push(st,exp[i]);
else if(exp[i]==')')
{ if(GetTop(st,e)==1)
{ if(e!='(') return(0);
else Pop(st,e);
}
else return(0);
}
i++;
}
if(StackEmpty(st)==1) return(1);
else return(0);
}
void main()
{
char exp[100];
printf("请输入一个表达式:");
scanf("%s",exp);
Match(exp,111);
}

Answer 1

这是我编的一个括号匹配检测，可以包含三种括号类型
#include "stdio.h"
#include "stdlib.h"
#define maxsize 100
typedef struct
{
char*base;
char*top;
int size;
}stack;

void main()
{
char L[maxsize];
char*p;
stack *S;
int a,b,c,a1,b1,c1;
a=b=c=a1=b1=c1=0;
S=(stack*)malloc(sizeof(stack));
S->base=(char*)malloc(maxsize*sizeof(char));
S->size=maxsize;
S->top=S->base;
printf("输入一个表达式存入L中:");
scanf("%s",L);
p=L;
while(*p)
{
switch(*p)
{
case '(' :a++;*S->top++=*p;break;
case ')' :a1++;if(S->top!=S->base&&a1==a&&a1>b&&a1>c){S->top--;a--;break;}
else printf("配对不正确:\n");exit(0);
case '[' :b++;*S->top++=*p;break;
case ']' :b1++;if(S->top!=S->base&&b1==b&&b1>a&&b1>c){S->top--;b--;break;}
else printf("配对不正确:\n");exit(0);
case '{' :c++;*S->top++=*p;break;
case '}' :c1++;if(S->top!=S->base&&c1==c&&c1>a&&c1>b){S->top--;c--;break;}
else printf("配对不正确:\n");exit(0);
default :break;
}
p++;
}
if(S->top==S->base)
printf("配对正确:\n");
else
printf("配对不正确:\n");
}

Answer 2

Ls的算法不能判别次序错误啊
例如(4*[3+2)-1]这种错误就检测不出来