#1136. JM的算术表达式(2)

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: JM233333

题目描述

今天JM要求你完成大量的小学数学题,如果你不能按时正确地完成就会被JM用黑魔法变成咸鱼,然后被czq和flh抓去做成酸菜鱼。为了不被吃掉,你必须解决如下问题:

给定 组算术表达式,要求你给出每个表达式的后缀表达式形式。

输入的表达式均满足:

  • 表达式以中缀表达式的格式给出,每个词素(运算符或操作数)之间用零至三个空格隔开,表达式的首尾两端无多余空格;

  • 表达式的语法一定是合法的;

  • 表达式包括 + , - , * , / 四种运算符,分别表示加减乘除,其中除法运算需要向下取整;

  • 表达式包括 ( , ) 括号;

  • 表达式中的操作数为 范围内的整数;

  • 表达式中的操作数的个数不超过

  • 表达式中的左右括号的总个数不超过

关于后缀表达式:

后缀表达式也被称为逆波兰表达式,其优点是便于计算机程序对其进行计算,缺点是不便于人类阅读。而我们通常习惯使用中缀表达式,它便于阅读,但是编程处理这样的表达式要麻烦得多。

所谓的“后缀”指的是 a b op 的格式,其中 a , b 是两个操作数, op 是一个二元运算符。相对应地,“中缀”指的是 a op b 的格式,也就是我们通常习惯的写法。

后缀表达式总是按照从左到右的顺序计算,不需要括号即可表示各种计算顺序,因而比中缀表达式要容易处理。例如中缀表达式 a * b + ca * (b + c) 的后缀形式分别为 a b * c +a b c + * ,不需要考虑运算符优先级,无需括号,不存在歧义。

计算后缀表达式时,我们从左到右依次读入词素,每当读到一个二元运算符 op 时,就将最后读到的两个操作数 ab 进行 op 运算,并将结果存下来。

a b * c + 为例,我们从左到右依次读入 a , b , * ,计算得到 a * b 的结果并将其记为 x ,再依次读入 c , + ,计算得到 x + c 的结果。

再以 a b c d + / - 为例,我们读到 + 时,计算得到 c + d 的结果并将其记为 x ;再读到 / ,计算得到 b / x 的结果并将其记为 y ;最后计算得到 a - y 的结果。

输入格式

第一行一个正整数 ,表示算术表达式的个数。

接下来 行,每行一个字符串,给出一个符合题意的算术表达式。

输出格式

输出 行,每行一个字符串,依次表示每个算术表达式的后缀表达式形式。

输出的表达式应满足:

  • 表达式以后缀表达式的格式给出,每个词素(运算符或操作数)之间需用一个空格隔开;

  • 表达式中不应含有括号;

  • 如果存在多种合法解,应当尽可能按照从左到右的顺序结合,例如 1 + 2 + 3 可以写成 1 2 + 3 +1 2 3 + + ,应当输出 1 2 + 3 +

样例

样例输入

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

样例输出

1 2 +
3 4 5 + *
1 2 / 4 3 * -
5 4 3 2 1 + * + 6 - *

数据范围与提示