栈的应用实战--字符匹配

一、如何实现编译器中的符号成对检测？

1>算法思路：

    1)从第一个字符开始扫描

    2)当遇见普通字符时忽略，当遇见左符号时压入栈中

    3）当遇见右符号时从栈中弹出栈顶符号

    4）进行匹配

        匹配成功：继续读入下一个字符

        匹配失败：立即停止，并报错

    5）结束

        成功：所有字符扫描完毕，且栈为空

        失败：匹配失败或所有字符扫描完毕但栈不为空

2>算法框架

scanner(code)

{

    创建栈S;

    i = 0;

    while(code[i] != '\0')

    {

        if( code[i]为左符号){

            Push(S, code[i]);

        }

         if( code[i]为右符号){

            c = Pop(S);

        if(c 与 code[i]不匹配){

            报错，停止循环；

        }

    }

    i++;

}

    if( (Size(S) == 0 ) && (code[i] == '\0') ){

        匹配成功；

    }else{

    匹配失败，报错

    }

}

/******************************C程序中符号的匹配*********************/

#include <stdio.h>
#include <stdlib.h>
#include "LinkStack.h"
/* run this program using the console pauser or add your own getch, system("pause") or input loop */

int isLeft( char c)
{
    int ret = 0;

    switch(c)
    {
        case '<':
        case '(':
        case '{':
        case '\'':
        case '\"':
            ret = 1;
            break;
        default:
            ret = 0;
            break;

    }

    return ret;
}

int isRight( char c)
{
    int ret = 0;

    switch(c)
    {
        case '>':
        case ')':
        case '}':
        case '\'':
        case '\"':
            ret = 1;
            break;
        default:
            ret = 0;
            break;

    }

    return ret;
}

int match(char left, char right)
{
    int ret = 0;

    switch(left)
    {
        case '<':
            ret = (right == '>');
            break;
        case '(':
            ret = (right == ')');
            break;
        case '{':
            ret = (right == '}');
            break;
        case '\'':
            ret = (right == '\'');
            break;
        case '\"':
            ret = (right == '\"');
            break;
        default:
            ret = 0;
            break;

    }

    return ret;
}

int scanner(const char* code)
{
    LinkStack* stack = LinkStack_Create();
    int ret = 0;
    int i = 0;

    while( code[i] != '\0')
    {
        if( isLeft(code[i]) )
        {
            LinkStack_Push(stack, (void*)(code + i));
        }

        if(isRight(code[i]))
        {
            char* c = LinkStack_Pop(stack);

            if( (c == NULL) || !match(*c, code[i]) )
            {
                printf("%c does not match!\n",code[i]);
                ret = 0;
                break;
            }
        }

        i++;
    }

    if( (LinkStack_Size(stack) == 0) && (code[i] == '\0'))
    {
        printf("Succeed!\n");
        ret = 1;
    }
    else
    {
        printf("Invalid code!\n");
        ret = 0;
    }

    LinkStack_Destroy(stack);

    return ret;
}

int main(int argc, char *argv[])
{
    const char* code = "#include  int main() { int a[5][5]; int (*p)[4]; p = a[0]; printf(\"%d\\n\", &p[3][3] - &a[3][3]); return 0; }";

    scanner(code);

    return 0;
}

当需要检测成对出现但又互不相邻的事物时，可以使用栈的“后进先出”的特性，栈非常适合于需

要“就近匹配”的场合。