题解 | #表达式求值# 抽取没有括号的表达式

import java.math.*;
import java.text.CharacterIterator;
import java.text.StringCharacterIterator;
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.stream.*;
import java.util.regex.*;
import java.util.function.*;

public class Main {

    static Map<String, IntBinaryOperator> OP_MAP = new
    HashMap<String, IntBinaryOperator>() {
        {
            put("+", Integer::sum);
            put("-", (a, b)->a - b);
            put("*", (a, b)->a * b);
            put("/", (a, b)->a / b);
        }
    };

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String line = in.nextLine();
        if (!line.startsWith("(")) {
            line = String.format("(%s)", line);
        }

        System.out.println(compute(line));
    }
    // 有括号的表达式
    static int compute(String line) {
        LinkedList<String> stack = new LinkedList<>();
        boolean lastIsNum = false;
        for (int i = 0; i < line.length();) {
            char c = line.charAt(i);
            if (c == '(' || c == '+' || (c == '-' && lastIsNum) || c == '*' || c == '/') {
                stack.push(String.valueOf(c));

                lastIsNum = false;
                i++;
            } else if (c == '-' || Character.isDigit(c)) {
                StringBuilder sb = new StringBuilder(String.valueOf(c));
                i++;
                while (i < line.length() && Character.isDigit(line.charAt(i))) {
                    sb.append(line.charAt(i));
                    i++;
                }
                stack.push(sb.toString());

                lastIsNum = true;
            } else if (c == ')') {
                List<String> list = new ArrayList<>();
                while (!"(".equals(stack.peek())) {
                    list.add(stack.pop());
                }
                stack.pop();
                Collections.reverse(list);
                stack.push(String.valueOf(computeSingle(list)));

                lastIsNum = true;
                i++;
            }
        }
        return Integer.parseInt(stack.pop());
    }
    // 没有括号的表达式。计算两遍，第一遍只计算乘除，第二遍只计算加减
    static int computeSingle(List<String> list) {
        // 只计算乘除
        Deque<String> deque = new LinkedList<>();
        Iterator<String> it = list.iterator();
        while (it.hasNext()) {
            String curr = it.next();
            if (!curr.equals("*") && !curr.equals("/")) {
                deque.offerLast(curr);
            } else {
                String op = curr;
                int a = Integer.parseInt(deque.pollLast());
                int b = Integer.parseInt(it.next());
                int result = OP_MAP.get(op).applyAsInt(a, b);
                deque.offerLast(String.valueOf(result));
            }
        }
        // 只计算加减
        int result = 0;
        while (!deque.isEmpty()) {
            String curr = deque.pollFirst();
            if (!curr.equals("+") && !curr.equals("-")) {
                result = Integer.parseInt(curr);
            } else {
                String op = curr;
                int a = result;
                int b = Integer.parseInt(deque.pollFirst());
                result = OP_MAP.get(op).applyAsInt(a, b);
            }
        }
        return result;
    }
}