問題文
表达数学表达式的符号 逆波兰表示法
有 。
在这个问题中,我们将使用一位整数( 0 从 9 )和
二元运算符(加法 + , 減算 - , 乗算 * )称为标记,由连接的标记组成的字符串表示逆波兰表示法的表达式。
例如,逆波兰表示法的表达式为 32-1+ 使用中缀表示法编写。
计算结果为 (3-2)+1 计算结果为 2 。
我为函数程序编写了以下伪代码来计算逆波兰表示法的表达式。
calc(s)
{
データ構造Xを空に初期化する
for (i in [0 .. |s|-1])
{
if (s[i]は数である)
{
X.push(s[i])
}
else
{
r = X.pop()
l = X.pop()
lとrを演算子s[i]で計算した結果をaとする
X.push(a)
}
}
ans = X.pop()
return ans
}
输入 s 是表示逆波兰表示法表达式的字符串,
它意味着令牌 s[i] 表示 i+1 番目 (0 \leq i \leq |s|-1) 。
「 l 和 我讨厌 r 至操作员 用 s[i] 计算的结果是 “ a ”的意思 l是左操作数, r作为右操作数运算符 使用 s[i] 执行加法、减法和乘法。 例如 s[i] 是
- 如果 a 中缀表示法
意思是替换 l - r 。
数据结构 压入和弹出到 X 的值是 请注意,这不一定是 0 从 9 的范围。 如果
数据结构 压入和弹出到 X 为空时弹出,程序将因错误而停止,并且不会获得任何输出。
代码中的数据结构 如果 X 是一个堆栈,这个函数将正确计算逆波兰表示法的表达式,但它会错误地创建一个队列,并且无法正确计算。 因此,您决定重新排列输入表达式,并让队列中创建的程序输出正确的答案。 堆栈中使用
X 创建的代码是S程序,
使用 X 作为队列创建的代码称为Q程序。
逆波兰表示法表达式
给出 A ,因此满足以下条件。
查找并打印 B 。
这是一种
- B 表示 A 是一个重新排列
- Q程序输入 Q 程序在给出 B 时不会给出错误
- S程序输入 给出 A 时的输出和 Q 程序的输入为 给出 B 时的输出是相同的
入力
输入是表示逆波兰表示法表达式的字符串 由一行组成: A 。 是由A
- 1 \leq |A| \leq 100
- 文字列 A 表示
0123456789+-*组成的字符串 - 文字列 A 是逆波兰表示法的有效表达式
出力
满足问题条件的字符串 在一行中输出 B。 如果有多个 B,则输出一个。B
入力例1
54-
出力例1
45-
入力 54- 的正确输出是
只有一个 45- 。
如果我们使用中缀表示法将
入力例2
321+-
出力例2
12+3-
入力 321+- 赋予 S 程序时编写计算, 3-(2+1) 并且S程序的输出是 0 。
入力例3
2
出力例3
2
仅包含一个数字的字符串也是逆波兰表示法的有效表达式。