用C語言寫解釋器（三）——中綴轉字尾

比如将中綴表達式 5 * ((10 - 1) / 3) 轉換成字尾表達式為 5 10 1 - 3 / *。其中數字 5 10 1 3 仍然按照原先的順序排列，而操作符的順序變為 - / ×，這意味着減号最先計算、其次是除号、最後才是乘号。也許你還在擔心如何将操作符從兩個操作數的中間移到它們的後邊。其實不用擔心，在完成了排序工作後你就發現它已經跑到操作數的後面了 ^_^。

從中綴表達式 1+2×3+4 中逐個擷取操作符，依次是 + × +。如果目前操作符的優先級不大于前面的操作符時，前面操作符就要先輸出。比如例子中的第二個加号，它前面是乘号，是以乘号從這個隊伍中跑到輸出的隊伍中當了“老大”；此時第二個加号再前面的加号比較，仍然沒有比它大，是以第一個加号也排到新隊伍中去了；最後隊伍中隻剩下加号自己了，是以它也走了。得到新隊伍裡的順序 × + + 就是所求解。下面的表格中詳細展示每一個步驟。

序号

輸入

臨時空間

輸出

1

+

2

×

3

+ ×

4

+ × +

5

+ +

6

× +

7

× + +

相信你心裡還是牽挂着那些操作數。很簡單，如果碰到的是操作符就按上面的規則處理，如果是操作數就直接輸出！下面的表格加上了操作數，将輸出完整的字尾表達式。

1 2

1 2 3

8

1 2 3 ×

9

1 2 3 × +

10

1 2 3 × + 4

11

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 = null;

while ( stack->token.ator.isp >= p->token.ator.icp ) {

tail->next = stack;

tail = tail->next;

p->next = stack;

stack = p;

break;

while ( stack ) {

if ( p->token.ator.oper != oper_min ) {

return list;

上一節介紹了中綴轉字尾的方法。其中關鍵的部分就是比較兩個操作符的優先級大小。通常情況下這都很簡單：比如乘除的優先級比加減大，但括号需要特殊考慮。

中綴表達式中用括号來提升運算符的優先級，是以左括号正在放入（incoming）臨時空間時優先級比任何操作符都大；一旦左括号已經放入（in-stack）空間中，此時它優先級如果還是最大，那無論什麼操作符過來它就馬上被踢出去，而我們想要的是任何操作符過來都能順利放入臨時空間，是以它放入空間後優先級需要變為最小。這意味着左括号在放入空間前後的優先級是不同的，是以我們需要用兩個優先級變量 icp 和 isp 來分别記錄操作符在兩個狀态下的優先級（還記得上一篇的問題嗎）。

另一個是右括号，它本身和優先級無關，它會将臨時空間裡的操作符一個個輸出，直到碰到左括号為止。下面是本程式中中綴轉字尾的代碼（有删減）。

在上面的代碼中你會看到一個陌生的函數 next_taken() 。它會從中綴表達式中獲得一個标記，方法類似從字元串中提取單詞（參看課後習題）。在本程式中能識别的标記除了操作符，還有純數字、字元串、變量名等操作數。唯一要注意的就是操作符和操作數之間可以存在零到多個空格。下面是參考代碼（有删減）。

static token next_token ()

token token = {0};

string s;

int i;

if ( e == null ) {

return token;

// 去掉前導空格

while ( *e && isspace(*e) ) {

e++;

if ( *e == 0 ) {

if ( *e == '"' ) {

// 字元串

token.type = token_operand;

token.var.type = var_string;

for ( i = 0; *e && *e != '"'; i++ ) {

token.var.s[i] = *e;

} else if ( isalpha(*e) ) {

// 如果首字元為字母則有兩種情況

// 1. 變量

// 2. 邏輯操作符

token.type = token_operator;

for ( i = 0; isalnum(*e); i++ ) {

s[i] = toupper(*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.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 );

goto errorhandler;

} else if ( isdigit(*e) || *e == '.' ) {

// 數字

token.var.type = var_double;

for ( i = 0; isdigit(*e) || *e == '.'; i++ ) {

s[i] = *e;

if ( sscanf ( s, "%lf", &token.var.i ) != 1 ) {

// 讀取數字失敗！

// 錯誤處理

// 剩下算數運算符和關系運算符

switch (*e) {

case '(':

token.ator = operators[oper_lparen];

// ...

// 此處省略其他操作符的代碼

default:

// 不可識别的操作符

before = token;

本章主要介紹中綴表達式轉字尾表達式的方法，并給出了相應的參考代碼。和前一篇文章結合起來就完成了解釋器中“表達式求值”和“記憶體管理”兩部分，在下一篇文章中我們将介紹語句的解析，其中包含了輸入/輸出、分支以及循環語句，請關注《用c語言寫解釋器（四）》。