目录

关于表达式树

由后缀表达式构建表达式树的方法

分析题面要求，进行定义

加括号规则

AC代码

C2第三次作业的第一题，题面如下：

【问题描述】 将由数字和四则运算符组成的后缀表达式变换为中缀表达式。 输入的后缀表达式包含的运算符不超过15个。 要求转换后的中缀表达式中不应出现不必要的括号。 例如，整个表达式两端的括号要省略，不影响原计算结果的括号要省略。 【输入形式】 程序从标准输入上读入一行字符串，是一个合法的后缀表达式，数字和运算符之间由空格分隔。 其中的数字可以是整数，也可以是带有小数部分的浮点数。 【输出形式】 向标准输出打印结果。 输出只有一行，是转换后的中缀表达式，并且 1. 各分量（包括括号）紧密输出，不使用空格进行分隔； 2. 在转换前后各运算数的出现顺序不变； 3. 浮点数保留输入时的小数位数。 【输入样例】 4 7 - 2.1 5 + * 7.1 9 - / 【输出样例】 (4-7)*(2.1+5)/(7.1-9) 【时间限制】 1s 【空间限制】 65536KB 【上传文件】 上传c语言源程序，文件名为convert.c。

因为感觉这个还是比较有用的所以单独发一篇好了。毕竟数据结构之后我很少写关于树的代码了（本身也不咋会），而且这题也算是这次里面差不多很复杂的一题了。至于吐槽我写C2第三周的时候再吐槽。

之前数据结构写过表达式求值，方法是将中缀表达式转换为后缀表达式然后计算，这一步用到的数据结构主要是栈。而且还写过将后缀表达式转换成表达式树。那么接下来这次终于是要写表达式树还原中缀表达式了。不过太久没接触这东西了，所以写这题的时候还是参考了网上的一些内容，并且翻阅了以前写的代码，才完成了这次的作业并且顺利A了。

关于表达式树

（1）表达式树的特点：所有叶节点都是操作数，即数字。而其他节点为运算符，在我们这里就是+-*/了。由于这些都是二元运算符，所以这里表达式树是二叉树。

（2）表达式树的前序遍历为前缀表达式，中序遍历为中缀表达式，后序遍历为后缀表达式。这样我们也能理解（1）中为何叶节点不能为运算符，因为其左右连接的是运算符左边和右边的表达式。

（3）由后缀表达式构建表达式树最为方便。如果给出了其他表达式，则需要先转换为后缀表达式才能构建。我们这题就不用转换了。

由后缀表达式构建表达式树的方法

（1）依次读入每个符号，如果为操作数，我们就建立一个树的节点，并且将其指针压入栈中。

（2）若符号为运算符，从栈中弹出两棵子树T1和T2，先弹出T1。然后形成一棵一个以该运算符为根的树，T1为右子树，T2为左子树。（栈的特性先进后出，后进先出，所以T1为较后出现的子树，即出现在运算符右边，所以是右子树）将该树压入栈中，继续读取。

分析题面要求，进行定义

首先数字可能是整数或浮点数，而且浮点数保留输入时的小数位数，因此1.0000这种不用化简。所以保存时直接用字符串保存即可。

由此，树的定义如下：

讯享网/*表达式树的定义*/ struct node { char num[LENGTH]; struct node *lchild; struct node *rchild; }; typedef struct node Node; typedef struct node* BTNodeptr;

另外我们需要输出中缀表达式，所以需要的是中序遍历，函数声明如下（命名懒得改了）：

void freeT(BTNodeptr p); //释放表达式树 void travel(BTNodeptr p); //中序遍历，输出中缀表达式以及添加括号 BTNodeptr buildT(char s[]); //建立表达式树

此外还需要栈来保存指针，简易写一下即可。

讯享网

讯享网/*存放表达式树的指针的栈*/ BTNodeptr tree[SUM]; int top = 0; void push(BTNodeptr p) { tree[++top] = p; } BTNodeptr pop() { return tree[top--]; }

加括号规则

根据题目要求，我们不一定要完全还原表达式的计算过程。例如表达式ab+cde+，其正确中缀表达式应该为(a+b)*(c*(d+e))，因为后缀表达式是先计算c*(d+e)，再将其与a+b相乘的。

而题目要求是不影响原计算结果的括号要省略，所以我们应该输出(a+b)*c*(d+e)。

加括号需要满足下面两个判断：

（1）对于当前节点（非叶节点，即为运算符的节点），若其左节点也为运算符，且其优先级小于当前节点，则为左节点的表达式添加括号。

优先级小于之时，显然应该添加括号。比如左子树表达式为a-b（这里a不一定为一个数，可能为一个表达式），当前节点为*，那么先计算a-b，应该添加括号，否则会改变运算顺序影响结果。

优先级用到小于，是因为左子树的表达式在运算符之前计算，如果运算符相等，是不必添加括号的。例如：左子树表达式为a*b，当前节点运算符为/，那么a*b外层无论添加不添加括号都不会影响运算顺序，自然不会影响结果。

（2）对于当前节点（非叶节点，即为运算符的节点），若其右节点也为运算符，且其优先级小于当前节点，则为右节点的表达式添加括号；若优先级相等，且当前节点运算符为'-'或者'/'，则也为右节点的表达式添加括号。

运算符优先级小于自然好理解。而等于之时需要判断，与左子树不同，这是因为右子树的表达式在运算符之后计算。如果优先级相等，括号是用来表示运算顺序的。我们一开始举了个例子就是如此，ab+cde+。但是当前节点为*或+时，a*b*c和a*(b*c)虽然改变了运算顺序，但是并不会改变运算结果。而当前节点为-或/，a/b/c和a/(b/c)结果就完全不同了。所以这是这题特殊的地方。

我们用以下三个函数来判断：

/*判断符号优先级*/ bool judge(char s[]); bool judgeLeft(char s1[], char s2[]); bool judgeRight(char s1[], char s2[]);

当然，如果题目要求改变，不是“不影响原计算结果的括号要省略”，而是还原原来的表达式的计算顺序，那么添加括号的顺序就不太相同了，需要另加判断。

而添加括号，我是在中序遍历中完成的。目前我只会写递归版本的，当然用递归来写添加括号当然是简单不少而且清晰明了。非递归版本的遍历还要加括号，可饶了我吧。

由原始的递归

讯享网void travel(BTNodeptr p) { if (p != NULL) { travel(p->lchild); printf("%s", p->num); travel(p->rchild); } }

改为这个版本：

void travel(BTNodeptr p) { if (p != NULL) { /*若p的左子树上是符号，并且小于p上的符号优先级，则添加括号*/ if (p->lchild && judgeLeft(p->num,p->lchild->num)) { printf("("); travel(p->lchild); printf(")"); } else travel(p->lchild); printf("%s", p->num); /*若p的右子树上是符号，并且不大于p上的符号优先级，则判断后添加括号*/ if (p->rchild && judgeRight(p->num, p->rchild->num)) { printf("("); travel(p->rchild); printf(")"); } else travel(p->rchild); } }

我自认为还是完成的不错的，看着也不算太复杂，也还是比较好理解。

AC代码

上面都是架构，下面则是完整的AC代码，虽然写的还是不好，不过比起大一时候的一团乱麻也算清晰了很多，这也算是一点进步吧（笑）。（大一时候的代码基本现在看不下去）

也欢迎各位参观的有什么建议来指正。

讯享网#include<stdio.h> #include<string.h> #include<stdlib.h> #include<stdbool.h> #define LENGTH 10007 #define SUM 512 /*表达式树的定义及函数*/ struct node { char num[LENGTH]; struct node *lchild; struct node *rchild; }; typedef struct node Node; typedef struct node* BTNodeptr; void freeT(BTNodeptr p); //释放表达式树 void travel(BTNodeptr p); //中序遍历，输出中缀表达式以及添加括号 BTNodeptr buildT(char s[]); //建立表达式树 /*存放表达式树的指针的栈*/ BTNodeptr tree[SUM]; int top = 0; void push(BTNodeptr p) { tree[++top] = p; } BTNodeptr pop() { return tree[top--]; } /*判断符号优先级*/ bool judge(char s[]); bool judgeLeft(char s1[], char s2[]); bool judgeRight(char s1[], char s2[]); int main() { char s[LENGTH]; BTNodeptr root = NULL; fgets(s, LENGTH, stdin); //不用gets是因为fgets更安全 root = buildT(s); travel(root); freeT(root); //虽然大一很菜很菜，不过记得free这个好习惯还是从大一就有了 //PS：其实是因为没听懂担心内存泄露 return 0; } void freeT(BTNodeptr p) { if (p != NULL) { freeT(p->lchild); freeT(p->rchild); free(p); p = NULL; } } /*表达式树特点：若p有左右节点，则p必定为符号位*/ void travel(BTNodeptr p) { if (p != NULL) { /*若p的左子树上是符号，并且小于p上的符号优先级，则添加括号*/ if (p->lchild && judgeLeft(p->num,p->lchild->num)) { printf("("); travel(p->lchild); printf(")"); } else travel(p->lchild); printf("%s", p->num); /*若p的右子树上是符号，并且不大于p上的符号优先级，则判断后添加括号*/ if (p->rchild && judgeRight(p->num, p->rchild->num)) { printf("("); travel(p->rchild); printf(")"); } else travel(p->rchild); } } BTNodeptr buildT(char s[]) { int i; BTNodeptr p; int a = 0; char temp[LENGTH]; for (i = 0; s[i] != '\0'; i++) { /*读取到数字，储存*/ if ((s[i] >= '0' && s[i] <= '9') || s[i] == '.') temp[a++] = s[i]; /*读取到空格，将数字存储*/ else if (s[i] == ' ' && a != 0) { temp[a] = '\0'; p = (BTNodeptr)malloc(sizeof(Node)); strcpy(p->num, temp); p->lchild = NULL; p->rchild = NULL; push(p); a = 0; } /*若为运算符，从栈中弹出T1和T2作为右节点和左节点*/ else if(s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/') { p = (BTNodeptr)malloc(sizeof(Node)); p->num[0] = s[i]; p->num[1] = '\0'; BTNodeptr pright = pop(); BTNodeptr pleft = pop(); p->lchild = pleft; p->rchild = pright; push(p); } } return p; } /*判断s是否为符号*/ bool judge(char s[]) { return (s[0] == '+' || s[0] == '-' || s[0] == '/' || s[0] == '*'); } /*判断父节点s1的优先级是否比左节点s2高 */ bool judgeLeft(char s1[], char s2[]) { if ((s1[0] == '*' || s1[0] == '/') && (s2[0] == '+' || s2[0] == '-')) return true; return false; } /*判断父节点s2的优先级是否大于右节点s2，若相等还需判断父节点是否为'/'或'-' */ bool judgeRight(char s1[], char s2[]) { if (s1[0] == '/' && judge(s2)) return true; if ((s1[0] == '*' || s1[0] == '-') && (s2[0] == '+' || s2[0] == '-')) return true; return false; }