表达式树

表达式树

表达式树是用来解决表达式的一种常用的工具，它将表达式建立成一个二叉树，而二叉树的后序遍历顺序刚好是表达式的运算顺序。
[题目] 输入一个字符表达式，每个字符代表一个数字，输出运算结果。
[代码]
以下代码参考了刘汝佳《算法竞赛入门经典》。

//表达式树声明
struct exprtree
{
	char op;
	exprtree *left;
	exprtree *right;
};

//建立表达式树函数
exprtree* build_exprtree(const string &s, int x, int y)
{
	int c1 = -1, c2 = -1, p = 0;
	exprtree *l = new exprtree();
	if (y - x == 1)
	{                
		l->op = s[x];
		l->left = nullptr;
		l->right = nullptr;
		return l;
	}

	for (int 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 build_exprtree(s, x + 1, y - 1);
	l->left = build_exprtree(s, x, c1);
	l->right = build_exprtree(s, c1 + 1, y);
	l->op = s[c1];
	return l;
}

//声明一个全局变量，存储字符到数字的映射
map<char, int> val;
//通过建立的二叉树递归计算数值
int calculator(exprtree *t)
{
	if (isalpha(t->op)) return val[t->op];
	switch (t->op)
	{
	case '+': return calculator(t->left) + calculator(t->right);
	case '-': return calculator(t->left) - calculator(t->right);
	case '*': return calculator(t->left) * calculator(t->right);
	case '/': return calculator(t->left) / calculator(t->right);
	}
	return 0;
}

//主函数
int main()
{
	string s;
	char a;
	int n;
	exprtree *T = new exprtree;
	cin >> s;
	while (cin>>a>>n)
	{
		val[a] = n;
	}
	int sz = s.size();
	T = build_exprtree(s, 0, sz);
	cout<<calculator(T)<<endl;
	delete T;
    return 0;
}

[总结] 上述表达式树的难点在于理解build_exprtree()中p，c1和c2的含义，建议手推一遍加深理解。