用链栈实现括号匹配.

用链栈实现字符匹配.

/*----------------------------括号匹配.c-----------------------------

  Program Description:利用栈来判断括号是否匹配
  Date:2011.9.14

 --------------------------------------------------------------------*/

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

#define TRUE 1
#define FALSE 0
#define N 100


/*定义数据结构体*/
typedef struct elem
{
    char c;
}Element;

/*定义链表栈*/
typedef struct node
{
    Element data;
    struct node *next;
}LinkStackNode;
typedef LinkStackNode *LinkStack;


int InitStack(LinkStack *top);
int Push(LinkStack top, char element);
int Pop(LinkStack top, char *element);
int GetTop(LinkStack top, char *element);
int match(char element_l, char element_r);
int IsEmpty(LinkStack top);

int main(void)
{
    int i = 0;
    int lenth = 0;
    char str[N];
    char ch;
    LinkStack top;

    if (FALSE == InitStack(&top))
    {
        return FALSE;
    }

    printf("请输入括号:\n");
    scanf("%s", str);

    lenth = strlen(str);
    for (i = 0; i < lenth; i++)
    {
        switch (str[i])
        {
            case '(':
            case '[':
            case '{':
                Push(top, str[i]);
                break;
            case ')':
            case ']':
            case '}':
                if (FALSE == IsEmpty(top))
                {
                    printf("右括号多余\n");
                    exit(0);
                }
                else
                {
                    GetTop(top, &ch);
                    if (TRUE ==  match(ch, str[i]) )
                    {
                        Pop(top, &ch);
                    }
                    else
                    {
                        printf("对应的左右括号不匹配\n");
                        exit(FALSE);
                    }
                }/*if*/
                break;
            default:
                exit(FALSE);
        }/*switch*/
    }/*for*/

    if (FALSE == IsEmpty(top))
    {
        printf("括号匹配\n");
    }
    else
    {
        printf("左括号多余\n");
        exit(FALSE);
    }

    return 0;
}

int InitStack(LinkStack *top)
{

    *top = (LinkStack)malloc(sizeof(LinkStackNode));
    if (NULL == top)
    {
        return FALSE;
    }

    (*top)->next = NULL;

    return TRUE;
}

int Push(LinkStack top, char element)
{
    LinkStack temp;

    temp = (LinkStack)malloc(sizeof(LinkStackNode));
    if (NULL == temp)
    {
        return FALSE;
    }

    temp->data.c = element;

    temp->next = top->next; //头插法
    top->next = temp;
//    top = top->next;     //top不需要改变，一直指向头指针.

    return TRUE;
}

int Pop(LinkStack top, char *element)
{
    LinkStack temp;

    if (NULL == top->next)
    {
        return FALSE;
    }

    temp = top->next;
    *element = temp->data.c;
    top->next = temp->next;

    free(temp);

    return TRUE;
}

int GetTop(LinkStack top, char *element)
{
    LinkStack temp;

    if (NULL == top->next)
    {
        return FALSE;
    }

    temp = top->next;
    *element = temp->data.c;

    return TRUE;
}

int IsEmpty(LinkStack top)
{
    if (NULL == top->next)
    {
        return FALSE;
    }
    else
    {
        return TRUE;
    }
}

int match(char element_l, char element_r)
{
    if (element_l == '(')
    {
        if (element_r == ')')
        {
            return TRUE;
        }
        else
        {
            return FALSE;
        }
    }
    else if (element_l == '[')
    {
        if (element_r == ']')
        {
            return TRUE;
        }
        else
        {
            return FALSE;
        }
    }
    else if (element_l == '{')
    {
        if (element_r == '}')
        {
            return TRUE;
        }
        else
        {
            return FALSE;
        }
    }
    else
    {
        exit(FALSE);
    }

}