首页 > 代码库 > 表达树求值
表达树求值
找到最后处理的运算符,它是整个树的根,然后递归处理。
注意:下面代码不能处理 -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;}
表达树求值
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。