题解 | #表达式求值#

通用的解决方案，可以参考里口上的解决方案。

import java.util.Scanner;
import java.util.Map;
import java.util.HashMap;
import java.util.Deque;
import java.util.ArrayDeque;

public class Main {

private static boolean isNumber(char c) {
    return Character.isDigit(c);
}

private static void calc(Deque<Integer> nums, Deque<Character> ops) {
    if (ops.isEmpty() || nums.size() < 2) return;
    int ans = 0;
    char operate = ops.pollLast();
    int x = nums.pollLast();
    int y = nums.pollLast();
    if (operate == '+') {
        ans = x + y;
    } else if (operate == '-') {
        ans = y - x;
    } else if (operate == '*') {
        ans = x * y;
    } else if (operate == '/') {
        ans = y / x;
    }
    nums.addLast(ans);
}


public static void main(String[] args) {
    Map<Character, Integer> map = new HashMap<Character, Integer>() {{
        put('+', 1);
        put('-', 1);
        put('*', 2);
        put('/', 2);
    }};

    Scanner sc = new Scanner(System.in);
    String s = sc.nextLine();
    s = s.replaceAll(" ", "");
    sc.close();
    s = s.replaceAll(" ", "");

    char[] cs = s.toCharArray();
    int n = cs.length;
    Deque<Character> ops = new ArrayDeque<Character>();
    Deque<Integer> nums = new ArrayDeque<Integer>();
    nums.addLast(0);
    for (int i = 0; i < n; i++) {
        char c = cs[i];
        if (c == '(') {
            ops.addLast(c);
        } else if (c == ')') {
            while (!ops.isEmpty()) {
                if (ops.peekLast() != '(') {
                    calc(nums, ops);
                } else {
                    // 将'('移除栈
                    ops.pollLast();
                    break;
                }
            }
        } else if (isNumber(c)) {
            // 取出一完整的数字
            int u = 0;
            int j = i;
            // 防止越界
            while (j < n && isNumber(cs[j])) u = u * 10 + cs[j++] - '0';
            i = j - 1;
            nums.addLast(u);
        } else { // 是一个操作符号
            // 防止（-3 + 5）or (+4 -5) 这种情况, 所有将表达式修改为(0-3+5)
            if (i > 0 && cs[i - 1] == '(') {
                nums.add(0);
            } else {
                // 有新的操作入栈时，将栈内的能计算的都计算掉
                // 只有当之前的运算符等级高于或者等于当前运算符号时，才进行计算.否则不计算
                // ( 5 + 10), 此时的'+'不需要对栈内的数据进行计算
                while (!ops.isEmpty() && ops.peekLast() != '(') {
                    Character prev = ops.peekLast();
                    if (map.get(prev) >= map.get(c)) {
                        calc(nums, ops);
                    } else {
                        break;
                    }
                }
            }
            // 将操作加入栈中.
            ops.addLast(c);
        }
    }
    while (!ops.isEmpty()) calc(nums, ops);
    System.out.printf("%d", nums.peekLast());
}

}