Stack

Time Limit: 1 sec Memory Limit: 131072 KB

题目描述

Reverse Polish Notation (RPN) 是一种记法，在这种记法中，每个运算符都放在其所有操作数的后面。例如，普通表达式 (1 + 2) * (5 + 4) 用 RPN 表示为：

1 2 + 5 4 + *

RPN 的一个优点是表达式中不需要括号。

你的任务是编写一个程序，读取一行 RPN 表达式并输出计算结果。

RPN 表达式可以用栈来计算：

• 从左到右依次读取每个符号（token）。
• 如果是操作数（数字），则将其压入栈中。
• 如果是运算符（+、-、*），则从栈中​弹出两个元素​​，先弹出的为​右操作数​，后弹出的为​左操作数​，进行相应运算，将结果压回栈中。
• 重复以上步骤，直到读完表达式。
• 栈顶的值即为表达式的计算结果。

输入格式

• 一行包含一个 RPN 表达式。
• 相邻的两个符号（操作数或运算符）之间用一个空格分隔。
• 操作符只会是 +、- 或 *。
• 操作数为小于 10610^6 的正整数。

输出格式

• 输出一个整数，表示计算结果。

约束条件

• $2\leq$ 表达式中的操作数个数 $\leq 100$
• 1≤ 表达式中的运算符个数 ≤99
• 栈中的值范围：$-10^9 \leq$ 值 $\leq 10^9$

样例输入 1

1 2 +

样例输出 1

3

样例输入 2

1 2 + 3 4 - *

样例输出 2

-3