题解 | #四则运算#

1. 将一个表达式分成三部分，数字、运算符和括号部分，将括号里的表达式看做一个整体，又可以分成这样三部分，于是可以用递归解决。
2. 遇到数字就存到栈里；遇到加减运算符接下来还是存到栈里，遇到乘除运算符就取出栈顶运算完再放进栈里；遇到括号就用递归解决括号里的表达式。
3. 定义了一个运算符的自由度，代表该运算符前的括号是否是完整的，比如示例3+2*{1+2*[-4/(8-6)+7]}这样一个表达式中，第一个+号和第一个*号是0自由度的，其他不为0；但如果只看大括号{}里的部分即1+2*[-4/(8-6)+7]，此时1后面的+号、2后面的*号变成了0自由度，这在递归中可以解决。
4. 将原始表达式存到一个作为成员变量的字符数组，这样递归时只需要传递首尾两个参数，不需要频繁的截取数组或字符串。
5. 计算时用的double类型，最后输出时如果小数部分为0就取整输出。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = br.readLine();
        Solution sl = new Solution();
        double num = sl.getAnswer(input);
        if (Math.round(num) - num == 0) {
            System.out.println((int) num);
        } else {
            System.out.println(num);
        }
    }
}

class Solution {

    char[] chars;
    char[] brackets = {')', ']', '}'};
    char[] operators = {'+', '-', '*', '/'};

    //将表达式转换为字符数组成员变量，计算局部表达式时只需要传递两个下标
    public double getAnswer(String expression) {
        chars = expression.toCharArray();
        return calculate(0, chars.length);
    }

    public double calculate(int pos, int end) {
        Stack<Double> store = new Stack<>();

        while (pos < end) {
            char cur = chars[pos];
            double val = 0;
            if (cur == '(' || cur == '[' || cur == '{') {
                int target = findFreeTarget(chars, pos + 1, end, 1, brackets);
                val = calculate(pos + 1, target);
                pos = target + 1;
            } else if (Character.isDigit(cur)) {
                while (pos < end && Character.isDigit(chars[pos])) {
                    val = val * 10 + chars[pos] - '0';
                    pos++;
                }
            } else {
                //找到下一个自由度为0的运算符，计算这一段表达式的值
                int target = findFreeTarget(chars, pos + 1, end, 0, operators);
                switch (cur) {
                    case '+':
                        val = calculate(pos + 1, target);
                        break;
                    case '-':
                        val = -calculate(pos + 1, target);
                        break;
                    case '*':
                        val = store.pop() * calculate(pos + 1, target);
                        break;
                    default:
                        val = store.pop() / calculate(pos + 1, target);
                }
                pos = target;
            }
            store.push(val);
        }

        double answer = 0;
        while (!store.isEmpty()) {
            answer += store.pop();
        }
        return answer;
    }

    //找到下一个自由度为0的 + 号或 - 号, 定义自由度为该字符前左括号和右括号的个数
    public int findFreeTarget(char[] chars, int pos, int end, int freedom, char[] targets) {
        while (pos < end) {
            char cur = chars[pos];
            if (cur == '(' || cur == '[' || cur == '{') {
                freedom++;
            } else if (cur == ')' || cur == ']' || cur == '}') {
                freedom--;
            }
            if (freedom == 0) {
                for (char target : targets) {
                    if (cur == target) {
                        return pos;
                    }
                }
            }
            pos++;
        }
        return end;
    }
}