#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 100
#define INIT_STACK_SIZE 10
#define STACKINCREMENT 10
typedef struct{
char *base;
char *top;
int stacksize;
}SqStack;//标准的栈定义
SqStack InitStack(SqStack S);
int Process(SqStack S,char expression[],int len);
SqStack Push(SqStack S,char c);
int StackEmpty(SqStack S);
SqStack Pop(SqStack S);
void OutPut(SqStack S);
int main(void)
{
SqStack S;
char expression[MAX];
int len;
printf("Please input string: /n");
scanf("%s",expression);
len=strlen(expression);//取栈的长度
S=InitStack(S); //初始化栈
if(Process(S,expression,len))//Process 用来判断字符串
printf("success./n");
else
printf("failure./n");
return 0;
}
SqStack InitStack(SqStack S)
{
if((S.base=(char *)malloc(INIT_STACK_SIZE * sizeof(char)))==NULL)
{
exit(1);
}
S.top=S.base;
S.stacksize=INIT_STACK_SIZE;
return S;
}
int Process(SqStack S,char expression[],int len)
{
int i,flag=1;
for(i=0;i<=len-1;i++)
{
switch(expression[i])
{
case '(': //如果出现左括号就压入栈
S=Push(S,expression[i]);
break;
case '[':
S=Push(S,expression[i]);
break;
case '{':
S=Push(S,expression[i]);
break;
case ')':
if(!StackEmpty(S) && *(S.top-1) == '(') //栈不空,且前一个元素是左括号
S=Pop(S); //出栈
else
{
flag=0;
return flag;
}
break;
case ']':
if(!StackEmpty(S) && *(S.top-1) == '[')
S=Pop(S);
else
{
flag=0;
return flag;
}
break;
case '}':
if(!StackEmpty(S) && *(S.top-1) == '{')
S=Pop(S);
else
{
flag=0;
return flag;
}
break;
default:
flag=0;
return flag;
}//switch
}//for
if(S.top == S.base) //栈空
flag=1;
else
flag=0;
return flag;
}
SqStack Push(SqStack S,char c)
{
*(S.top++)=c;
if(S.top-S.base >= S.stacksize)
{
if((S.base=(char *)realloc(S.base,(S.stacksize + STACKINCREMENT) * sizeof(char)))==NULL)
{
exit(1);
}
S.top=S.base + S.stacksize;
S.stacksize+=STACKINCREMENT;
}
return S;
}
int StackEmpty(SqStack S)
{
int flag=0;
if(S.top == S.base)
flag=1;
return flag;
}
SqStack Pop(SqStack S)
{
S.top--;
return S;
}