LeetCode-150-|LeetCode-150- 逆波兰表达式求值 LeetCode-150-逆波兰表达式求值

逆波兰表达式求值

题目描述：根据逆波兰表示法，求表达式的值。
【LeetCode-150-|LeetCode-150- 逆波兰表达式求值】有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：

整数除法只保留整数部分。

给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

逆波兰表达式：详情介绍见逆波兰表达式
示例说明请见LeetCode官网。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：栈

利用栈后进先出的特点来求解逆波兰表达式（后缀表达式）的值，具体求解过程如下：

如果原表达式只有一个参数，则直接返回操作数。

否则，声明一个操作数栈nums用来存放操作数，按顺序遍历逆波兰表达式的字符：

如果当前字符是操作数，则直接入栈；

如果当前字符是操作符，则从栈中取出2个操作数，并按照当前操作符进行计算，将计算结果重新计算。

最后，返回操作数栈的唯一的一个值，即为逆波兰表达式的求值结果。

import java.util.ArrayList; import java.util.List; import java.util.Stack; public class LeetCode_150 {public static int evalRPN(String[] tokens) { if (tokens.length == 1) { return Integer.valueOf(tokens[0]); } List operatorList = new ArrayList<>(); operatorList.add("+"); operatorList.add("-"); operatorList.add("*"); operatorList.add("/"); // 操作数栈 Stack nums = new Stack<>(); for (int i = 0; i < tokens.length; i++) { if (operatorList.contains(tokens[i])) { // 如果是操作符，取出2个操作数进行运算然后将结果重新入栈 int num1 = Integer.valueOf(nums.pop()); int num2 = Integer.valueOf(nums.pop()); if ("+".equals(tokens[i])) { nums.push(num2 + num1); } else if ("-".equals(tokens[i])) { nums.push(num2 - num1); } else if ("*".equals(tokens[i])) { nums.push(num2 * num1); } else if ("/".equals(tokens[i])) { nums.push(num2 / num1); } } else { // 如果是操作数，则入栈 nums.push(Integer.valueOf(tokens[i])); } } return nums.pop(); }public static void main(String[] args) { // 测试用例 String[] tokens = new String[]{"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"}; // 转换成中缀表达式的结果是： ((10 * (6 / ((9 + 3) * -11))) + 17) + 5 // 计算结果为： 22 System.out.println(evalRPN(tokens)); } }