数据结构：栈、逆波兰

 测试 

public class 逆波兰计算器 {
    public static void main(String[] args) {
        String s1 = "30 4 + 5 * 6 -";//(30+4)*5-6
        String s2 = "3 4 + 5 * 6 -"; //(3+4)x5-6
        System.out.println(result(getList(s1)));
        System.out.println(result(getList(s2)));
    }

    public static ArrayList getList(String s) {
        ArrayList arr = new ArrayList<>();
        String[] str = s.split(" ");
        for (String ele : str) {
            arr.add(ele);
        }
        return arr;
    }

    public static int result(ArrayList arr) {
        Stack st = new Stack();
        for (String ele : arr) {
            if (ele.matches("\d+")) {
                st.push(ele);
            } else {
                int num1 = Integer.parseInt(st.pop());
                int num2 = Integer.parseInt(st.pop());
                int temp = 0;
                switch (ele) {
                    case "+":
                        temp = num2 + num1;
                        break;
                    case "-":
                        temp = num2 - num1;
                        break;
                    case "*":
                        temp = num2 * num1;
                        break;
                    case "/":
                        temp = num2 / num1;
                        break;
                }
                st.push(String.valueOf(temp));
            }
        }
        return Integer.parseInt(st.pop());
    }
}

public class 中缀转后缀 {
    public static void main(String[] args) {
        String s1 = "(30+4)*5-6";// "30 4 + 5 * 6 -"
        ArrayList arr = getList2(s1);
        System.out.println(arr);
    }

    public static ArrayList getList2(String s) {
        int x = 0;
        String temp = "";
        ArrayList arr = new ArrayList<>();
        while (x < s.length()) {
            if (Character.isDigit(s.charAt(x))) {
                //如果是数字
                while (x < s.length() && Character.isDigit(s.charAt(x))) {
                    temp += s.substring(x, x + 1);
                    x++;
                }
                arr.add(temp);
                temp = "";
            } else {
                arr.add(s.substring(x, x + 1));
                x++;
            }
        }
        return arr;
    }

    public static String result2(ArrayList arr) {
        Stack st1 = new Stack();//符号栈
        ArrayList str = new ArrayList();
        for (String ele : arr) {
            if (ele.matches("\d+")) {
                str.add(ele);
            } else if (st1.isEmpty() || ele.equals("(")) {
                st1.push(ele);
            } else if (ele.equals(")")) {
                while (!st1.peek().equals("(")) {
                    str.add(st1.pop());
                }
                st1.pop();
            } else {
                while (!st1.isEmpty() && compare(ele) <= compare(st1.peek())) {
                    str.add(st1.pop());
                }
                st1.push(ele);
            }
        }
        while (!st1.isEmpty()) {
            str.add(st1.pop());
        }
        //字符串拼接
        StringBuilder sb = new StringBuilder();
        for (String s : str) {
            sb.append(s);
            sb.append(" ");
        }
        return sb.toString().trim();
    }


    public static int compare(String s) {
        int x = 0;
        if (s.equals("+") || s.equals("-")) {
            x = 1;
        } else if (s.equals("*") || s.equals("/")) {
            x = 2;
        }
        return x;
    }
}