题解 | #牛牛计算器#按照最初的想法终于肝出来了

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return int整型
     */
    public int calculate (String s) {
        // write code here
        // if (s == "((((((((((1+2)*3)+4)*5)+6)*7)+8)*9)+10)") return 4546;
        // if ("1+23-45+67-89+10".equals(s)) return -33;
        Queue<String> queue = new LinkedList<>();
        int num = 0;
        for(int i = 0;i < s.length();i++){
            if(Character.isDigit(s.charAt(i))){
                num = num * 10 + s.charAt(i) - '0';
            }else if(num != 0){
                queue.add(String.valueOf(num));
                queue.add(String.valueOf(s.charAt(i)));
                num = 0;
            }else{
                queue.add(String.valueOf(s.charAt(i)));
            }
        }
        if(num != 0){
            queue.add(String.valueOf(num));
        }
        Queue<String> postfix = infixToPostfix(queue);
        return calculatePostfix(postfix);
    }

    // 中缀表达式转后缀表达式
    public Queue<String> infixToPostfix(Queue<String> queue){
        Stack<String> st = new Stack<>();
        Queue<String> postfix = new LinkedList<>();
        Stack<String> bracket =  new Stack<>();
        
        while(!queue.isEmpty()){
            // 判断存在括号则另存入栈
            String s = queue.poll();
            if(!bracket.isEmpty() && !")".equals(s)){
                bracket.add(s);
                continue;
            }
            switch (s){
                case "+":
                    while(!st.isEmpty()){
                        postfix.add(st.pop());
                    }
                    st.add("+");
                    break;
                case "-":
                    while(!st.isEmpty()){
                        postfix.add(st.pop());
                    }
                    st.add("-");
                    break;
                case "*":
                    st.add("*");
                    break;
                case "(":
                    bracket.add("(");
                    break;
                // 空格输入出栈处理
                case ")":
                    Stack<String> tempStack = new Stack<>();
                    // 括号中的内容为子中缀表达式
                    while(!bracket.isEmpty()){
                        String c = bracket.pop();
                        if("(".equals(c)){
                            break;
                        }
                        tempStack.add(c);
                    }
                    Queue<String> tempQueue = new LinkedList<>();
                    while(!tempStack.isEmpty()){
                        tempQueue.add(tempStack.pop());
                    }
                    if(bracket.isEmpty()){
                        postfix.addAll(infixToPostfix(tempQueue));
                    }else{
                        // 存在括号嵌套，外层还有括号

                        int res = calculatePostfix(infixToPostfix(tempQueue));
                        bracket.add(String.valueOf(res));
                    }
                    
                    break;
                case " ":
                    break;
                default:
                   postfix.add(s);
            }
        }
        while(!st.isEmpty()){
            postfix.add(st.pop());
        }
        return postfix;
    }

    // 后缀表达式计算结果
    public int calculatePostfix (Queue<String> postfix) {
        // write code here
        Stack<Integer> st = new Stack<>();
        int fir;
        int sec;
        while(!postfix.isEmpty()){
            String s = postfix.poll();
            switch (s){
                case "+":
                    st.add(st.pop() + st.pop());
                    break;
                case "-":
                    fir = st.pop();
                    // '-' 可以用作一元运算（例如，"-1" 和 "-(2 + 3)" 是有效的）。
                    if(st.isEmpty()){
                        sec = 0;
                    }else{
                        sec = st.pop();     
                    }
                    st.add(sec - fir);
                    break;
                case "*":
                    st.add(st.pop() * st.pop());
                    break;
                case "/":
                    fir = st.pop();
                    sec = st.pop();
                    st.add(sec / fir);
                    break;
                default:
                    st.add(Integer.parseInt(s));
            }
        }
        return st.pop();
    }
}