用C语言写解释器（二）——表达式求值

// in basic_io.h

#define memory_size (26)

typedef enum {

var_null = 0,

var_double,

var_string

} variant_type;

typedef char string[128];

typedef struct {

variant_type type;

union {

double i;

string s;

};

} variant;

extern variant memory[memory_size];

// in expression.h

typedef variant operand;

程序自带 a-z 26个可用变量，初始时都处于未赋值（ver_null)状态。所有变量必须先赋值再使用，否则就会报错！至于赋值语句的实现请参见后面语法分析的章节。

表达式中光有数值不行，还需要有操作符。在《一》中“表达式运算”一节已经给出了解释器需要实现的所有操作符，包括“算术运算”、“关系运算”和“逻辑运算”。下面给出程序中操作符的定义和声明：

/* 算数运算 */

oper_lparen = 0, // 左括号

oper_rparen, // 右括号

oper_plus, // 加

oper_minus, // 减

oper_multiply, // 乘

oper_divide, // 除

oper_mod, // 模

oper_power, // 幂

oper_positive, // 正号

oper_negative, // 负号

oper_factorial, // 阶乘

/* 关系运算 */

oper_lt, // 小于

oper_gt, // 大于

oper_eq, // 等于

oper_ne, // 不等于

oper_le, // 不大于

oper_ge, // 不小于

/* 逻辑运算 */

oper_and, // 且

oper_or, // 或

oper_not, // 非

/* 赋值 */

oper_assignment, // 赋值

oper_min // 栈底

} operator_type;

left2right,

right2left

} associativity;

int numbers; // 操作数

int icp; // 优先级

int isp; // 优先级

associativity ass; // 结合性

operator_type oper; // 操作符

} operator;

// in expression.c

static const operator operators[] = {

{2, 17, 1, left2right, oper_lparen}, // 左括号

{2, 17, 17, left2right, oper_rparen}, // 右括号

{2, 12, 12, left2right, oper_plus}, // 加

{2, 12, 12, left2right, oper_minus}, // 减

{2, 13, 13, left2right, oper_multiply}, // 乘

{2, 13, 13, left2right, oper_divide}, // 除

{2, 13, 13, left2right, oper_mod}, // 模

{2, 14, 14, left2right, oper_power}, // 幂

{1, 16, 15, right2left, oper_positive}, // 正号

{1, 16, 15, right2left, oper_negative}, // 负号

{1, 16, 15, left2right, oper_factorial}, // 阶乘

{2, 10, 10, left2right, oper_lt}, // 小于

{2, 10, 10, left2right, oper_gt}, // 大于

{2, 9, 9, left2right, oper_eq}, // 等于

{2, 9, 9, left2right, oper_ne}, // 不等于

{2, 10, 10, left2right, oper_le}, // 不大于

{2, 10, 10, left2right, oper_ge}, // 不小于

{2, 5, 5, left2right, oper_and}, // 且

{2, 4, 4, left2right, oper_or}, // 或

{1, 15, 15, right2left, oper_not}, // 非

// basic 中赋值语句不属于表达式！

{2, 2, 2, right2left, oper_assignment}, // 赋值

/* 最小优先级 */

{2, 0, 0, right2left, oper_min} // 栈底

你也许会问为什么需要 icp（incoming precedence）、isp（in-stack precedence） 两个优先级，现在不用着急，以后会详细解释！

现在操作数（operand）和操作符（operator）都有了，一个表达式就是由它们组合构成的，我们就统称它们为标记（token）。在程序中定义如下：

token_operand = 1,

token_operator

} token_type;

token_type type;

operand var;

operator ator;

} token;

typedef struct tlist {

token token;

struct tlist *next;

} token_list, *ptlist;

我们平时习惯将表达式符写作：operand operator operand（比如1+1），这是一个递归的定义，表达式本身也可作为操作数。像这种将操作符放在两个操作数之间的表达式称为中缀表达式，中缀表达式的好处是可读性强，操作数之间泾渭分明（尤其是手写体中）。但它有自身的缺陷：操作符的位置说明不了它在运算的先后问题。例如 1+2×3 中，虽然 + 的位置在 × 之前，但这并不表示先做加运算再做乘运算。为解决这个问题，数学中给操作符分了等级，级别高的操作符先计算（乘号的级别比加号高），并用括号提高操作符优先级。因此上例表达式的值是 7 而不是 (1+2)*3=9。

但对于计算机来说，优先级是一个多余的概念。就像上面提到的，中缀表达式中操作符的顺序没有提供运算先后关系的信息，这就好比用4个字节的空间仅保存1个字节数据——太浪费了！索性将操作符按照运算的先后排序：先计算的排最前面。此时操作符就不适合再放中间了，可以将它移到被操作数的后面：operand operand operator（比如 1 1 +）。上例中 1+2×3 就变化为 1 2 3 × +；(1+2)×3 变化成 1 2 + 3 ×，这种将操作符符放到操作数后面的表达式称为后缀表达式。同理还有将操作符符按照逆序放到操作数的前面的前缀表达式。

无论是前缀表达式还是后缀表达式，它们的优点都是用操作符的顺序来代替优先级，这样就可以舍弃括号等概念，化繁为简。

请看下面的梯等式计算，比较中缀表达式和后缀表达式的求值过程。

后缀表达式的求值方式：从头开始一个标记（token）一个标记地往后扫描，碰到操作数时先放到一个临时的空间里；碰到操作符就从空间里取出最后两个操作数，做相应的运算，然后将结果再次放回空间中。到了最后，空间中就只剩下操作数即运算结果！这个中缀表达式求值类似，只不过中缀表达式操作数取的是前后各一个。下面的代码是程序中后缀表达式求值的节选，其中只包含加法运算，其他运算都是类似的。

variant eval ( const char expr[] )

{

// ...

// 一些变量的定义和声明

// 将中缀表达式转换成后缀表达式

// 转换方法将在后续文章中介绍

list = infix2postfix ();

while ( list ) {

// 取出一个 token

p = list;

list = list->next;

// 如果是操作数就保存到 stack 中

if ( p->token.type == token_operand ) {

p->next = stack;

stack = p;

continue;

}

// 如果是操作符...

switch ( p->token.ator.oper ) {

// 加法运算

case oper_plus:

// 取出 stack 中最末两个操作数

op2 = stack;

op1 = stack = stack->next;

if ( op1->token.var.type == var_double &&

op2->token.var.type == var_double ) {

op1->token.var.i += op2->token.var.i;

} else {

// 字符串的加法即合并两个字符串

// 如果其中一个是数字则需要先转换为字符串

if ( op1->token.var.type == var_double ) {

sprintf ( s1, "%g", op1->token.var.i );

strcpy ( s1, op1->token.var.s );

if ( op2->token.var.type == var_double ) {

sprintf ( s2, "%g", op2->token.var.i );

strcpy ( s2, op2->token.var.s );

op1->token.type = var_string;

strcat ( s1, s2 );

strcpy ( op1->token.var.s, s1 );

free ( op2 );

break;

// 其他操作符方法类似

default:

// 无效操作符处理

free ( p );

value = stack->token.var;

free ( stack );

// 最后一个元素即表达式的值

return value;

这一篇文章主要介绍了表达式中的操作符、操作数在程序内部的表示方法、后缀表达式的相关知识以及后缀表达式求值的方法。在下一篇文章中将着重介绍如何将中缀表达式转换成后缀表达式，请关注《用c语言写解释器（三）》。