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

声明

为提高教学质量，我所在的学院正在筹划编写C语言教材。《用C语言写解释器》系列文章经整理后将收入书中“综合实验”一章。因此该系列的文章主要阅读对象定为刚学完C语言的学生（不要求有数据结构等其他知识），所以行文比较罗嗦，请勿见怪。本人水平有限，如有描述不恰当或错误之处请不吝赐教！特此声明。

操作符排序

如果你忘记了后缀表达式的概念，赶紧翻回上一篇《用C语言写解释器（二）》回顾一下。简单地说，将中缀表达式转换成后缀表达式，就是将操作符的执行顺序由“优先级顺序”转换成“在表达式中的先后顺序”。因此，所谓的中缀转后缀，其实就是给原表达式中的操作符排序。

比如将中缀表达式 5 * ((10 - 1) / 3) 转换成后缀表达式为 5 10 1 - 3 / *。其中数字 5 10 1 3 仍然按照原先的顺序排列，而操作符的顺序变为 - / ×，这意味着减号最先计算、其次是除号、最后才是乘号。也许你还在担心如何将操作符从两个操作数的中间移到它们的后边。其实不用担心，在完成了排序工作后你就发现它已经跑到操作数的后面了 ^_^。

从中缀表达式 1+2×3+4 中逐个获取操作符，依次是 + × +。如果当前操作符的优先级不大于前面的操作符时，前面操作符就要先输出。比如例子中的第二个加号，它前面是乘号，因此乘号从这个队伍中跑到输出的队伍中当了“老大”；此时第二个加号再前面的加号比较，仍然没有比它大，因此第一个加号也排到新队伍中去了；最后队伍中只剩下加号自己了，所以它也走了。得到新队伍里的顺序 × + + 就是所求解。下面的表格中详细展示每一个步骤。

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

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

// 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;
}

操作符优先级

上一节介绍了中缀转后缀的方法。其中关键的部分就是比较两个操作符的优先级大小。通常情况下这都很简单：比如乘除的优先级比加减大，但括号需要特殊考虑。

中缀表达式中用括号来提升运算符的优先级，因此左括号正在放入（incoming）临时空间时优先级比任何操作符都大；一旦左括号已经放入（in-stack）空间中，此时它优先级如果还是最大，那无论什么操作符过来它就马上被踢出去，而我们想要的是任何操作符过来都能顺利放入临时空间，因此它放入空间后优先级需要变为最小。这意味着左括号在放入空间前后的优先级是不同的，所以我们需要用两个优先级变量 icp 和 isp 来分别记录操作符在两个状态下的优先级（还记得上一篇的问题吗）。

另一个是右括号，它本身和优先级无关，它会将临时空间里的操作符一个个输出，直到碰到左括号为止。下面是本程序中中缀转后缀的代码（有删减）。

获取标识符

在上面的代码中你会看到一个陌生的函数 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 = memory[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语言写解释器（四）》。

版权声明

请尊重原创作品。转载请保持文章完整性，并以超链接形式注明原始作者“redraiment”和主站点地址，方便其他朋友提问和指正。

联系方式

我的邮箱，欢迎来信（redraiment@gmail.com）
我的Blogger（子清行）：http://redraiment.blogspot.com/
我的Google Sites（子清行）：https://sites.google.com/site/redraiment
我的CSDN博客（梦婷轩）：http://blog.csdn.net/redraiment
我的百度空间（梦婷轩）：http://hi.baidu.com/redraiment