首页 > 代码库 > 表达树求值

表达树求值

找到最后处理的运算符,它是整个树的根,然后递归处理。

注意:下面代码不能处理 -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;}

表达树求值