题解 | #表达式求值#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 返回表达式的值
     * @param s string字符串 待计算的表达式
     * @return int整型
     */
    public int solve (String s) {
        List<String> midList=midToList(s);//处理两个数字相邻的情况，所以转换为List<String>
        List<String> postList=midToPost(midList);//中缀转后缀
        return compute(postList);//后缀计算
    }
    public List<String> midToList(String s){
        List<String> res=new ArrayList<>();
        char[] c=s.toCharArray();
        String mutiCount="";
        int i=0;
        while(i<c.length){
            if(Character.isDigit(c[i])){//如果是数字要把连续的数字组成一个字符串加入list
                mutiCount+=c[i++];
                while(i<c.length&&Character.isDigit(c[i])){
                    mutiCount+=c[i++];
                }
                res.add(mutiCount);
                mutiCount="";
            }else{//不是数字直接作为字符串加入list
                res.add(c[i++]+"");
            }
        }
        return res;
    }
    public List<String> midToPost(List<String> midList){//中序变后续
        Stack<String> stack=new Stack<>();//符号栈
        List<String> res=new ArrayList<>();
        for(int i=0;i<midList.size();i++){
            String s=midList.get(i);
            if(isNumber(s)){
                res.add(s);
            }else if(s.equals("(")){
                stack.push(s);
            }else if(s.equals(")")){
                String tmp=stack.pop();
                while(!tmp.equals("(")){
                    res.add(tmp);
                    tmp=stack.pop();
                }
            }else if(s.equals("*")||s.equals("/")){//把大于等于此运算符的符号都出栈,直到遇到(或者比此运算符小的
                if(!stack.isEmpty()){
                    while(!stack.isEmpty() && (stack.peek().equals("*")||stack.peek().equals("/")) ){
                        res.add(stack.pop());
                    } 
                }
                stack.push(s);
            }else{//+ - stack中（之前的所有操作符都出来
                if(!stack.isEmpty()){//把大于等于此运算符的符号都出栈,直到遇到(或者比此运算符小的
                    while(!stack.isEmpty() && !stack.peek().equals("(")){
                        res.add(stack.pop());
                    }
                }
                stack.push(s);
            }
        }
        while(!stack.isEmpty()){
            res.add(stack.pop());
        }
        return res;
    }

    public int compute(List<String> postList){
        Stack<Integer> stack=new Stack<>();//操作数栈
        for(int i=0;i<postList.size();i++){
            String s=postList.get(i);
            if(isNumber(s)){
                stack.push(Integer.parseInt(s));
            }else{
                int num2=stack.pop();
                int num1=stack.pop();
                switch(s){
                    case "+":
                        stack.push(num1+num2);
                        break;
                    case "-":
                        stack.push(num1-num2);
                        break;
                    case "*":
                        stack.push(num1*num2);
                        break;
                    case "/":
                        stack.push(num1/num2);
                        break;
                }
            }
        }
        return stack.pop();
    }
    public boolean isNumber(String s){
        for(int i=0;i<s.length();i++){
            if(!Character.isDigit(s.charAt(i))){
                return false;
            }
        }
        return true;
    }

}