题目内容：众所周知，任何一个表达式，都可以用一棵表达式树来表示。例如，表达式a+b*c，可以表示为如下的表达式树。现在，给你一个中缀表达式，这个中缀表达式用变量来表示（不含数字），请你将这个中缀表达式用表达式二叉树的形式输出出来。

   +
  / \
 a   *
    / \
    b c

输入格式:

输入分为三个部分。

第一部分为一行，即中缀表达式(长度不大于50)。中缀表达式可能含有小写字母代表变量（a-z），也可能含有运算符（+、-、*、/、小括号），不含有数字，也不含有空格。

第二部分为一个整数n(n < 10)，表示中缀表达式的变量数。

第三部分有n行，每行格式为C　x，C为变量的字符，x为该变量的值。

输出格式：

输出分为三个部分，第一个部分为该表达式的逆波兰式，即该表达式树的后根遍历结果。占一行。

第二部分为表达式树的显示，如样例输出所示。如果该二叉树是一棵满二叉树，则最底部的叶子结点，分别占据横坐标的第1、3、5、7……个位置（最左边的坐标是1），然后它们的父结点的横坐标，在两个子结点的中间。如果不是满二叉树，则没有结点的地方，用空格填充（但请略去所有的行末空格）。每一行父结点与子结点中隔开一行，用斜杠（/）与反斜杠（\）来表示树的关系。/出现的横坐标位置为父结点的横坐标偏左一格，\出现的横坐标位置为父结点的横坐标偏右一格。也就是说，如果树高为m，则输出就有2m-1行。

第三部分为一个整数，表示将值代入变量之后，该中缀表达式的值。需要注意的一点是，除法代表整除运算，即舍弃小数点后的部分。同时，测试数据保证不会出现除以0的现象。

输入样例：

a+b*c
3
a 2
b 7
c 5

输出样例：

abc*+
   +
  / \
 a   *
    / \
    b c
37

C++实现

思路：

首先用 map 保存字符到整型的映射，遍历输入的表达式，利用操作符栈来构建后缀表达式，然后遍历后缀表达式，同样利用操作符栈来计算表达式的值，并同时构建树结构。

然后利用层序遍历获取树的层数，根据层数就可以知道每一层树节点之间的距离以及每一层首节点的位置。

再次层序遍历，构建一个满二叉树，满二叉树可以使用堆来表示，这里使用字符串来表示，没有子节点的地方全部用空字符代替。

最后遍历满二叉树字符串，打印树结构

#include < iostream>
#include < string>
#include < map>
#include < queue>
#include < stack>
using namespace std;

struct treenode
{
	struct treenode *left;
	struct treenode *right;
	char c;
	int v;
};

struct treenode *alloc_treenode(struct treenode *left, struct treenode *right, char c)
{
	struct treenode *newnode = new struct treenode;
	newnode->left = left;
	newnode->right = right;
	newnode->c = c;
	newnode->v = 0;
	return newnode;
}

/* 计算优先级 */
bool prior(char x, char y)
{
	if ((y == '*' || y == '/') & &  (x == '+' || x == '-'))
		return false;
	return true;
}

int main(int argc, char const *argv[])
{
	string expression;
	cin >> expression;

	int n;
	cin >> n;

	map< char, int> values;
	map< char, int>::iterator iter;
	char k;
	int v;
	for (int i = 0; i <  n; i++)
	{
		cin >> k >> v;
		values[k] = v;
	}

	stack< char> ops;
	string str;

    /* 遍历输入中缀表达式，构建后缀表达式 */
	for (auto c : expression)
	{
		if (isalpha(c))
		{
			str.push_back(c);
		}
		else if (c == '(')
		{
			ops.push(c);
		}
		else if (c == ')')
		{
			while (ops.top() != '(')
			{
				str.push_back(ops.top());
				ops.pop();
			}
			if (ops.top() == '(')
			{
				ops.pop();
			}
		}
		else if (c == '+' || c == '-' || c == '*' || c == '/')
		{
			if (ops.empty() || ops.top() == '(' || prior(c, ops.top()))
				ops.push(c);
			else
			{
				str.push_back(ops.top());
				ops.pop();
				ops.push(c);
			}
		}
	}

    /* 将操作符栈中的剩余字符 pop 到后缀表达式 */
	while (!ops.empty())
	{
		str.push_back(ops.top());
		ops.pop();
	}

	cout < <  str < <  endl;

	stack< struct treenode *> treestack;
	struct treenode *newnode = nullptr;

    /* 遍历后缀表达式，构建树，同时计算表达式的值 */
	for (auto c : str)
	{
		if (isalpha(c))
		{
			newnode = alloc_treenode(nullptr, nullptr, c);
			iter = values.find(c);
			if (iter != values.end())
			{
				newnode->v = values[c];
			}
			else
			{
				cout < <  "error " < <  c < <  " not found\n";
			}
			treestack.push(newnode);
		}
		else if (c == '+' || c == '-' || c == '*' || c == '/')
		{
			struct treenode *right = treestack.top();
			treestack.pop();
			struct treenode *left = treestack.top();
			treestack.pop();
			newnode = alloc_treenode(left, right, c);
			switch (c)
			{
			case '+':
				newnode->v = left->v + right->v;
				break;
			case '-':
				newnode->v = left->v - right->v;
				break;
			case '*':
				newnode->v = left->v * right->v;
				break;
			case '/':
				newnode->v = left->v / right->v;
				break;
			}
			treestack.push(newnode);
		}
	}

	struct treenode *root = treestack.top();
	treestack.pop();

	queue< struct treenode *> qtreenode;
	string heapchar;

	int level = 0, count = 1, newcount;
	/* 层序遍历计算树的深度 */
	qtreenode.push(root);
	while (!qtreenode.empty())
	{
		newcount = 0;
		for (int i = 0; i <  count; i++)
		{
			newnode = qtreenode.front();
			qtreenode.pop();
			if (newnode->left)
			{
				qtreenode.push(newnode->left);
				newcount++;
			}

			if (newnode->right)
			{
				qtreenode.push(newnode->right);
				newcount++;
			}
		}
		level++;
		count = newcount;
	}

	struct treenode *nullnode = alloc_treenode(nullptr, nullptr, ' ');
	int totallevel = level;
	qtreenode.push(root);
	heapchar.push_back(root->c);

	level = 0;
    /* 构建字符串 heapchar 表示的满二叉树，类似堆 */
	while (!qtreenode.empty() & &  level <  totallevel)
	{
		count = 1 < <  level;
		for (int i = 0; i <  count; i++)
		{
			newnode = qtreenode.front();
			qtreenode.pop();
			if (newnode->left)
			{
				qtreenode.push(newnode->left);
				heapchar.push_back(newnode->left->c);
			}
			else
			{
				qtreenode.push(nullnode);
				heapchar.push_back(' ');
			}

			if (newnode->right)
			{
				qtreenode.push(newnode->right);
				heapchar.push_back(newnode->right->c);
			}
			else
			{
				qtreenode.push(nullnode);
				heapchar.push_back(' ');
			}
		}
		level++;
	}

	int max = 1 < <  totallevel;
	string outlr = string(max, ' ');
	string outc = string(max, ' ');
	int first = max / 2, distance, pos;

    /* 打印用堆表示的满二叉树 */
	for (int i = 0; i <  totallevel; i++)
	{
		outlr = string(max, ' ');
		outc = string(max, ' ');
		int levelcount = 1 < <  i;
		distance = first * 2;
		pos = first;
		for (int j = 0; j <  levelcount; j++)
		{
			int k = levelcount + j;
			outc[pos - 1] = heapchar[k - 1];
			if (i != totallevel - 1)
			{
				if (!isspace(heapchar[k * 2 - 1]))
					outlr[pos - 1 - 1] = '/';
				if (!isspace(heapchar[k * 2]))
					outlr[pos + 1 - 1] = '\\';
			}
			pos += distance;
		}
		cout < <  outc < <  endl;
		if (i != totallevel - 1)
			cout < <  outlr < <  endl;
		first = first / 2;
	}

	cout < <  root->v < <  endl;

	return 0;
}