后缀表达式求值

题目描述

给定一个合法的后缀表达式，请计算它的值。

表达式由整数和四种运算符组成：+、-、*、/。

从左向右扫描表达式：

• 遇到整数时，将它压入栈中；
• 遇到运算符时，弹出两个整数。先弹出的是右操作数 $b$，后弹出的是左操作数 $a$，再计算 $a\ 运算符\ b$，并将结果压回栈中。

整数除法规则与 C++ 中的整数除法相同，即结果向 $0$ 取整。

输入格式

第一行输入一个整数 $n$，表示表达式中的记号数量。

第二行输入 $n$ 个以空格分隔的记号，每个记号是整数或运算符。

输出格式

输出表达式的计算结果。

输入输出样例

5
10 2 3 * +

16

数据范围

• $1\le n\le 100000$；
• 每个输入整数的绝对值不超过 $10^9$；
• 输入保证表达式合法；
• 除数不会为 $0$；
• 所有中间结果均在 long long 范围内。

提示

减法和除法的顺序不能颠倒：先弹右操作数，后弹左操作数。

来源

数据结构课堂练习——后缀表达式求值