题解 | #表达式求值#

import java.util.*;
import java.util.regex.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        map.put(')', 0);
        map.put('(', 0);
        map.put('*', 2);
        map.put('/', 2);
        map.put('+', 1);
        map.put('-', 1);
        map.put('#', 1);
        Pattern p = Pattern.compile("[0-9]");
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            String str = in.nextLine()
                    .replaceAll("\\[", "(")
                    .replaceAll("]", ")")
                    .replaceAll("\\{", "(")
                    .replaceAll("}", ")");
             Stack<String> numStack = new Stack<String>();
            Stack<Character> symbolStack = new Stack<Character>();
            char[] chars = str.toCharArray();
            for (int i = 0; i < chars.length; i++) { 
                char c = chars[i];
                if ((c == '-' && i == 0) ||
                    (c == '-' && ((chars[i - 1] < '0' || chars[i - 1] > '9') && chars[i-1]!=')'))
                    ) { //处理负号，要注意下标顺序，先判断边界值，在判断前面的字符
                    c = '#';
                }
                if (c >= '0' && c <= '9') { //处理数字
                    StringBuilder sb = new StringBuilder(String.valueOf(c));
                    for(int j=i+1; j<chars.length;j++) { //处理两位数以上
                        if(chars[j]>='0' && chars[j] <= '9') {
                            sb.append(chars[j]);
                            i=j;
                        } else {
                            break;
                        }
                    }
                    numStack.push(sb.toString());
                } else if (c == '(') { //"(" 直接入栈
                    symbolStack.push(c);
                } else if (c != ')') { // 非")"的符号
                    if (symbolStack.isEmpty()) { //符号栈空直接入栈
                        symbolStack.push(c);
                    } else { 
                        while (!symbolStack.isEmpty()) {
                            if (map.get(c) > map.get(symbolStack.peek())) { //判断优先级
                                symbolStack.push(c);
                                break;
                            } else {
                                numStack.push(String.valueOf(symbolStack.peek()));
                                symbolStack.pop();
                            }
                        }
                        if(symbolStack.isEmpty()) { //优先级判断完成后栈空，入栈
                            symbolStack.push(c);
                        }
                    }
                } else if (c == ')') { //遇到 "(" ，符号栈依次出栈，直到"(" 出栈
                    while (!symbolStack.isEmpty()) {
                        if (symbolStack.peek() == '(') {
                            symbolStack.pop();
                            break;
                        } else {
                            numStack.push(String.valueOf(symbolStack.peek()));
                            symbolStack.pop();
                        }
                    }
                }
            }
            while (!symbolStack.isEmpty()) { //将剩余的符号按次序出栈
                numStack.push(String.valueOf(symbolStack.peek()));
                symbolStack.pop();
            }
            int length = numStack.size();
            Stack<String> currStack = new Stack<String>();
            for(int i=0;i<length;i++) { //反转后缀表达式栈
                currStack.push(numStack.peek());
                numStack.pop();
            }
            numStack.clear();
            double sum = 0;
            Stack<Double> sumStack = new Stack<Double>();
            for (int i = 0; i < length; i++) {
                String c = currStack.peek();
                if (p.matcher(c).find()) { //数字直接入结果栈
                    sumStack.add(Double.parseDouble(c));
                } else if (c.equals("#")) { //符号反转结果栈顶数字
                    sum = -sumStack.peek();
                    sumStack.pop();
                    sumStack.add(sum);
                } else { //其他运算符拿 栈顶下一个数字 - 栈顶数字 得到新栈顶数字在入栈
                    double b = sumStack.peek();
                    sumStack.pop();
                    double a = sumStack.peek();
                    sumStack.pop();
                    switch(c) {
                        case "+":
                            sum = a+b;
                            break;
                        case "-":
                            sum = a-b;
                            break;
                        case "*":
                            sum = a*b;
                            break;
                        case "/":
                            sum = a/b;
                            break;
                    }
                    sumStack.add(sum);
                }
                currStack.pop(); //操作每一步后后缀表达式栈要弹出栈顶元素
            }
            System.out.println((int)sum);
        }
    }
}