表达式· 表达式树· 表达式求值 众所周知， 任何一个表达式， 都可以用一棵表达式树来表示。 例如， 表达式 a+b*c， 可以表示为如下的表达式树： + / \ a * / \ b c 现在， 给你一个中缀表达式， 这个中缀表达式用变量来表示(不含数字)， 请你将这个中缀表达式用表达式二叉树的形式输出出来。 时间限制： 1000 内存限制： 65535 输入 输入分为三个部分。 第一部分为一行， 即中缀表达式(长度不大于 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++）：表达式转表达式树并求值。用运算符优先级构造树：递归找括号内最低优先级运算符作根，左子树为左表达式右子树为右表达式。后序遍历得逆波兰式，代入变量值递归求值（除法整除）。样例a+b*c→abc*+，值37。核心：中缀建表达式树。
试卷来源：202212 青少年等级考试C/C++真题七级