题解 | #表达式求值#

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String input = in.next();
        //先转换成字符数组
        char[] cs = input.toCharArray();
        //声明两个栈，注意泛型类型。
        //符号栈symbolStack用于临时存放操作符
        Stack<Character> symbolStack = new Stack<>();
        //输出栈outputStack用于存放后缀表达式（逆序的）
        Stack<String> outputStack = new Stack<>();

        //为了解决最左边就是减号的情况，在输出栈补个0
        //避免了计算时减法运算少个操作数，到那时处理将需要更复杂的逻辑
        if (cs[0]=='-'){
            outputStack.push("0");
        }
	  
        //挨个处理
        for (int i = 0; i < cs.length; i++){
            //数字记得把后面连续的数字拼接上，然后输出（入outputStack）
            if(isNumber(cs[i])){
                int num = cs[i] - 48;
                //若下一位未越界，且是数字
                while((i < cs.length-1) && isNumber(cs[i+1])){
                    num = num * 10 + cs[++i] - 48;
                }
                //下一位不是数字了，输出
                outputStack.push(num+"");            
            }
            //如果是左括号，入符号栈
            //注意如果后面紧跟着减号，也是在输出栈补个0
            else if (cs[i] == '('){
                if (cs[i+1] == '-'){
                    outputStack.push("0");
                }
                //左括号入符号栈
                symbolStack.push(cs[i]);
            }
            //如果是右括号，将符号栈中遇到左括号之前的所有运算符出栈，
            //并入输出栈，左括号也弹出，但不用入输出栈了，
            //这个右括号至此也可以丢弃了
            else if (cs[i] == ')'){
                while (symbolStack.peek() != '('){
                    outputStack.push(symbolStack.pop()+"");
                }
                symbolStack.pop();
            }
            //如果是运算符
            else {
                //循环判断符号栈顶是否是优先级>=该运算符的运算符，
                //是则弹出，并入输出栈，
                //>的在计算时先参与计算，
                //=的也要处理是因为运算从左到右法则
                while(!symbolStack.empty()
                    &&needPop(symbolStack.peek(),cs[i])){
                        outputStack.push(symbolStack.pop()+"");
                }
                //再将自己入符号栈
                symbolStack.push(cs[i]);
            }
        }
        //遍历完了，将符号栈中剩余元素弹出，放入输出栈
        while(!symbolStack.empty()){
            outputStack.push(symbolStack.pop()+"");
        }

        //处理完毕，此时输出栈中的元素出栈是逆序的，需要先倒一次
        Stack<String> suffixStack = new Stack<>();
        while(!outputStack.empty()){
            suffixStack.push(outputStack.pop());
        }
        //再声明一个栈用于处理计算过程中的数据
        Stack<Integer> calculateStack = new Stack<>();
        //对于后缀表达式栈suffixStack中的元素
        //计算的逻辑很简单了：
        //遇到数，直接入操作数栈
        //遇到运算符，取出操作数栈中栈顶的两个数，计算并将结果入操作数栈
        //直到后缀表达式栈为空，操作数栈中的元素即为所求
        while(!suffixStack.empty()){
            String e = suffixStack.pop();
            if((!e.equals("+"))&&(!e.equals("-"))&&
            (!e.equals("*"))&&(!e.equals("/"))){
                calculateStack.push(Integer.valueOf(e));
            }else{
                int a = calculateStack.pop();
                int b = calculateStack.pop();
                int c;
                switch (e) {
                    case "+" : c = b + a; break;
                    case "-" : c = b - a; break;
                    case "*" : c = b * a; break;
                    default : c = b / a; break;
                }
                calculateStack.push(c);
            }
        }
        int result = calculateStack.pop();
        System.out.println(result);
    }


    private static boolean isNumber(char c){
        return c >= 48 && c <= 57;
    }
    private static boolean needPop(char fromStack,char current){
        //栈顶运算符是*或/，则current是+-*/的优先级都不高于它，要弹出
        if(fromStack == '*' || fromStack == '/'){return true;}
        //栈顶是+或-，则current也是+或-才要弹出
        return (current == '+' || current == '-')
            && (fromStack == '+' || fromStack == '-');
    }
}