力扣772 基本计算器 III_基本计算器3

772. 基本计算器 III

实现一个基本的计算器来计算简单的表达式字符串。

表达式字符串只包含非负整数，算符 +、-、*、/ ，左括号 ( 和右括号 ) 。整数除法需要 向下截断 。

你可以假定给定的表达式总是有效的。所有的中间结果的范围为 [-2^31, 2^31 - 1] 。

示例 1：

输入：s = "1+1"
输出：2
示例 2：

输入：s = "6-4/2"
输出：4
示例 3：

输入：s = "2*(5+5*2)/3+(6/2+8)"
输出：21
示例 4：

输入：s = "(2+6*3+5-(3*14/7+2)*5)+3"
输出：-12
示例 5：

输入：s = "0"
输出：0
 

提示：

1 <= s <= 10^4
s 由整数、'+'、'-'、'*'、'/'、'(' 和 ')' 组成
s 是一个 有效的 表达式

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/basic-calculator-iii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

成功，比较难的模拟题，有点耐心就可以写

方法：栈非递归写法

老师教的：先乘除，后加减，有括号的先算括号里的，说明了这三者的优先级

1. 先处理括号
2. 再处理乘除
3. 最后处理加减

具体写法

1. 数字记录左边界，从0开始，遇到符号，从符号下一个开始
2. 遇到符号，检查前面数字左边界是否有空隙，有空隙追加数字
3. 遇到右括号进行拆括号操作
   • 找到当前位置到上一个左括号的范围
   • 计算这一段里面的乘除法
     • 非乘除号直接扔进一个新的栈，先不处理
     • 遇到乘除取出左右数字，算完之后塞回去
     • 还原原始栈内容
   • 计算这一段里面的加减法
     • 默认前一个数字0
     • 遇到符号进行计算，取出下一个数字
     • 计算结果累计回数字
     • 最后计算的数值放回原始栈
4. 其他符号，数字，直接扔栈里，先不处理
5. 考虑到不想写额外处理，前面补一个左括号，最终当做遇到右括号进行拆括号处理一次
6. 拿出栈顶

class Solution {
        public int calculate(String s) {
            Stack<String> stack = new Stack<>();
            //补一个左括号，最后当做有括号处理
            stack.push("(");
            int n = s.length();
            int j = 0;
            for(int i = 0; i < n; i++){
                char c = s.charAt(i);
                if(Character.isDigit(c)) continue;
                if(i>j)stack.push(s.substring(j,i));
 
                j = i+1;
                if(c == ')'){
                    //先拆掉所有括号
                    calculateNoBacket(stack);
                }else{
                    stack.push(String.valueOf(c));
                }
            }
            //最后非括号情况会有数字，补一个数
            if(j<n) stack.push(s.substring(j,n));
            //计算整个无括号表达式
            calculateNoBacket(stack);
            return Integer.parseInt(stack.peek());
 
        }
 
        /**
         * 拆括号，拆出当前位置到上一个左括号的表达式
         */
        private void calculateNoBacket(Stack<String> stack){
            Stack<String> tmp = new Stack<>();
            boolean hasMulDiv = false;
            while (!"(".equals(stack.peek())){
                if(stack.peek().equals("*") || "/".equals(stack.peek()))
                    hasMulDiv = true;
                tmp.push(stack.pop());
            }
            stack.pop();
 
 
            if(hasMulDiv) calculateMulDiv(tmp);
            int num = calculateAddSub(tmp);
            stack.push(String.valueOf(num));
        }
 
        /**
         * 算加减，负数也不用特别处理（因为必然拿到前面是0）
         */
        private int calculateAddSub(Stack<String> stack){
            int num = 0;
            while (!stack.isEmpty()){
                String str = stack.pop();
                if(!"+".equals(str) && !"-".equals(str)){
                    num = Integer.parseInt(str);
                    continue;
                }
 
                int num2 = Integer.parseInt(stack.pop());
                if("+".equals(str)){
                    num = num+num2;
                }else{
                    num = num-num2;
                }
            }
            return num;
        }
 
        /**
         * 算乘除，非乘除号的都不管（注意，不用处理负数，最后加减会处理，(-5)*3=-(5*3),不影响结果）
         * 乘除号的算出结果放左侧栈
         * 最后需放回到原始栈
         */
        private void  calculateMulDiv(Stack<String> stack){
            Stack<String> tmp = new Stack<>();
            while (!stack.isEmpty()){
                String str = stack.pop();
                if (!"*".equals(str) && !"/".equals(str)){
                    tmp.push(str);
                    continue;
                }
                int numA = Integer.parseInt(tmp.pop());
                int numB = Integer.parseInt(stack.pop());
 
                if("*".equals(str)){
                    tmp.push(String.valueOf(numA*numB));
                }else{
                    tmp.push(String.valueOf(numA/numB));
                }
 
            }
 
            while (!tmp.isEmpty()){
                stack.push(tmp.pop());
            }
        }
 
    }

其实是自己转载自己（给个力扣上的自己这篇题解链接，方便大家看）