首页 > 代码库 > ACM:树的变换,根据表达式建立表达式树

ACM:树的变换,根据表达式建立表达式树

题目:输入一个表达式,建立一个表达式树!


分析:找到最后计算的运算符(它是整棵表达式树的根),然后递归处理!

            在代码中,只有当p==0的时候,才考虑这个运算符,因为括号里的运算符一定不是最后计算的,应当忽略!

    由于加减跟乘除都是左结合的,最后一个运算符才是最后计算的,所以用两个变量c1跟c2分别记录在括号外面的“最右”出现的加减号和乘除号。


#include <iostream>
#include <string>
using namespace std;

const int MAXN = 1000;
string str;  //表达式
int lch[MAXN], rch[MAXN];   //每个节点的左右儿子节点编号
char op[MAXN];   //每个节点里面的字符
int nc = 0;   //代表节点个数

int build_tree(string s, int x, int y) {
	int p = 0, c1 = -1, c2 = -1;   //c1和c2分别记录最右出现的加减号和乘除号,前提是他们在括号外面,因为如果在括号里面的话,这个运算符肯定不是最后一个计算的!
	int u;
	if(y - x == 1) {   //如果仅有一个字符,那么建立单独节点!
		u = ++nc;
		lch[u] = 0;
		rch[u] = 0;
		op[u] = s[x];
		return u;
	}
	for(int i = x; i < y; ++i) {  //找括号外面的最右边的加减号跟乘除号,位置分别由c1跟c2记录!
		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 build_tree(str, x+1, y-1);   //如果括号外面加减乘除号都没有,那意思就是整个表达式被一个括号包围了。
	u = ++nc;  
	lch[u] = build_tree(str, x, c1);   //运算符s[c1]的左子树区间是[x, c1],右子树区间是[c1+1, y]
	rch[u] = build_tree(str, c1+1, y);
	op[u] = s[c1];
	return u;
}

int main() {
	cin >> str;
	build_tree(str, 0, str.size());
	for(int i = 1; i < nc+1; ++i) {
		cout << lch[i] << "  " << rch[i] << "  " << op[i] << endl;
	}
	return 0;
}