OpenJudge

36:表达式·表达式树·表达式求值

总时间限制:
1000ms
内存限制:
65535kB
描述

众所周知,任何一个表达式,都可以用一棵表达式树来表示。例如,表达式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
全局题号
5430
添加于
2016-05-12
提交次数
14
尝试人数
7
通过人数
3

Other language verions