LeetCode_224.基本计算器

题目描述

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

代码实现

双栈的思想，数字栈和字符栈

class Solution {
    public int calculate(String s) {
    //******栈的预处理********
    Deque<Integer> nums = new ArrayDeque<>();
    nums.addLast(0);
    Deque<Character> ops = new ArrayDeque<>();
    s = s.replaceAll(" ","");
    char []cs = s.toCharArray();
    int n = cs.length;
    //处理每一个字符
    for(int i = 0 ; i < n ; i ++){
        char c = cs[i];
        // 处理 ( 左括号
        if(c==() ops.addLast(c);
        // 处理 ) 右括号
        else if (c == )){
            //操作符不空的情况下
            while(!ops.isEmpty()){
                char op = ops.peekLast();
                //不为左括号的情况下，计算
                if(op!=() calc(nums,ops);
                else{
                    //如果是左括号，就出栈，结束循环
                    ops.pollLast();
                    break;
                }
            }
        }else{
            //如果的数字的话    入nums栈
            if(isNum(c)){
                int u = 0 ; 
                while(i<n && isNum(cs[i])) u = u*10+(int)(cs[i++]-0);
                nums.addLast(u);
                i--;
            }
            //如果是运算符的话，如果前面是左括号，就先插入0，防止负数运算，如果不是，先运算完可以运算的操作
            else{
                if(i>0 && cs[i-1]==() nums.addLast(0);
                //如果运算符不为空，而且运算符也不是左括号，运算可以运算的部分
                while(!ops.isEmpty() && ops.peekLast()!=() calc(nums,ops);
                //插入运算符
                ops.addLast(c);
            }
        }
    }
    //当运算符不为空的情况继续计算直至运算完成
    while(!ops.isEmpty()) calc(nums,ops);
    //返回最终结果
    return nums.peekLast();
    }
    
    void calc(Deque<Integer> nums,Deque<Character> ops){
        // *******判断部分*******
        //数字不足时，无法计算
        if(nums.isEmpty() || nums.size()<2)   return;
        //没有运算符时，无法计算
        if(ops.isEmpty())   return ;
        //提出栈顶的两个数

        // *******计算部分*******
        int b = nums.pollLast(),a=nums.pollLast();
        char op = ops.pollLast();
        nums.addLast(op==+?a+b:a-b);
    }
	//判断字符是否的数字的函数
    boolean isNum(char c){
        return Character.isDigit(c);
    }
}