#AT0033. 表达式的转换

    ID: 392 远端评测题 1000ms 128MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>算法基础模拟字符串数据结构线性结构

表达式的转换

题目描述

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

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

例如: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+-*/^(),并且不会出现形如 2*-3 的格式。

表达式中的基本数字也都是一位的,不会出现形如 12 形式的数字。

所输入的字符串不要判错。

输出格式

若干个后缀表达式,第 i+1i + 1 行比第 ii 行少一个运算符和一个操作数,最后一行只有一个数字,表示运算结果。

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

2^2^3

2 2 3 ^ ^
2 8 ^
256

提示

运算的结果可能为负数,/ 以整除运算。并且中间每一步都不会超过 2312^{31}。字符串长度不超过 100100

注意乘方运算 ^ 是从右向左结合的,即 2 ^ 2 ^ 32 ^ (2 ^ 3),后缀表达式为 2 2 3 ^ ^

其他同优先级的运算是从左向右结合的,即 4 / 2 / 2 * 2((4 / 2) / 2) * 2,后缀表达式为 4 2 / 2 / 2 *

保证不会出现计算乘方时幂次为负数的情况,故保证一切中间结果为整数。