题解 | #牛牛计算器#

1、使用队列分别保存数字和运算符
2、遇到负数，则数字队列连续入队0和值运算符队列入队-号
3、运算规则是，运算符队列出一个运算符，数字队列出两个数字，同时将得到的值入队
4、符号入队时，从原来的队列中取上一个运算符，若当前运算符优先级大于上一个则入队，小于或者等于上一个优先级则
出队上一个运算符和两个数字计算，并将得到的值入队，再入队当前运算符
5、遇到‘）’时，一直出队计算到遇到"("



import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @return int整型
     */
    public int calculate (String s1) {
        String str = s1.replaceAll(" ","");
        List<String> stringList = new ArrayList<>();
        for (int i = 0; i < str.length(); i++) {
            stringList.add(str.substring(i, i + 1));
        }
        String opStr = " +-*/()";
        List<Integer> numList = new ArrayList<>();
        List<String> operatorList = new ArrayList<>();
        int kuoNum = 0;

        while (stringList.size() > 0) {
            String s = stringList.get(0);
            if (opStr.indexOf(s) > 0) {
                if (s.equals("(")) {
                    operatorList.add(s);
                    kuoNum++;
                } else if (s.equals(")")) {
                    // 当出现右括号后，要一直出运算符队列到左括号
                    String operator = operatorList.get(operatorList.size() -1);
                    while (!operator.equals("(")) {
                        int value2 = numList.get(numList.size() - 1);
                        int value1 = numList.get(numList.size() - 2);
                        int value = getValue(value1, value2, operator);
                        // 移除数字和运算符
                        numList.remove(numList.size() - 1);
                        numList.remove(numList.size() - 1);
                        operatorList.remove(operatorList.size() - 1);
                        numList.add(value);
                        operator = operatorList.get(operatorList.size() -1);
                        System.out.println("value1:" + value1 + " value2:" + value2 + " operator:" + operator + " value" + value);

                        System.out.println(value);
                    }
                    operatorList.remove(operatorList.size() - 1);
                } else { // 是运算符
                    // 如果是负数
                    if (s.equals("-") && numList.size() < operatorList.size() + 1 - kuoNum) {
                        numList.add(0);
                        operatorList.add(s);
                        stringList.remove(0);
                        continue;
                    }
                    if (operatorList.size() > 0) { // 运算符队列不为空
                        String operator = operatorList.get(operatorList.size() -1);

                        if ((operator.equals("+") || operator.equals("-")) && (s.equals("+") || s.equals("-"))) {
                            int value2 = numList.get(numList.size() - 1);
                            int value1 = numList.get(numList.size() - 2);
                            int value = getValue(value1, value2, operator);
                            // 移除数字和运算符
                            numList.remove(numList.size() - 1);
                            numList.remove(numList.size() - 1);
                            operatorList.remove(operatorList.size() - 1);
                            numList.add(value);
                            operatorList.add(s);
                        } else if ((operator.equals("*") || operator.equals("/")) && (s.equals("*") || s.equals("/"))) {
                            int value2 = numList.get(numList.size() - 1);
                            int value1 = numList.get(numList.size() - 2);
                            int value = getValue(value1, value2, operator);
                            // 移除数字和运算符
                            numList.remove(numList.size() - 1);
                            numList.remove(numList.size() - 1);
                            operatorList.remove(operatorList.size() - 1);
                            numList.add(value);
                            operatorList.add(s);
                        } // 上述是优先级一样的运算符，则先算队列里的

                        else if (operator.equals("*") || operator.equals("/")) { // 如果队列里的是乘除拿出来运算,这里保证了不会出现连续的*/符合
                            int value2 = numList.get(numList.size() - 1);
                            int value1 = numList.get(numList.size() - 2);
                            int value = getValue(value1, value2, operator);

                            // 移除数字和运算符
                            numList.remove(numList.size() - 1);
                            numList.remove(numList.size() - 1);
                            operatorList.remove(operatorList.size() - 1);
                            numList.add(value);
                            operatorList.add(s);
                            // 将新值放入
                        } else {
                            operatorList.add(s);
                        }
                    } else {
                        operatorList.add(s);
                    }
                }
                stringList.remove(0);
            } else {
                int currentValue = Integer.parseInt(s);
                numList.add(currentValue);
                stringList.remove(0);

                while (stringList.size() > 0 && !(opStr.indexOf(stringList.get(0)) > 0)) {
                    currentValue = currentValue * 10 + Integer.parseInt(stringList.get(0));
                    numList.remove(numList.size() - 1);
                    numList.add(currentValue);
                    stringList.remove(0);
                }

            }
        }


        while (operatorList.size() > 0) {
            if (operatorList.contains("*")) {
                int opIndex = operatorList.indexOf("*");
                String operator = operatorList.get(opIndex);
                int value1 = numList.get(opIndex);
                numList.remove(opIndex);
                int value2 = numList.get(opIndex);
                int value = getValue(value1, value2, operator);
                numList.set(opIndex, value);
                operatorList.remove(opIndex);
                continue;
            } else if (operatorList.contains("/")) {
                int opIndex = operatorList.indexOf("/");
                String operator = operatorList.get(opIndex);
                int value1 = numList.get(opIndex);
                numList.remove(opIndex);
                int value2 = numList.get(opIndex);
                int value = getValue(value1, value2, operator);
                numList.set(opIndex, value);
                operatorList.remove(opIndex);
                continue;
            }

            String operator = operatorList.get(0);
            int value1 = numList.get(0);
            int value2 = numList.get(1);
            int value = getValue(value1, value2, operator);
            // 移除数字和运算符
            numList.remove(0);
            //numList.remove(0);
            operatorList.remove(0);
            numList.set(0, value);
            System.out.println("value1:" + value1 + " value2:" + value2 + " operator:" + operator + " value" + value);

        }
        System.out.println("size:" + numList.size() + "  operatorList.size:" + operatorList.size());
        for (int i = 0; i < operatorList.size(); i++) {
            System.out.println(operatorList.get(i));
        }
        for (int i = 0; i < numList.size(); i++) {
            System.out.println("num:"+ i + " " + numList.get(i));
        }
        return numList.get(0);
    }

    public static int getValue(int value1, int value2, String operator) {
        if (operator.equals("*")) {
            return value1 * value2;
        } else if (operator.equals("/")) {
            return value1 / value2;
        } else if (operator.equals("+")) {
            return value1 + value2;
        } else if (operator.equals("-")) {
            return value1 - value2;
        }
        System.out.println("error operator:" + operator);
        return -1;
    }
}