前缀表达式

题目描述

奶龙正在学习表达式求值，ta 了解到表达式可以有中缀形式（运算符在操作数中间，如 $A+B$）和前缀形式（运算符在操作数前面，如 $+AB$）。现在他需要将一个简单的中缀表达式转换为前缀表达式。

转换规则如下：

1. 表达式只包含单个大写字母作为操作数，以及加号 $+$ 和减号 $-$ 作为运算符
2. 运算符都是二元运算符（需要两个操作数）
3. 不需要考虑运算符优先级问题，表达式总是从左到右计算（即所有运算符优先级相同，都是左结合的）

例如：

• 中缀表达式 $A+B-C$ 对应的前缀表达式是 $-+ABC$
• 中缀表达式 $A+B$ 对应的前缀表达式是 $+AB$

输入格式

输入一行，包含一个合法的中缀表达式 $S$.

输出格式

输出一行，表示转换后的前缀表达式。

样例 #1

样例输入 #1

A+B-C

样例输出 #1

-+ABC

样例 #2

样例输入 #2

A+B+C-D+E

样例输出 #2

+-++ABCDE

数据范围

对于全部数据：

• 表达式长度 $\leq 10000$
• 表达式只包含大写字母和 $+$、$-$ 运算符
• 表达式保证合法（即每个运算符都有两个操作数）

样例解释

对于样例一：

1. 先计算 $A+B$，转换为 $+AB$
2. 然后计算 $(A+B)-C$，转换为 $-+ABC$

对于样例二：

1. 从左到右依次转换：
   • $A+B \rightarrow +AB$
   • $(A+B)+C \rightarrow ++ABC$
   • $((A+B)+C)-D \rightarrow -++ABCD$
   • $(((A+B)+C)-D)+E \rightarrow +++-ABCDE$