LeetCode--150.逆波兰表达式求值（栈和队列）

题目描述给你一个字符串数组tokens表示一个根据 逆波兰表示法 表示的算术表达式。请你计算该表达式。返回一个表示表达式值的整数。注意有效的算符为、-、*和/。每个操作数运算对象都可以是一个整数或者另一个表达式。两个整数之间的除法总是向零截断。表达式中不含除零运算。输入是一个根据逆波兰表示法表示的算术表达式。答案及所有中间计算结果可以用32 位整数表示。示例 1输入tokens [2,1,,3,*] 输出9 解释该算式转化为常见的中缀算术表达式为((2 1) * 3) 9示例 2输入tokens [4,13,5,/,] 输出6 解释该算式转化为常见的中缀算术表达式为(4 (13 / 5)) 6示例 3输入tokens [10,6,9,3,,-11,*,/,*,17,,5,] 输出22 解释该算式转化为常见的中缀算术表达式为 ((10 * (6 / ((9 3) * -11))) 17) 5 ((10 * (6 / (12 * -11))) 17) 5 ((10 * (6 / -132)) 17) 5 ((10 * 0) 17) 5 (0 17) 5 17 5 22提示1 tokens.length 104tokens[i]是一个算符、-、*或/或是在范围[-200, 200]内的一个整数逆波兰表达式逆波兰表达式是一种后缀表达式所谓后缀就是指算符写在后面。平常使用的算式则是一种中缀表达式如( 1 2 ) * ( 3 4 )。该算式的逆波兰表达式写法为( ( 1 2 ) ( 3 4 ) * )。逆波兰表达式主要有以下两个优点去掉括号后表达式无歧义上式即便写成1 2 3 4 *也可以依据次序计算出正确结果。适合用栈操作运算遇到数字则入栈遇到算符则取出栈顶两个数字进行计算并将结果压入栈中解题思路中缀表达式适合使用栈存储来计算如下图所示代码classSolution{publicintevalRPN(String[]tokens){// 初始化栈,存放待计算的整数StackIntegerstacknewStack();// 遍历tokens数组for(Strings:tokens){// 如果是运算符取出两个栈顶元素进行计算if(.equals(s)){intnum1stack.pop();intnum2stack.pop();stack.push(num2num1);}elseif(-.equals(s)){intnum1stack.pop();intnum2stack.pop();stack.push(num2-num1);}elseif(*.equals(s)){intnum1stack.pop();intnum2stack.pop();stack.push(num2*num1);}elseif(/.equals(s)){intnum1stack.pop();intnum2stack.pop();stack.push(num2/num1);}else{// 其余数字压栈stack.push(Integer.parseInt(s));}}returnstack.pop();}}