时间限制： 1.0 秒

空间限制： 256 MB

题目描述

逆波兰表示法是一种将运算符（operator）写在操作数（operand）后面的描述程序（算式）的方法。

举个例子，我们平常用中缀表示法描述的算式 (1+2)*(5+4)，改为逆波兰表示法之后则是 1 2 + 5 4 + *。

相较于中缀表示法，逆波兰表示法的优势在于不需要括号。

请输出以逆波兰表示法输入的算式的计算结果。

输入格式

从标准输入读入数据。

在一行中输入一个算式。相邻的符号（操作数或运算符）用一个空格隔开。

输出格式

输出到标准输出。

输出一行一个整数，表示计算结果。答案可能很大，输出答案对 $10^9+7$ 取模的结果即可。

4 3 + 2 -

5

样例 1 解释

样例 1 的表达式为 $4+3-2=5$。

1 2 + 3 4 - *

1000000004

样例 2 解释

样例 2 的表达式为 $(1+2)\times (3-4)=-3$。

如果 $x$ 为负数，则其在模 $10^9+7$ 的值为 $((10^9+7)-((-x)\bmod (10^9+7))) \bmod (10^9+7)$。

因此输出 $(10^9+7)-3=10^9+4$。

子任务

对于所有数据，保证操作数个数规模不超过 $10^4$，每一个操作数 $x$ 满足 $0\le x < 10^9+7$，且一定为合法的逆波兰表达式。

提示

Chap 04 栈与队列，逆波兰表达式

实际上求解逆波兰表达式的中间结果，对应着逆波兰表达式树的内部节点（叶子节点为给定的操作数）。由于本题均为二元运算符，因此表达式树是一个二叉树。

为什么不在这里出除法、乘方、阶乘呢？因为计算具体值会有各种各样的问题，我们将这部分留给其他题目进行考察。

本题的加法、乘法都不需要注意两个操作符的顺序，但是减法还是需要注意一下的。

此外，本题本质上属于不定个数字符串的输入，可以有以下两种方法判断文件终结：

#include <stdio.h>
char s[20];
int main()
{
    while (scanf("%s", s) != EOF)
    {
        // todo.
    }
}

#include <iostream>
#include <string>
std::string s;
int main()
{
    while (std::cin >> s)
    {
        // todo.
    }
}

对于字符串类如何判断和转换（操作数 or 运算符），可以看习题解析 [4-6] 的 readNumber 实现。

此外，在本地调试的时候可以按 ctrl+Z（Windows）或者 ctrl+D（Linux/Mac）模拟文件终止符。但是我们还是建议将样例输入保存为文件（例如 1.in），然后使用 freopen("1.in", "rb", stdin) 重定向文件的输入输出流（fstream 也有类似操作）。