逆波兰表达式求值

1.什么是逆波兰表达式？
也叫后缀表达式，(3+4)*5-6 对应的逆波兰表达式 3 4 + 5 * 6 -

2.代码

/**
 * @author shengjk1
 * @date 2020/2/16
 */
/*
逆波兰表达式
 */
public class PolandNotation {
    public static void main(String[] args) {
        //(3+4)*5-6
        String suffixExpression = "3 4 + 5 * 6 -";
        List<String> listString = getListString(suffixExpression);
        System.out.println(listString);
        System.out.println(calculate(listString));
        
    }
    
    //将逆波兰表达式转化为list
    public static List<String> getListString(String suffixExpression) {
        String[] split = suffixExpression.split(" ");
        ArrayList<String> list = new ArrayList<>();
        
        for (String s : split) {
            list.add(s);
        }
        return list;
    }
    
    /**
     * 逆波兰表达式 求值
     * <p>
     * 从左至右扫描表达式，
     * 遇到数字，将数字压入堆栈，
     * 遇到运算符，弹出栈顶的两个数，
     * 用运算符对它们做相应的计算(次栈顶元素和栈顶元素)，并将结果入栈。
     * 重复上述过程直到表达式最右端，最后运算得出的值即为表达式的结果。
     *
     * @param s
     * @return
     */
    public static int calculate(List<String> s) {
        Stack<String> stack = new Stack<>();
        for (String item : s) {
            if (item.matches("\\d+")) {
                stack.push(item);
            } else {
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int res = 0;
                if (item.equals("+")) {
                    res = num2 + num1;
                } else if (item.equals("-")) {
                    res = num2 - num1;
                } else if (item.equals("*")) {
                    res = num2 * num1;
                } else if (item.equals("/")) {
                    res = num2 / num1;
                } else {
                    throw new RuntimeException("运算符有误");
                }
                stack.push("" + res);
            }
        }
        return Integer.parseInt(stack.pop());
    }
}

3.应用场景
一般用 stack 对表达式求值时，都会先将中缀表达式转化为逆波兰表达式