栈应用之平衡字符

编译器检查程序的语法错误，但是常常由于缺少一个符号（如遗漏一个花括号或者注释起始符），引起编译器列出上百行的诊断，而真正的错误并没有找出。这种情况下，一个有用的工具就是去检验成对出现的符号，比如每一个左花括号{都搭配一个右花括号}（方括号、圆括号等）。例如，”（[]）”是对的，而“({)}”显然是错的。
本节Jungle用栈来实现这样一个平衡字符的程序，两步走：

• 1.链表实现栈的设计
• 2.平衡字符检验

1.链表实现栈的设计

这一个内容与上一节的内容（栈Stack的链表实现）一样，不过数据域需要改成char类型，相应的操作也做微小变化。
栈的设计放在头文件List_Stack.h里：

#ifndef LIST_STACK
#define LIST_STACK

typedef struct STACK
{
    char ch;
    struct STACK* next;
}Stack;

//栈顶指针
Stack* topNode;

bool isEmpty()
{
    return topNode == NULL;
}

void push(char iData)
{
    Stack *currentNode;
    currentNode = (Stack*)malloc(sizeof(Stack));
    if(currentNode == NULL)
        printf("分配内存失败！\n");
    currentNode->ch = iData;
    currentNode->next = topNode;
    topNode = currentNode;
}

char pop()
{
    if(isEmpty())
    {
        printf("The Stack is Empty!\n");
        return ' ';
    }
    Stack *currentNode;
    currentNode = topNode;
    topNode = topNode->next;
    char ch = currentNode->ch;

    free(currentNode);
    return ch;
}

///销毁栈
void deleteStack()
{
    Stack *tempNode;
    if(isEmpty())
    {
        printf("The Stack is Empty!\n");
        return;
    }
    tempNode = topNode;
    while(topNode->next!=NULL)
    {
        tempNode = topNode->next;
        free(topNode);
        topNode = tempNode;
    }
    free(topNode);
    topNode = NULL;
}
#endif //LIST_STACK

2.平衡字符

检测到输入了开放符号（‘（’、‘[’、‘{’），就压入栈中；检测到封闭符号（‘)’、‘]’、‘}’），首先检测栈是否为空，为空肯定是错的；其次检测出战的字符是否与当前的封闭符号对应。

void testSymbol()
{
    char ch=' ';
    char tempCh = ' ';
    while(scanf("%c",&ch))
    {
        if(ch == '\n')//回车键结束输入
            break;
        if(ch == '[' || ch == '(' || ch == '{' )
        {
            //开放符号入栈
            push(ch);   
            printf("Push: %c\n",ch);
        }
        else 
        {
            if(ch==']'|| ch==')'|| ch=='}')
            {
                tempCh = pop();
                printf("Pop: %c\n",tempCh);
                if((ch==']'&& tempCh!='[') || (ch==')'&& tempCh!='(') || (ch=='}'&& tempCh!='{'))
                {
                    if(isEmpty())
                    {
                        printf("1 Wrong!The stack is empty!");
                        break;
                    }
                    else
                    {
                        printf("2 Wrong! %c is not match %c",ch,tempCh);
                        break;
                    }
                }
            }
        }
    }
    if(!isEmpty())
        printf("Wrong!");
}

3.测试