372. 表达式转换

【题目描述】

平常我们书写的表达式称为中缀表达式，因为它将运算符放在两个操作数中间，许多情况下为了确定运算顺序，括号是不可少的，而后缀表达式就不必用括号了。

后缀标记法：书写表达式时采用运算符紧跟在两个操作数之后，从而实现了无括号处理和优先级处理，使计算机的处理规则简化为：从左到右顺序完成计算，并用结果取而代之。

例如： $8-(3+2*6)/5+4$可以写为：

8 3 2 6 * + 5 / – 4 +

其计算步骤为：

8 3 2 6 * + 5 / – 4 +
8 3 12 + 5 / – 4 +
8 15 5 / – 4 +
8 3 – 4 +
5 4 +
9

编写一个程序，完成这个转换，要求输出的每一个数据间都留一个空格。

【输入格式】

就一行，是一个中缀表达式。

输入保证字符串中只包含0123456789+-*/^()；表达式中的基本数字也都是一位的，不会出现形如$12$形式的数字；/是整除；输入数据保证每一步算术运算的中间结果均在C++整数范围内；输入的字符串不要判错。

【输出格式】

输出包含若干行，每行一个后缀表达式。

第1行为中缀表达式转化的后缀表达式，后续每一行都比上一行少一次运算，最后一行只有一个数字，表示运算结果(注意可能为负数)。

【样例输入】

8-(3+2*6)/5+4

【样例输出】

8 3 2 6 * + 5 / – 4 +
8 3 12 + 5 / – 4 +
8 15 5 / – 4 +
8 3 – 4 +
5 4 +
9