C语言编程--二叉树--构建解析树

完整代码示例

• 构建解析树
• 操作解析树
  • 生成对应的中缀表达式(中序遍历解析树)
  • 生成对应的后缀表达式(后序遍历解析树)
  • 生成对应的求值机器码(后序历解析树)

框架代码：

#include <stdio.h>
#include <stdlib.h>char *a;int i;typedef struct Tnode* link;struct Tnode {char token;link l;link r;
};link NEW(char token, link l, link r);
link parse();
void visit(link h);
void trav_in(link h, void(*visit)(link));
void trav_post(link h, void(*visit)(link));
void visit_codegen(link h);int main(){i = 0;char input[] = {'*', '+', 'a', '*', '*', 'b', 'c', '+', 'd', 'e', 'f'};a = input;//构建前缀表达式对应的解析树link root = parse();// show(root, 4);//中序遍历得到对应的中缀表达式trav_in(root, visit);printf("\n");//后序遍历得到对应的后缀表达式trav_post(root, visit);printf("\n");//后序遍历生成对应的求值机器码trav_post(root, visit_codegen);return 0;
}

任务1：构建前缀表达式的解析树

link NEW(char token, link l, link r){link x = malloc(sizeof(*x));x->token = token;x->l = l;x->r = r;return x;
}
link parse(){char t = a[i++];link x = NEW(t, NULL, NULL);if ((t == '*') || t == '+') {x->l = parse();x->r = parse();}return x;
}

任务2：生成对应的中缀表达式

中序遍历解析树

void visit(link h){printf("%c ", h->token);
}void trav_in(link h, void(*visit)(link)){if (h == NULL) {return ;}trav_in(h->l,visit);(*visit)(h);trav_in(h->r, visit);
}

任务3：生成对应的后缀表达式

后序历解析树

void trav_post(link h, void(*visit)(link)){if (h == NULL) {return ;}trav_post(h->l,visit);trav_post(h->r, visit);(*visit)(h);
}

任务4：生成对应的求值机器码

后序历解析树

void visit_codegen(link h){if (h == NULL) {return ;}if (h->token == '*') {printf("MULTIPLY\n");}else if (h->token == '+') {printf("ADD\n");}else {printf("LOAD %c\n", h->token);}
}