跳至主要内容

用C语言写解释器（三）


用C语言写解释器（三）——中缀转后缀



redraiment, 2009-11-01


操作符排序



　　如果你忘记了后缀表达式的概念，赶紧翻回上一篇《用C语言写解释器（二）》回顾一下。简单地说，将中缀表达式转换成后缀表达式，就是将操作符的执行顺序由“优先级顺序”转换成“在表达式中的先后顺序”。因此，所谓的中缀转后缀，其实就是给原表达式中的操作符排序。
　　比如将中缀表达式 5 * ((10 - 1) / 3) 转换成后缀表达式为 5 10 1 - 3 / *。其中数字 5 10 1 3 仍然按照原先的顺序排列，而操作符的顺序变为 - / ×，这意味着减号最先计算、其次是除号、最后才是乘号。也许你还在担心如何将操作符从两个操作数的中间移到它们的后边。其实不用担心，在完成了排序工作后你就发现它已经跑到操作数的后面了 ^_^。
　　从中缀表达式 1+2×3+4 中逐个获取操作符，依次是 + × +。如果当前操作符的优先级不大于前面的操作符时，前面操作符就要先输出。比如例子中的第二个加号，它前面是乘号，因此乘号从这个队伍中跑到输出的队伍中当了“老大”；此时第二个加号再前面的加号比较，仍然没有比它大，因此第一个加号也排到新队伍中去了；最后队伍中只剩下加号自己了，所以它也走了。得到新队伍里的顺序 × + + 就是所求解。下面的表格中详细展示每一个步骤。
序号输入临时空间输出
1+

2×+
3++ ×
4
+ × +
5
+ +×
6
+× +
7

* + +
　　相信你心里还是牵挂着那些操作数。很简单，如果碰到的是操作符就按上面的规则处理，如果是操作数就直接输出！下面的表格加上了操作数，将输出完整的后缀表达式。
序号输入临时空间输出
11

2+
1
32+1
4×+1 2
53+ ×1 2
6++ ×1 2 3
7
+ × +1 2 3
8
+ +1 2 3 ×
94+1 2 3 × +
10
+1 2 3 × + 4
11

1 2 3 × + 4 +
　　得到最终结果 1 2 3 × + 4 + 就是所求的后缀表达式。下面是程序中的参考代码（有删减）。

操作符优先级

　　上一节介绍了中缀转后缀的方法。其中关键的部分就是比较两个操作符的优先级大小。通常情况下这都很简单：比如乘除的优先级比加减大，但括号需要特殊考虑。
　　中缀表达式中用括号来提升运算符的优先级，因此左括号正在放入（incoming）临时空间时优先级比任何操作符都大；一旦左括号已经放入（in-stack）空间中，此时它优先级如果还是最大，那无论什么操作符过来它就马上被踢出去，而我们想要的是任何操作符过来都能顺利放入临时空间，因此它放入空间后优先级需要变为最小。这意味着左括号在放入空间前后的优先级是不同的，所以我们需要用两个优先级变量 icp 和 isp 来分别记录操作符在两个状态下的优先级（还记得上一篇的问题吗）。
　　另一个是右括号，它本身和优先级无关，它会将临时空间里的操作符一个个输出，直到碰到左括号为止。下面是本程序中中缀转后缀的代码（有删减）。
// in expression.c
PTLIST infix2postfix ()
{
    PTLIST list = NULL, tail, p;
    PTLIST stack = NULL;

    // 初始时在临时空间放一个优先级最低的操作符
    // 这样就不用判断是否为空了，方便编码
    stack = (PTLIST)calloc(1, sizeof(TOKEN_LIST));
    stack->next = NULL;
    stack->token.type = token_operator;
    stack->token.ator = operators[oper_min];

    // before 为全局变量，用于保存之前的操作符
    // 具体作用参看下面的章节
    memset ( &before, 0, sizeof(before) );
    for (;;) {
        p = (PTLIST)calloc(1, sizeof(TOKEN_LIST));
        // calloc 自动初始化
        p->next = NULL;
        p->token = next_token ();
        if ( p->token.type == token_operand ) {
            // 如果是操作数，就不用客气，直接输出
            if ( !list ) {
                list = tail = p;
            } else {
                tail->next = p;
                tail = p;
            }
        } else if ( p->token.type == token_operator) {
            if ( p->token.ator.oper == oper_rparen ) {
                // 右括号
                free ( p );
                while ( stack->token.ator.oper != oper_lparen ) {
                    p = stack;
                    stack = stack->next;
                    tail->next = p;
                    tail = p;
                    tail->next = NULL;
                }
                p = stack;
                stack = stack->next;
                free ( p );
            } else {
                while ( stack->token.ator.isp >= p->token.ator.icp ) {
                    tail->next = stack;
                    stack = stack->next;
                    tail = tail->next;
                    tail->next = NULL;
                }
                p->next = stack;
                stack = p;
            }
        } else {
            free ( p );
            break;
        }
    }
    while ( stack ) {
        p = stack;
        stack = stack->next;
        if ( p->token.ator.oper != oper_min ) {
            p->next = NULL;
            tail->next = p;
            tail = p;
        } else {
            free ( p );
        }
    }

    return list;
}


获取标识符



　　在上面的代码中你会看到一个陌生的函数 next_taken() 。它会从中缀表达式中获得一个标记，方法类似从字符串中提取单词（参看课后习题）。在本程序中能识别的标记除了操作符，还有纯数字、字符串、变量名等操作数。唯一要注意的就是操作符和操作数之间可以存在零到多个空格。下面是参考代码（有删减）。
// in expression.c
static TOKEN next_token ()
{
    TOKEN token = {0};
    STRING s;
    int i;

    if ( e == NULL ) {
        return token;
    }

    // 去掉前导空格
    while ( *e && isspace(*e) ) {
        e++;
    }

    if ( *e == 0 ) {
        return token;
    }

    if ( *e == '"' ) {
        // 字符串
        token.type = token_operand;
        token.var.type = var_string;
        e++;
        for ( i = 0; *e && *e != '"'; i++ ) {
            token.var.s[i] = *e;
            e++;
        }
        e++;
    } else if ( isalpha(*e) ) {
        // 如果首字符为字母则有两种情况
        // 1. 变量
        // 2. 逻辑操作符
        token.type = token_operator;
        for ( i = 0; isalnum(*e); i++ ) {
            s[i] = toupper(*e);
            e++;
        }
        s[i] = 0;
        if ( !strcmp ( s, "AND" ) ) {
            token.ator = operators[oper_and];
        } else if ( !strcmp ( s, "OR" ) ) {
            token.ator = operators[oper_or];
        } else if ( !strcmp ( s, "NOT" ) ) {
            token.ator = operators[oper_not];
        } else if ( i == 1 ) {
            token.type = token_operand;
            token.var = memery[s[0]-'A'];
            if ( token.var.type == var_null ) {
                memset ( &token, 0, sizeof(token) );
                fprintf ( stderr, "变量%c未赋值！\n", s[0] );
                exit ( EXIT_FAILURE );
            }
        } else {
            goto errorhandler;
        }
    } else if ( isdigit(*e) || *e == '.' ) {
        // 数字
        token.type = token_operand;
        token.var.type = var_double;
        for ( i = 0; isdigit(*e) || *e == '.'; i++ ) {
            s[i] = *e;
            e++;
        }
        s[i] = 0;
        if ( sscanf ( s, "%lf", &token.var.i ) != 1 ) {
            // 读取数字失败！
            // 错误处理
        }
    } else {
        // 剩下算数运算符和关系运算符
        token.type = token_operator;
        switch (*e) {
        case '(':
            token.ator = operators[oper_lparen];
            break;
        // ...
        // 此处省略其他操作符的代码
        default:
            // 不可识别的操作符
            break;
        }
        e++;
    }
    before = token;

    return token;
}

总结

　　本章主要介绍中缀表达式转后缀表达式的方法，并给出了相应的参考代码。和前一篇文章结合起来就完成了解释器中“表达式求值”和“内存管理”两部分，在下一篇文章中我们将介绍语句的解析，其中包含了输入/输出、分支以及循环语句，请关注《用C语言写解释器（四）》。

评论

发表评论

此博客中的热门博文

AutoHotKey 新手入门教程

AutoHotKey 真是一个好玩的工具！短短几行代码就是先了“窗口置顶”、“窗口透明”等功能，之前我还特意为此装了好几个小工具，现在都可以卸掉了。闲来无事，就把 Quick Start 翻译了一下，我没有逐字逐句地翻译，有时候我嫌原文罗嗦就用自己的话概括地描述了一下。 原文地址：http://www.autohotkey.com/docs/Tutorial.htm 教程目录 创建脚本 启动程序 模拟鼠标键盘 操纵窗口 输入 变量与剪切板 循环 操纵文件 其他特性 创建脚本 每个脚本都是一个纯文本文件，由一些能被 AutoHotKey.exe 执行的命令组成。一个脚本可能还包含 热键 和 热字符串 。如果没有热键和热字符串，脚本在启动的时候就会从头依次执行到尾。 创建一个新的脚本： 下载 并安装 AutoHotkey。 右击鼠标，选择 新建 -> 文本文档 。 输入文件名并确保以 .ahk 结尾。例如：Test.ahk。 右击文件，选择 编辑脚本 。 输入以下内容：#space::Run www.google.com 上一行的第一个字符 "#" 代表键盘上的 Windows 键；所以 #space 表示在按住 Windows 键后再按空格键。"::" 后面的命令会在热键激活后执行，在本例中则会打开谷歌主页。继续按下面步骤操作，来执行这个脚本： 保存并关闭该文件。 双击该文件来启动它。在系统托盘里会出现一个新图标。 按下 Windows 和空格键，网页会在默认的浏览器里打开。 右击系统托盘里的绿色图标可以退出或编辑当前脚本。 注意： 可以同时启动多个脚本，并且在系统托盘里都会有一个相应的图标。 每个脚本都能定义多个 热键 和 热字符串 。 想让某个脚本开机即启动，可以将它的 快捷方式放到开始菜单的启动目录里 。 启动程序 命令 Run 可以运行程序、打开文档、网页链接或快捷键。请参看以下示例： Run Notepad Run C:\My Documents\Address List.doc Run C:\My Documents\My Shortcut.lnk Run www.yahoo.com Run mailto:someone@somedoma...
发表评论
阅读全文

好玩的数学——吉普赛读心术解密

好玩的数学——吉普赛读心术解密 redraiment, 2009-11-19 神奇的吉普赛读心术 　　闲着无聊窜寝室，看到一个同学在玩一个 flash 游戏：吉普赛读心术（ http://gb.cri.cn/mmsource/flash/2006/04/10/er060410001.swf ）。规则如下： 任意选择一个两位数（或者说，从10~99之间任意选择一个数），把这个数的十位与个位相加，再把任意选择的数减去这个和。例如：你选的数是23，然后2+3=5，然后23-5=18 在图表中找出与最后得出的数所相应的图形，并把这个图形牢记心中，然后点击水晶球。你会发现，水晶球所显示出来的图形就是你刚刚心里记下的那个图形。 　　咋看之下觉得很神奇，但仔细把玩两三回后你就会发现其中的奥秘： 右边的图标每次都会改变； 9、18、27、...、81 这9个图标永远是一样的。 　　假设你选择的两位数是 ab（即 ab=a×10+b），其中 1≤a≤9, 0≤b≤9 。按照规则计算就是 (a×10+b)-(a+b)=9×a，结果是 9 的倍数，∵ 1≤a≤9 ∴ 结果为 9、18、27、...、81 中的任意一个。又∵ 这9个图标是一样的，∴ 水晶球神奇地知道你记的图标。 手指计算器 　　无独有偶，记的小学数学课上老师教我们用手指计算任意两个5-10之间的数的积。 　　例如 6×8 ，一只手伸出 6-5=1 根指头，另一只手伸出 8-5=3 根指头。1+3=4，4 就是积的十位数；把两手弯曲的指头数相乘得 4×2=8，8 是积的个位数。则 6×8=48。 　　道理和上面相同：a×b=[(a-5)+(b-5)]×10+(10-a)×(10-b) 神秘的失踪 　　做这道题一定要的亲自动手才有滋味！否则就会像浮光掠影，印象不深。 　　将一个正方形分割成 7×7=49 的小方格，并按下图将它们分为“甲、乙、丙、丁、戊”五部分。 　　然后，甲块不动、乙块和丙块对调、戊块上移、丁块右移。得到新图如下： 　　经过这样重新组合拼成的新正方形，中间奇迹般地空出了一个洞！ 　　实际上这只不过是一个小戏法，上面的新图形并不是真的正方形。 观察原始图可知 △ABC 和 △AED 是相似三角形 ∴ DE:CB=AD:AC=4:7 ∴ DE=8/7 ∴ EF=DE+DF=36/7 ∴ 上图...
发表评论
阅读全文

JavaScript中的字符串乘法

JavaScript中的字符串乘法 redraiment, Date 原文 原文地址： http://www.davidflanagan.com/2009/08/string-multipli.html 原作者：David Flanagan In Ruby, the "*" operator used with a string on the left and a number on the right does string repetition. "Ruby"*2 evaluates to "RubyRuby", for example. This is only occasionally useful (when creating lines of hyphens for ASCII tables, for example) but it seems kind of neat. And it sure beats having to write a loop and concatenate n copies of a string one at a time--that just seems really inefficient. I just realized that there is a clever way to implement string multiplication in JavaScript: String.prototype.times = function(n) {     return Array.prototype.join.call({length:n+1}, this); }; "js".times(5) // => "jsjsjsjsjs" This method takes advantage of the behavior of the  Array.join()  method for arrays that have undefined elements. But it doesn't even bother creating an array with n+1 undefined ele...
发表评论
阅读全文