J7 习题-1 计算器

题目描述

从标准输入中读入一个整数算术运算表达式，如24 / ( 1 + 2 + 36 / 6 / 2 - 2) * ( 12 / 2 / 2 )= ，计算表达式结果，并输出。

要求：

表达式运算符只有+、-、*、/，表达式末尾的 = 字符表示表达式输入结束，表达式中可能会出现空格；表达式中会出现圆括号，括号可能嵌套，不会出现错误的表达式；出现除号 / 时，以整数相除进行运算，结果仍为整数，例如：$5/3$ 结果应为 1。

要求采用表达式树来实现表达式计算。

表达式树（expression tree）：

我们已经知道了在计算机中用后缀表达式和栈来计算中缀表达式的值。在计算机中还有一种方式是利用表达式树来计算表达式的值。表达式树是这样一种树，其根节点为操作符，非根节点为操作数，对其进行后序遍历将计算表达式的值。由后缀表达式生成表达式树的方法如下：

读入一个符号：

如果是操作数，则建立一个单节点树并将指向他的指针推入栈中；

如果是运算符，就从栈中弹出指向两棵树 $T1$ 和 $T2$ 的指针（ $T1$ 先弹出）并形成一棵新树，树根为该运算符，它的左、右子树分别指向 $T2$ 和 $T1$，然后将新树的指针压入栈中。

例如输入的后缀表达为：

ab+cde+**

则生成的表达式树为：

输入格式

从键盘输入一个以 = 结尾的整数算术运算表达式。操作符和操作数之间可以有空格分隔。

输出格式

第一行：输出表达式树根、左子节点及右子节点上的运算符或操作数，中间由一个空格分隔， 第二行：输出表达式计算结果。

样例输入

24 / ( 1 + 2 + 36 / 6 / 2 - 2 ) * ( 12 / 2 / 2 ) =

样例输出

* / /
18

样例分析

按照运算符及括号优先级依次计算表达式的值。在生成的表达树中 * 是根节点的运算符，/ 是根节点的左子节点上运算符，/ 是根节点的右子节点上运算符，运算结果为 18。

数据范围

对于 $100\%$ 的数据：$3\le$算术表达式长度$\le 100$。