使用栈计算逆波兰表达式

简介：逆波兰表达式又叫做后缀表达式。逆波兰表示法是波兰逻辑学家J・卢卡西维兹(J・ Lukasiewicz)于1929年首先提出的一种表达式的表示方法 [1]  。后来,人们就把用这种表示法写出的表达式称作“逆波兰表达式”。逆波兰表达式把运算量写在前面,把算符写在后面。

class ReversePolandStack {
    public static void main(String[] args) {
        String s = "30 4 + 5 * 6 -";
        List<String> list = addList(s);
        int calculate = calculate(list);
        System.out.println(calculate);
    }

    public static List<String> addList(String s) {
        List<String> list = new ArrayList<String>();
        String[] split = s.split(" ");
        for (String item : split) {
            list.add(item);
        }
        return list;
    }

    public static int calculate(List<String> list) {
        Stack<String> stack = new Stack<String>();
        list.forEach(r -> {
            if (r.matches("\\d+")) {
                stack.push(r);
            } else {
                int num2 = Integer.parseInt(stack.pop());
                int num1 = Integer.parseInt(stack.pop());
                int res = 0;
                switch (r) {
                    case "+":
                        res = num1 + num2;
                        break;
                    case "-":
                        res = num1 - num2;
                        break;
                    case "*":
                        res = num1 * num2;
                        break;
                    case "/":
                        res = num1 / num2;
                        break;
                    default:
                        throw new RuntimeException("表达式有误");
                }
                stack.push(res + "");
            }
        });
       return Integer.parseInt(stack.pop());
    }
}