2103: 转逆波兰表达式

Memory Limit：128 MB Time Limit：1.000 S
Judge Style：Text Compare Creator：
Submit：13 Solved：4

Description

给你一个只包含整数、加减乘除运算符以及圆括号的中缀算术表达式字符串 s，请将其转换为逆波兰表示法（RPN，后缀表达式），并输出转换结果。

本题只需完成转换，不需要对表达式求值。
运算符仅包含：+、-、*、/。
括号仅包含：(、)。
整数为十进制，可能为多位数；表达式中可能包含空格。

  • 运算符优先级：*、/ 高于 +、-。

  • 结合性：上述四种运算符均为左结合。

  • 括号优先级最高。

  • 允许一元负号出现在数字前（如 -4、(-15)），其应当被视为数字的一部分，即输出时为一个整体 token -4、-15。

    • 说明：一元负号只会直接修饰数字，不会出现 -(...) 这种形式。

Input

输入一行为字符串 s，表示一个合法的中缀表达式。字符串中可能含有任意数量的空格。

Output

输出该表达式对应的逆波兰表达式，各记号之间用单个空格分隔。

  • 记号包括：整数（如 12、-7）、运算符（+ - * /）。

  • 不要在行首或行尾输出额外空格；行末换行可有可无，判题不受影响。

Sample Input Copy 

 2 - 1 + ( -4 + 1 )

Sample Output Copy 

2 1 - -4 1 + +

HINT

数据范围

  • 1 <= s.length <= 1000

  • 数字范围：-3000 <= 整数 <= 3000

  • s 仅由数字字符、空格、+ - * / ( ) 组成，并保证表达式合法且括号匹配。

  • 输入中不会出现 -(...) 的一元负号形式；若出现负数，均直接以 - 紧贴数字的形式给出（如 -7、(-12)）。

Source/Category

SubmitSubmit RecordStatisticsShowOff!