波蘭表示法與表達式樹

來自專欄 Milo的編程

昨晚撰寫答案《Milo Yip：怎麼用 C 語言畫出二叉樹的圖形？》，以 ASCII 字元列印任意深度的滿二叉樹（full binary tree）。評論中問及如何列印非滿二叉樹。我記起，整個滿二叉樹可存儲在單個一維數組。那麼，可以先把非滿二叉樹的節點寫到一維數組，然後修改列印程序，如果數組中存有該序號的節點，才列印該節點及其指向父節點的連線，否則列印空白佔位字元。

我的回評或過於簡短，不夠清晰，因此我想用實際代碼解釋。然而，怎樣建一個非滿二叉樹？我想到可以寫一個簡單的表達式解析器，支持加減乘除，不支持負數操作數。程序也能列印出其表達式樹。

最簡單的表達式語法，莫過於波蘭表示法（Polish notation）。波蘭表示法又稱為前綴表示法，即運算符寫在前面。波蘭表示法的特點是不需要括弧。例如，表達式(1 + 2) * (3 - 4) 的波表示法是 * + 1 2 - 3 4。

（題圖 photo by Elliott Engelmann）

首先設計解析後的數據結構，表達式樹的節點可能是運算符或操作數：

typedef enum { NUM, ADD, SUB, MUL, DIV } Type;typedef struct NodeTag { union { double number; struct NodeTag *children[2]; } u; Type type;} Node;

因為一個節點不會同時為運算符或操作數，採用 union可能節省一點內存。

波蘭表示法的解釋器非常簡單，可通過遞歸實現，不需要額外的數據結構：

Node* parse(char** s) { while (isspace(**s)) (*s)++; if (**s == ) return NULL; else { Node* n = (Node*)calloc(1, sizeof(Node)); if (isdigit(**s)) { n->type = NUM; n->u.number = strtod(*s, s); } else { int i; switch (**s) { case +: n->type = ADD; break; case -: n->type = SUB; break; case *: n->type = MUL; break; case /: n->type = DIV; break; default: release(n); return NULL; } (*s)++; for (i = 0; i < 2; i++) if ((n->u.children[i] = parse(s)) == NULL) { release(n); return NULL; } } return n; }}

每次有內存分配，都匹對釋放，也是遞歸：

void release(Node* n) { int i; if (n->type != NUM) for (i = 0; i < 2; i++) if (n->u.children[i]) release(n->u.children[i]); free(n);}

然後我們可以列印中綴表示法：

#define OPERATOR_CHAR(n) ("+-*/"[n->type - ADD])void printInfix(const Node *n) { if (n->type == NUM) printf("%lg", n->u.number); else { putchar((); printInfix(n->u.children[0]); printf(" %c ", OPERATOR_CHAR(n)); printInfix(n->u.children[1]); putchar()); }}

以及對表達式樹求值：

double eval(const Node* n) { switch (n->type) { case ADD: return eval(n->u.children[0]) + eval(n->u.children[1]); case SUB: return eval(n->u.children[0]) - eval(n->u.children[1]); case MUL: return eval(n->u.children[0]) * eval(n->u.children[1]); case DIV: return eval(n->u.children[0]) / eval(n->u.children[1]); case NUM: return n->u.number; }}

編寫main()：

int main(int argc, char** argv) { if (argc != 2) return printf("Help: pntree "+ * 1 2 3""); else { char** p = &argv[1]; Node* root = parse(p); if (root) { printInfix(root); printf(" = %lg
", eval(root)); release(root); } else return printf("Invalid input
"); }}

測試：

$ ./pntree "* + 1 2 - 3 4"((1 + 2) * (3 - 4)) = -3

接下來，我們要修改之前的滿二叉樹列印程序。和之前的需求不一樣，樹的深度是隨輸入改變的，所以需先求出最大高度（深度）：

int maxDepth(const Node* n) { if (n->type == NUM) return 1; else { int maximum = 0, i, d; for (i = 0; i < 2; i++) if (maximum < (d = maxDepth(n->u.children[i]))) maximum = d; return maximum + 1; }}

接著是分配一個 大小的數組，把序號映射至節點：

void fillMap(Node** map, Node* n, int index) { int i; map[index] = n; if (n->type != NUM) for (i = 0; i < 2; i++) fillMap(map, n->u.children[i], index * 2 + i + 1);}void printTree(Node* n) { int depth = maxDepth(n), i, j, index; Node** map = (Node**)calloc((1 << depth) - 1, sizeof(Node*)); fillMap(map, n, 0); // ... free(map);}

這裡和原答案一樣，使用廣度優先遍歷去列印節點。先忽略連線的部分：

void putchars(char c, int n) { while (n--) putchar(c);}int printNode(Node* n, int w) { if (n->type == NUM) return printf("%*lg", w, n->u.number); else return printf("%*c", w, "+-*/"[n->type - ADD]);}void printTree(Node* n) { int depth = maxDepth(n), i, j, index; Node** map = (Node**)calloc((1 << depth) - 1, sizeof(Node*)); fillMap(map, n, 0); for (j = 0, index = 0; j < depth; j++) { int w = 1 << (depth - j + 1); // Curve to parent ... // Node content for (i = 0; i < 1 << j; i++, index++) if (map[index]) putchars( , w * 2 - printNode(map[index], w)); else putchars( , w * 2); putchar(
); } free(map);}

putchars(c, n)連續列印 n 個相同字元。

printNode(n, w) 列印節點的內容（運算符或操作數），列印寛度為w個字元，返回實際列印字元數目。

在 printTree(n)中，採用之前相同的兩層循環，在內循環里遞增序號index，並獲取當前節點map[index]。若該序號沒有節點，則列印空白字元。

最終結果：

本文簡單示範如何實現波蘭表示法的計算器，並列印其非滿二叉表達式樹。此方法需要 的時間和空間複雜度。如實際節點數量遠低於 ，可考慮用哈希表存儲該映射表，但時間複雜度始終無法降低。另一簡單優化方法，是用二維數組存儲字元輸出，那就只需繪畫表達式樹含有的節點。

完整代碼位於 pntree.c。