编程实现基于二叉树结构的表达式求值算法：

具体实现要求思路定义树节点和节点指针定义找根节点（即最后计算的计算符）函数建立二叉树实现表达式计算求值定义主函数

具体实现要求

表达式包含加减乘除四则运算以及至少一层括弧运算； 首先将输入的原表达式转换成二叉树结构，然后采用二叉树的后序遍历递归算法求得表达式的值。

思路

定义树节点和节点指针

里面包含树节点定义。定义了树的节点和节点指针：

typedef struct _Btree * Ptree; struct _Btree { char elem; Ptree left; Ptree right; }Btree;

定义找根节点（即最后计算的计算符）函数

实现对传入部分数组以根节点为界进行分隔，找到传入部分的根节点，返回找到的根节点的数组下标。（start>end，即传入部分是表达式，非单字符）

具体思路是：定义返回变量tag,当找到根节点时把i赋值tag，定义是否在括号内标志is_in_braket,初值为0；定义等级优先标志more_grade，初值为0；如果最外层有括号，先去掉括号；依次遍历数组，当遇到‘（’is_in_braket置为1，表示在括号内，遇到‘）’再置为0，表示出了括号。当is_in_braket为0即不在括号内且遇到‘+’、‘-’，more_grade置为1表示已经存在‘+’‘-’做根节点，最高优先级满足；接着判断是否满足不在括号内且不存在‘+’‘-’节点即more_grade==0的‘*’‘/’节点，若有则为根节点，赋值i给tag，最后return tag。

int find_split(char express[], int start, int end) { int tag = -1; if (express[start] == '(' && express[end] == ')') { ++start; --end; } int is_in_braket = 0; int more_grade = 0; for (int i = start; i <= end; i++) { if (express[i] == '(') ++is_in_braket; else if (express[i] == ')') --is_in_braket; if ((express[i] == '+' || express[i] == '-') && is_in_braket == 0) { more_grade = 1; tag = i; //无break, 找最后一个符合条件的运算符, 取顶级的+和- } else if ((express[i] == '*' || express[i] == '/') && more_grade == 0 && is_in_braket == 0) { tag = i; //无break, 找最后一个符合条件的运算符 } } return tag; }

建立二叉树

通过递归调用实现二叉树的建立。

具体思路如下： 首先定义树节点并赋值为ＮＵＬＬ，接着判断如果ｓｔａｒｔ＝ｅｎｄ即只有一个字符，开辟新树节点空间，赋值为叶子节点；否则先调用find_split(express, start, end)找到根节点下标，若返回ｔａｇ＜０找不到根节点，报错并退出，否则开辟新节点空间并赋值。接着不能立即递归调用，而应该先消除可能存在的表达式最外围的括号，避免以根节点为界拆分后左右括号分离。最后递归调用并赋值左右指针，return地址指针。

Ptree creat_Btree(const char *express, int start, int end) { Ptree pTree = NULL; if (start == end) { pTree = (Ptree)malloc(sizeof(Btree)); pTree->elem = express[start]; pTree->left = NULL; pTree->right = NULL; } else { //递归调用, 各自创建左右的表达式的对应二叉树 int tag = find_split(express, start, end); if (tag < 0) { printf("1.invalid express, exit.\n"); exit(-1); } else { pTree = (Ptree)malloc(sizeof(Btree)); pTree->elem = express[tag]; } if (express[start] == '(' && express[end] == ')') { ++start; --end; } pTree->left = creat_Btree(express, start, tag - 1); pTree->right = creat_Btree(express, tag + 1, end); } return pTree; }

实现表达式计算求值

Ptree creat_Btree(const char *express, int start, int end)函数已经实现创建一棵如下为例的二叉树，每一棵树的值为其左右子树的值做根节点的符号的运算。

+ / \ a * / \ b c

故可递归实现，递归出口为叶子节点，均为数值型，直接return　pTree->elem - ‘0’。

int post_traverser_calc(Ptree pTree) { if (pTree == NULL) return -1; else if ('0' <= pTree->elem &&pTree->elem <= '9') return pTree->elem - '0'; else if(pTree->elem=='+') return post_traverser_calc(pTree->left) + post_traverser_calc(pTree->right); else if(pTree->elem=='-') return post_traverser_calc(pTree->left) - post_traverser_calc(pTree->right); else if(pTree->elem=='*') return post_traverser_calc(pTree->left) * post_traverser_calc(pTree->right); else if(pTree->elem=='/') return post_traverser_calc(pTree->left) / post_traverser_calc(pTree->right); }

定义主函数

#include <stdio.h> #include <string.h> int main() { char a[100]; int result=0; char ch; printf("请输入中缀表达式：\n"); scanf("%s", a); while ((ch = getchar()) != '\n'); //吸收末尾的回车 Ptree express_tree = creat_Btree(a, 0, strlen(a)-1); result=post_traverser_calc(express_tree); printf("后缀表达式："); post_order_traverser(express_tree); printf("\n"); printf("表达式结果为：%d\n", result); return 0; }

整合起来就实现了基于二叉树结构的表达式求值算法

小白一个，第一次写博客，还请大家指点 ：）