给定一个包含正整数、加法运算符 + 和减法运算符 - 的后缀表达式(逆波兰表示法),请编写程序计算该表达式的值。
后缀表达式的定义:
操作数:正整数
运算符:加法运算符 + 和减法运算符 -
运算规则:遇到操作数时入栈;遇到运算符时,弹出栈顶的两个元素进行运算,并将结果入栈
注意:减法运算时,先弹出的是减数,后弹出的是被减数
输入一行字符串,表示后缀表达式。字符串由正整数、加法运算符 + 和减法运算符 - 组成,不同元素之间用单个空格分隔。
输出一个整数,表示后缀表达式的计算结果。
表达式中操作数的数量范围:[1, 100]
每个操作数的范围:[1, 1000]
保证表达式合法,且最终结果在 int 范围内
必须使用栈结构来实现
时间复杂度:O(n)
空间复杂度:O(n)