栈的应用之括号匹配的检验

栈的应用之括号匹配的检验
16年2月29日22:09:16
检验括号匹配的方法，就是对给定的字符串依次检验，若是左括号，入栈，若是右括号，则判断栈最上面那个元素，如果能够匹配，就继续判断，如果不匹配的话就返回错误。如果是其他字符，就不检验。检验到字符串的结尾的话，这时候要判断栈是否为空，判断是否有剩余的左括号。

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

#define STACK_INIT_SIZE 100
#define STACK_INCREMENT 10


typedef struct {
    char *top;
    char *base;
    int stacksize;
}Stack;

char * InitStack(Stack *S)
{
    S->base = (char *)malloc(sizeof(char) * STACK_INIT_SIZE);
    if (!S->base)
    {
        printf("Can not malloc memory for stack.\n");
        exit(-1);
    }

    S->top = S->base;
    S->stacksize = STACK_INIT_SIZE;

    return S->base;
}

void Push(Stack *S, char c)
{
    if ((S->top - S->base) > S->stacksize)
    {
         S->base = (char *)realloc(S->base, (S->stacksize + STACK_INCREMENT));
         if (!S->base)
         {
             printf("Can not reallco memory for Stack.\n");
             exit(-1);
         }

         S->top = S->base + S->stacksize;
         S->stacksize += STACK_INCREMENT;
    }

    *S->top = c;
    S->top++;
}

int Pop(Stack *S, char c)
{
    if (S->top == S->base)
    {
        printf("The stack is empty.\n");
        exit(-1);
    }

    c = *(--S->top);

    return 1;
}

int IsEmpty(Stack S)
{
    return S.top == S.base ? 1 : 0;
}

char GetTop(Stack S, char *elem)
{
    if (S.top == S.base)
    {
        printf("The Stack is Empty.\n");
        exit(-1);
    }

    *elem = *--S.top;
    return *elem;
}

void TraverseStack(Stack S)
{
    while (S.top > S.base)
    {
        printf("%c", *--S.top);
    }
    printf("\n");
}

int IsMatch(char ch1, char ch2)
{
    if(ch1 == '(' && ch2 == ')')
    {
         return 1;
    }
    else if(ch1 == '[' && ch2 == ']')
    {
        return 1;
    }else if(ch1 == '{' && ch2 == '}')
    {
        return 1;
    }else
    {
        return 0;
    }

}


int main(int argc, char const *argv[])
{
    Stack S;
    char ch[80], *p, e;

    InitStack(&S);

    printf("Please enter the formula with brackets:\n");
    gets(ch);

    p = ch;

    while (*p)
    {
        switch (*p)
        {
            case '(' :
            case '[' :
            case '{' :
            Push(&S, *p);
            break;
            case ')':
            case ']':
            case '}':
            if (IsEmpty(S))
            {
                printf("Error formula, don't match.\n");
                exit(-1);
            }

            if (IsMatch(GetTop(S, &e), *p))
            {
                Pop(&S, e);
            }
            else
            {
                printf("Don't match.\n");
                exit(-1);
            }
            default: ;
        }
        p++;
    }

    if (IsEmpty(S))
    {
        printf("Matched.\n");
    }
    else
    {
        printf("Error, don't match.\n");
    }

    return 0;
}

在写这个程序的时候，程序出错调试了很久，原因是从新写了一个GetTop函数和IsMatch函数，这两个函数写出来以后都没有进行测试就直接使用了，导致的错误。比如刚开始写的IsMatch函数：
int IsMatch(char ch1, char ch2)
{
    if(ch1 == '(' && ch2 == ')')
    {
         return 1;
    }
    else if(ch1 == '[' && ch2 == ']')
    {
        return 1;
    }else if(ch1 == '{' && ch2 == '}')
    {
        return 1;
    }else
    {
        return 0;
    }

}
它有两个参数，第一个参数是左括号，第二个参数是右括号，但是在下面调用的时候，
IsMatch(*p， GetTop(S, &e))，当程序执行到这里的时候，*p是右括号，而栈里面的元素是左括号，这两个参数写反了，导致了这个函数一直返回0。以后写程序的时候要注意这个问题，所有新写的函数最好都测试一遍，这样花费的时间比最后调试花费的时间少很多。