Chinaunix首页 | 论坛 | 博客
  • 博客访问: 256591
  • 博文数量: 52
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 1538
  • 用 户 组: 普通用户
  • 注册时间: 2013-04-24 07:45
个人简介

生活就像海洋,只有意志坚强的人,才能到达彼岸。

文章存档

2013年(52)

分类: C/C++

2013-08-17 17:09:07

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

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{
    匹配失败,报错
    }
}


点击(此处)折叠或打开

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

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

  6. int isLeft( char c)
  7. {
  8.     int ret = 0;
  9.     
  10.     switch(c)
  11.     {
  12.         case '<':
  13.         case '(':
  14.         case '{':
  15.         case '\'':
  16.         case '\"':
  17.             ret = 1;
  18.             break;
  19.         default:
  20.             ret = 0;
  21.             break;    
  22.     
  23.     }
  24.     
  25.     return ret;
  26. }

  27. int isRight( char c)
  28. {
  29.     int ret = 0;
  30.     
  31.     switch(c)
  32.     {
  33.         case '>':
  34.         case ')':
  35.         case '}':
  36.         case '\'':
  37.         case '\"':
  38.             ret = 1;
  39.             break;
  40.         default:
  41.             ret = 0;
  42.             break;    
  43.     
  44.     }
  45.     
  46.     return ret;
  47. }

  48. int match(char left, char right)
  49. {
  50.     int ret = 0;
  51.     
  52.     switch(left)
  53.     {
  54.         case '<':
  55.             ret = (right == '>');
  56.             break;
  57.         case '(':
  58.             ret = (right == ')');
  59.             break;
  60.         case '{':
  61.             ret = (right == '}');
  62.             break;
  63.         case '\'':
  64.             ret = (right == '\'');
  65.             break;
  66.         case '\"':
  67.             ret = (right == '\"');
  68.             break;
  69.         default:
  70.             ret = 0;
  71.             break;    
  72.     
  73.     }
  74.     
  75.     return ret;
  76. }

  77. int scanner(const char* code)
  78. {
  79.     LinkStack* stack = LinkStack_Create();
  80.     int ret = 0;
  81.     int i = 0;
  82.     
  83.     while( code[i] != '\0')
  84.     {
  85.         if( isLeft(code[i]) )
  86.         {
  87.             LinkStack_Push(stack, (void*)(code + i));    
  88.         }    
  89.         
  90.         if(isRight(code[i]))
  91.         {
  92.             char* c = LinkStack_Pop(stack);
  93.             
  94.             if( (c == NULL) || !match(*c, code[i]) )    
  95.             {
  96.                 printf("%c does not match!\n",code[i]);
  97.                 ret = 0;
  98.                 break;    
  99.             }
  100.         }
  101.         
  102.         i++;
  103.     }
  104.     
  105.     if( (LinkStack_Size(stack) == 0) && (code[i] == '\0'))
  106.     {
  107.         printf("Succeed!\n");
  108.         ret = 1;    
  109.     }
  110.     else
  111.     {
  112.         printf("Invalid code!\n");
  113.         ret = 0;    
  114.     }
  115.     
  116.     LinkStack_Destroy(stack);
  117.     
  118.     return ret;
  119. }

  120. int main(int argc, char *argv[])
  121. {
  122.     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; }";
  123.     
  124.     scanner(code);
  125.     
  126.     return 0;
  127. }
当需要检测成对出现但又互不相邻的事物时,可以使用栈的“后进先出”的特性,栈非常适合于需

要“就近匹配”的场合。

阅读(2862) | 评论(1) | 转发(1) |
给主人留下些什么吧!~~

CU博客助理2013-10-10 11:41:50

嘉宾点评: 对于使用栈来解决字符匹配,相关代码已有不少,但博主将算法思路、算法框架和代码实现简明地写出来让人一看则明。值得赞扬的是博文内容详实、版面工整,让人读得舒服,学得快速。希望博主能够为大家写就更多的好文。(感谢您参与“原创博文评选”获奖结果即将公布)