[数据结构与算法]中缀转后缀表达式，后缀表达式计算

四则运算表达式计算

public class Arithmetic {
    private static final Map<String, Integer> sign = new HashMap();
    private static final List<String> operation = Arrays.asList("+", "-", "(", ")", "/", "*");

    static {
        //sign.put(")", Integer.valueOf("3"));
        sign.put("*", Integer.valueOf("2"));
        sign.put("/", Integer.valueOf("2"));
        sign.put("+", Integer.valueOf("1"));
        sign.put("-", Integer.valueOf("1"));
        sign.put("(", Integer.valueOf("0"));
    }

    public static void main(String[] args) {
        System.out.println(reverseExpressionCompute("(1+2)*(3+4)"));
    }

    //将表达式拆分成一个一个单元
    private static List<String> toStringList(String s) {
        char[] c = s.toCharArray();
        int lastIndex = 0;
        List<String> list = new ArrayList<>();
        for (int i = 0; i < c.length; i++) {
            if (operation.contains(String.valueOf(c[i])) || i == c.length - 1) {
                if (lastIndex != i) {
                    list.add(s.substring(lastIndex, i));
                }
                list.add(String.valueOf(c[i]));
                lastIndex = i + 1;
            }
        }
        return list;
    }

    //转成后缀表达式
    private static List<String> toSuffixExpression(String s) {
        List<String> list = toStringList(s);
        Stack<String> stack = new Stack<>();
        List<String> result = new ArrayList<>();
        for (int i = 0; i < list.size(); i++) {
            //如果遇到操作数，我们就直接将其输出。
            if (list.get(i).matches("[0-9a-z]*")) {
                result.add(list.get(i));
            }
            //如果遇到操作符，则我们将其放入到栈中，遇到左括号时我们也将其放入栈中。
            //System.out.println(list.get(i));
            //System.out.println(operation.contains(list.get(i)));
            if (operation.contains(list.get(i))) {
                //如果遇到一个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为止。注意，左括号只弹出并不输出。
                if (")".equals(list.get(i))) {
                    String q = stack.pop();
                    while (!stack.isEmpty() && !q.equals("(")) {
                        result.add(q);
                        q = stack.pop();
                    }
                } else if ("(".equals(list.get(i))) {
                    stack.push(list.get(i));
                } else if (stack.isEmpty() || sign.get(stack.peek()) < sign.get(list.get(i))) {
                    stack.push(list.get(i));
                } else {
                    result.add(stack.pop());
                    while (!stack.isEmpty() && sign.get(stack.peek()) >= sign.get(list.get(i))) {
                        result.add(stack.pop());
                    }
                    stack.push(list.get(i));
                }
            }
            if (i == list.size() - 1) {
                while (!stack.isEmpty()) {
                    result.add(stack.pop());
                }
            }
        }
        return result;
    }

    private static int reverseExpressionCompute(String string) {
        List<String> list = toSuffixExpression(string);
        Stack<String> stack = new Stack<>();
        for (String s : list) {
            if (!operation.contains(s)) {
                stack.push(s);
            } else {
                String b = stack.pop();
                String a = stack.pop();
                stack.push(counter(a, b, s).toString());
            }
        }
        return Integer.parseInt(stack.pop());
    }

    private static Integer counter(String a, String b, String ope) {
        if (ope.equals("+")) {
            return Integer.parseInt(a) + Integer.parseInt(b);
        } else if (ope.equals("-")) {
            return Integer.parseInt(a) - Integer.parseInt(b);
        } else if (ope.equals("*")) {
            return Integer.parseInt(a) * Integer.parseInt(b);
        } else {
            return Integer.parseInt(a) / Integer.parseInt(b);
        }
    }

}