题解 | #表达式求值（java 中缀表达式转后缀表达式 逆波兰）#

后缀表达式（逆波兰）对于我们来说不太友好，但是对于机器来说是十分的友好的，不用管符号之间的优先级，没有括号，只要碰到符号就可以运算，下面是我写的一个逆波兰代码，可能写的有点菜

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        // write code here
        // 获取逆波兰表达式（本来应该是String，这里就不将他转成String了）
        ArrayList<String> polish = inToPost(s);

        Stack<Integer> nums = new Stack<>();

        // 由于已经转化成了逆波兰，所以运算规则:
        //  1.遇到了数字，压入数字栈，
        //  2.遇到了符号，需要两个数字出栈做该符号的运算，然后将结果压回数字栈
        //  3.循环1、2步，直到item遍历完成，此时数字栈一定只剩一个数，这个数就是最终结果
        for (String item : polish) {
            if (item.matches("\\d+")) {
                nums.push(Integer.valueOf(item));
            } else {
                int b = nums.pop();
                int a = nums.pop();

                int res = 0;

                switch (item) {
                        case "+": 
                                res = a + b;
                                break;
                        case "-": 
                                res = a - b;
                                break;    
                        case "*": 
                                res = a * b;
                                break;
                        case "/": 
                                res = a / b;
                }

                nums.push(res);
            }
        }

        return nums.pop();
    }

    // 中缀表达式转后缀表达式：
    //     * 1.碰到数字直接入中间结果
    //     * 2.碰到“（”直接入栈
    //     * 3.碰到“）”将所有的符号出栈直到碰到“（”
    //     * 4.其他普通符号判断优先级，如果优先级大于栈顶符号直接入栈，如果小于或等于栈顶富豪的优先级直接先出栈然后再压栈
    //     * 5.重复上述步骤直到字符串最末尾的一个字符
    //     * 6.将符号栈中剩下的符号加入到中间结果中产生最终结果。
    private ArrayList<String> inToPost(String s) {

        ArrayList<String> items = toArray(s);

        ArrayList<String> polish = new ArrayList<>();
        Stack<String> signs = new Stack<>();

        for (String item : items) {
            if (item.matches("\\d+")) {
                polish.add(item);
            } else if (item.equals("(")) {
                signs.push(item);
            } else if (item.equals(")")) {
                while (!signs.peek().equals("(")) {
                    polish.add(signs.pop());
                }
                signs.pop();
            } else {
                while (!signs.empty() && getPriority(signs.peek()) >= getPriority(item)) {
                    polish.add(signs.pop());
                }
                signs.push(item);
            }
        }

        while (!signs.empty()) {
            polish.add(signs.pop());
        }

        return polish;
    }

    //返回符号优先级：括号最低，+-其次，*/最高
    private int getPriority(String sign) {
        switch(sign) {
            case "(" :
            case ")" :
                return 0;
            case "+" :
            case "-" :
                return 1;
            default:
                return 2;
        }
    }

    //将数字和符号拆成一个个单元，按顺序保存
    private ArrayList<String> toArray(String s) {

        ArrayList<String> items = new ArrayList<>();

        char[] cs = s.toCharArray();

        for (int i = 0; i < cs.length; i ++) {
            if (cs[i] >= 48 && cs[i] <= 57) {
                 StringBuffer temp = new StringBuffer();

                while (i + 1 < cs.length && cs[i + 1] >= 48 && cs[i + 1] <= 57) {
                    temp.append(cs[i]);
                    i++;
                }

                temp.append(cs[i]);

                items.add(temp.toString());
            } else {
                items.add("" + cs[i]);
            }
        }

        return items;
    }
}