题解 | #四则运算#

import java.util.*;//模板
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String str = sc.nextLine();
        str = str.replace("[","(");
        str = str.replace("{","(");
        str = str.replace("}",")");
        str = str.replace("]",")");
        //优化,考虑负数情况   空栈异常优化
        str = str.replace("(-","(0-");
        if(str.charAt(0)=='-') {
        	str = str.replace("-","0-");
        }
        //空格先不处理,作用是分隔字符为字符串数组
        
        
        String[] strs=toList(str);//转String[] 
        List<String> midToBack = midToBack(strs); // 中缀转后缀
        Stack<String> stk = new Stack<>();    // 存储中间结果
        // 逆波兰计算器
        stk.push("0");
        for (int i = 0; i < midToBack.size(); i++) {
            String tmp = midToBack.get(i);
            if (isOper(tmp)) {
                String num2 = stk.pop();
                String num1 = stk.pop();//空栈异常需优化
                String reuslt = cal(num1, tmp, num2);
                stk.push(reuslt);
            } else if(!"".equals(tmp)){ // 数字直接入栈     NumberFormatException  For input string: ""优化
                stk.push(tmp);
            }
        }
        System.out.println(stk.pop());
    }
    
    public static boolean isOper(String str) {
    	return "+".equals(str) || "-".equals(str) || "*".equals(str) || "/".equals(str) ||
          "(".equals(str) || ")".equals(str) || "[".equals(str) || "]".equals(str) ||
          "{".equals(str) || "}".equals(str);
    }

    public static int priority(String oper) {
    	if ("+".equals(oper) || "-".equals(oper)) {
    		return 0;
    	} else if ("*".equals(oper) || "/".equals(oper)) {
    		return 1;
    	} else {
    		return -1;
	  }
	}


    public static String cal(String num1, String oper, String num2) {
    	int result = 0;
	    int a = Integer.parseInt(num1);
	    int b = Integer.parseInt(num2);
		switch (oper) {
			case "+":
				result = a + b;
				break;
	        case "-":
	        	result = a - b;
	        	break;
	        case "*":
	        	result = a * b;
	        	break;
	        case "/":
	        	result = a / b;
	        	break;
		}
		return String.valueOf(result);
	}
   
//转String[]   目的是为了可以提炼出两位及以上的操作数
    public static String[] toList(String str){
    	StringBuffer sb=new StringBuffer();
    	String str1=str.replaceAll("\\s*", "");//去除字符串中所有空白符，不仅限于空格
    	String[] strs=new String[str1.length()];
    	for (int i = 0; i < str1.length(); i++) {
            char tmp = str1.charAt(i);
            if(Character.isDigit(tmp)){// if(isDigit(tmp)           	
            	sb.append(tmp);//sb.append(str.charAt(i));
            }
            else {
            	sb.append(" ");//与前面数字分割
            	sb.append(tmp);
            	sb.append(" ");//与后面数字分割
            }
    	}
    	str1=sb.toString();
    	// trim()删除字符串开头和结尾的空格
    	String str2=str1.trim();
    	strs=str2.split(" ");
    	return strs;
    }
    
//中缀转后缀   peek取数不弹出 pop取数并弹出
//操作符情形    
//1.当前操作符优先级>操作符栈顶,直接压入符号栈
//2.反之当前操作符优先级<=操作符栈顶,弹出操作符栈顶并压入结果栈
//3.当遇到)时,按序弹出到结果集直到匹配( ,匹配到(后直接丢掉符号栈里的(
    public static List<String> midToBack(String[] strs) {
        List<String> rlRoot = new ArrayList<>();
        Stack<String> stack1 = new Stack<>();   // 只用于保存操作符
        Stack<String> stack2 = new Stack<>();   // 用于保存中间结果
        for (int i = 0; i < strs.length; i++) {
        	String tmp=strs[i];
            if (isOper(tmp)) {   // 操作符要根据情况来入栈 1
                if (stack1.isEmpty()||"(".equals(tmp) ) {
                    // 如果 stack1 是空的，或者 tmp 是左括号，直接入栈     情形1
                    stack1.push(tmp);
                } else { // stack1 不是空的，且 tmp 不是左括号
                	if (")".equals(tmp)) {
                        // tmp 是右括号，则把 stack1 遇到左括号之前，全部倒入 stack2     情形3                		
                        while (!("(".equals(stack1.peek()))) {
                            stack2.push(stack1.pop());
                        }
                        stack1.pop();   // 丢掉左括号
                    } else {
                        // tmp 是 +-*/ 其中之一
                        while (!stack1.isEmpty() && priority(stack1.peek()) >= priority(tmp)) {
                            // 在 tmp 能够碾压 stack1 的栈顶操作符之前，把 stack1 的栈顶操作符倒入 stack 2 中  情形2
                            stack2.push(stack1.pop());
                        }
                        // 离开 while 时，要么 stack1 已经倒空了，要么就是现在 tmp 优先级大于  stack1.peek() 了  情形1
                        stack1.push(tmp);
                    }
                }
                
            } else { // 操作数直接入栈 2
                stack2.push(tmp);
            }
        }

        // stack1 剩余操作符全部倒入 stack2
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }

        // stack2 的逆序才是结果，所以要再倒一次
        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
//此后可不操作,也可直接返回栈
        // 现在 stack1 的元素倒出来的顺序就是后缀表达式
        while (!stack1.isEmpty()) {
        	rlRoot.add(stack1.pop());
        }

        return rlRoot;
    }

}