找到最后处理的运算符，它是整个树的根，然后递归处理。
注意：下面代码不能处理 -1这样的表达式。
#include <iostream> #include <cstring> using namespace std; const int MAXN = 1000; int lch[MAXN],rch[MAXN]; //每个结点的左右儿子 char op[MAXN]; //存放每个结点的字符 char input[MAXN]; //input数组存放输入的表达式字符串 int nc = 0; //nc存放表达式树的结点，开始时结点数为0 /***************************************************** 递归构造表达式树，每次找括号外的+、-、*、/ 优先+、-划分，其次*、/划分，原则是找最后运算的符号 如果所有运算符均在括号内，忽略这个括号，继续递归内层 *****************************************************/ int buildTree(char *s,int x,int y) { //根据表达式建立表达式树 //c1、c2分别记录“最右”出现的加减号和乘除号 //标志p=0避免记录括号内的+、-、*、/ int i,c1 = -1, c2 = -1, p = 0; int u; if(y-x == 1) { //仅一个字符，建立单独结点 u = nc++; lch[u] = rch[u] = 0; //单独结点无左右子树，所以左右子树的编号为0 op[u] = s[x]; //此时把s[x]值赋给数组op[u] return u; } for(i = x; i < y; ++i) { switch(s[i]) { case '(': p++; break; case ')': p--; break; case '+': case '-': if(!p) c1 = i; break; case '*': case '/': if(!p) c2 = i; break; } } if(c1 < 0) c1=c2; //找不到括号外的加减号，就用乘除号 if(c1 < 0) return buildTree(s, x+1, y-1); //整个表达式被一对括号括起来 u = nc++; //对结点的左子树区间[x,c1]，对表达式进行处理 lch[u] = buildTree(s,x,c1); //对结点的右子树区间[c1+1,y]，对表达式进行处理 rch[u] = buildTree(s,c1+1,y); op[u] = s[c1]; // return u; } int transTree(int cur) { //根据算术表达式树，来计算表达式值 //当前结点无左右子树，op[cur]-'0'表示一个数值 if(lch[cur] ==0 || rch[cur] == 0) return op[cur] - '0'; else { int ret1 = transTree(lch[cur]); //计算当前结点左子树的值 int ret2 = transTree(rch[cur]); //计算当前结点右子树的值 switch(op[cur]) { //根据当前结点是+、-、*、/，由左右子树值计算当前结点的值 case '+': return ret1 + ret2; case '-': return ret1 - ret2; case '*': return ret1 * ret2; case '/': return ret1 / ret2; } } } /********************************* 输入算术表达式：a+b*(c-d)-e/f 输出算术表达式的运算结果 *********************************/ int main() { memset(input, 0, sizeof(input)); //初始化数组input cin >> input; //从键盘输入的字符串存放在数组input中 buildTree(input, 0, strlen(input)); //建立表达式树 cout << transTree(0) << endl; //计算表达式的值 return 0; }