关于java:LeetCode150-逆波兰表达式求值

42次阅读

共计 1481 个字符，预计需要花费 4 分钟才能阅读完成。

题目形容：依据逆波兰表示法，求表达式的值。

无效的算符包含 +、-、*、/。每个运算对象能够是整数，也能够是另一个逆波兰表达式。

阐明：

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

给定逆波兰表达式总是无效的。换句话说，表达式总会得出无效数值且不存在除数为 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<String> operatorList = new ArrayList<>();
        operatorList.add("+");
        operatorList.add("-");
        operatorList.add("*");
        operatorList.add("/");

        // 操作数栈
        Stack<Integer> 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));
    }
}