题解 | #四则运算#

思路：

• 先使用栈取出优先级最高的式子；
• 如果取出来的字符串长度小于3，则一定是负数，重新压入栈中；
• 如果取出来的字符串长度大于3，将字符串按照'+'，'-'，'*’，'/'拆分成有序的字符串列表，使列表中只包含数字（负号变成负数）、'*'、'/'；然后对列表进行运算；
• ---运算规则：从前往后做加法，遇到乘法（除法），则减去上一个加的数，并且使用上个数乘以（除以）下一个数，然后加上乘积（商）
• 将运算的结果重新压入栈，继续下一次运算；
• 如此递归运算，得到最终结果。

如：3+2*{1+2*[-4/(8-6)+7]}

• 先取出： 8-6 变成 [8, -6] 计算得 2，压入栈
• 再取出：-4/2+7 变成 [-4, /, 2, 7] 计算得 5，压入栈
• 再取出：1+2*5 变成 [1, 2, *, 5]计算得 11，压入栈
• 接着取出：3+2*11 变成 [3, 2, *, 11]计算得 25
• 最终结果：25

import java.util.*;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()){
            char[] array = sc.nextLine().toCharArray();
            System.out.println(calcular(array));
        }

    }

    public static int calcular(char[] array){
        Map<Character, Character> map = new HashMap<>();
        map.put('(', ')');
        map.put('[',']');
        map.put('{', '}');
        Stack<Character> stack = new Stack<>();

        for (int i = array.length-1; i >=0; i--){
            char c = array[i];
            if (stack.empty()){
                stack.push(c);
            } else{
               if (map.containsKey(c)){
                   // 循环取出栈中的数据，直到匹配value为止
                   String s = getSubInBrackets(map, stack, c);
                   String calculate = getAndCalculate(s);
                   for (int k = calculate.length()-1; k >=0; k--){
                       stack.push(calculate.charAt(k));
                   }
               } else {
                   stack.push(c);
               }
            }
        }

        // 取出栈中剩余的数据
        StringBuilder sb = new StringBuilder();
        while(true){
            if (stack.empty()){
                break;
            }
            sb.append(stack.pop());
        }
        String re = getAndCalculate(sb.toString());

        return Integer.parseInt(re);

    }

    private static String getAndCalculate(String sb) {
        // 取出的字符长度小于3，则直接当做一个整体的数字（一定是负数）放入栈中
        if (sb.length() < 3){
            return sb;
        }
        // 两个符号之间的数为要计算的数，作为整体； 负号与数字一起作为一个整体，使整个运算中只有加法、乘法、除法
        List<String> numList = handleMinus(sb);

        int sum = 0;
        int lastNum = 0;  // 上一个数，可能为计算后的数
        List<String> add = new ArrayList<>();
        for (int j = 0; j < numList.size(); ){
            int xj = 0;
            if (numList.get(j).equals("*")) {
                sum -= lastNum;  // 减去上一个已加的数
                xj = lastNum * Integer.parseInt(numList.get(j+1)); // 上个数*下一个数
                lastNum = xj; // 乘积作为下个运算的上一个数
                sum += xj; // 加上积
                j += 2;
            } else if (numList.get(j).equals("/")){
                sum -= lastNum;  // 减去上一个已加的数
                xj = lastNum / Integer.parseInt(numList.get(j+1)); // 上一个数/下一个数
                lastNum = xj; // 运算结果作为下一个运算的上一个数
                sum += xj; // 加上运算结果
                j += 2;
            } else {
                sum += Integer.parseInt(numList.get(j)); // 加上当前数
                lastNum = Integer.parseInt(numList.get(j));
                j++;
            }
        }
        return String.valueOf(sum);
    }

    /**
     * 处理减号和负号，分割数字和符号，最终只剩下数字，*，/
     * 如例子：8-6  变成 [8, -6]
     * @param sb
     * @return
     */
    private static List<String> handleMinus(String sb) {
        int start = 0;
        int end = 0;
        List<String> numList = new ArrayList<>();
        for (int i = 0; i < sb.length(); i++){
            char sign = sb.charAt(i);
            if (sign == '+') {
                numList.add(sb.substring(start,end));
                start = end = i+1;
            } else if (sign == '*' || sign == '/'){
                numList.add(sb.substring(start,end));
                numList.add(String.valueOf(sign));
                start = end = i+1;
            } else if (sign == '-'){
                if(start < end){
                    numList.add(sb.substring(start,end));
                }
                start = end = i;
                end += 1;
            } else{
                end++;
            }
        }
        if (end > start) {
            numList.add(sb.substring(start));
        }
        return numList;
    }

    /**
     * 获取括号内的字符串
     *
     * @param map
     * @param stack
     * @param c
     * @return
     */
    private static String getSubInBrackets(Map<Character, Character> map, Stack<Character> stack, char c) {
        StringBuilder sb = new StringBuilder();
        while(true){
            Character pop = stack.pop();
            if (pop.equals(map.get(c))){
                break;
            }
            sb.append(pop);
        }
        return sb.toString();
    }
}