Bracket Matching Problem With Stack Structure

2010/11/19

#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;
}