LeetCode中227. 基本计算器 II题解-java

题目

227. 基本计算器 II

难度中等337

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

整数除法仅保留整数部分。

示例 1：

输入：s = "3+2*2"
输出：7

示例 2：

输入：s = " 3/2 "
输出：1

示例 3：

输入：s = " 3+5 / 2 "
输出：5

提示：

1 <= s.length <= 3 * 105
s 由整数和算符 ('+', '-', '*', '/') 组成，中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
题目数据保证答案是一个 32-bit 整数

题解

方法一：栈

思路

将字符串转化为字符数组，遍历，当遇到数时，判断此数字的大小，然后根据上一操作符，将栈中元素与此值进行运算（起始默认为0,），将运算后的结果重新放入栈中，最后栈中存储的元素即为最后加法运算的值，遍历栈，逐个加，将最后的和返回

代码实现

class Solution {
    public int calculate(String s) {
        // 存储结果
        Stack<Integer> numStack =  new Stack<>(); 
        // 存储上一操作运算符      
        char lastOp = '+';
        // 将字符串转化为字符数组
        char[] arr = s.toCharArray();
        // 遍历字符数组
        for(int i = 0; i < arr.length; i++){
            // 若为空格，则跳过此次循环
            if(arr[i] == ' ') continue;
            // 若为数字，判断此数字的值，然后判断操作符，与stack的值进行运算，把结果存入stack
            if(Character.isDigit(arr[i])){
                int tempNum = arr[i] - '0';
                while(++i < arr.length && Character.isDigit(arr[i])){
                    tempNum = tempNum * 10 + (arr[i] - '0');
                }
                i--;
                if(lastOp == '+') numStack.push(tempNum);
                else if(lastOp == '-') numStack.push(-tempNum);
                else numStack.push(res(lastOp,numStack.pop(), tempNum));
            }else if {
                // 若为操作符，则将操作符赋予lastOp操作符
                lastOp = arr[i];          
            } 
        }

        int ans = 0;
        // 遍历stack栈，遍历加，将结果输出返回
        for(int num : numStack) ans += num;
        return ans;
    }

    private int res(char op , int a, int b){
        if(op == '*') return a*b;
        else if(op == '/') return a/b;
             else if(op == '+') return a + b;
                  else return a - b;
    }
}

复杂度分析

提交详情

方法二：栈

思路

代码实现

class Solution {
    public int calculate(String s) {
        String str = s.replaceAll(" ", "");
        Deque<Integer> stack = new LinkedList<Integer>();
        char preSign = '+';
        int num = 0;
        int value = 0;
        for(int i = 0; i < str.length(); i++){
            if(Character.isDigit(str.charAt(i))){
                num = num * 10 + str.charAt(i) - '0';
            }
            if(!Character.isDigit(str.charAt(i)) || i == str.length() - 1){
                switch(preSign) {
                    case '+':
                        stack.push(num);
                        break;
                    case '-':
                        stack.push(-num);
                        break;
                    case '*':
                        stack.push(stack.pop() * num);
                        break;
                    default:
                        stack.push(stack.pop() / num);
                        break;                
                }
                preSign = str.charAt(i);
                 num = 0;
            }
        }
        while(!stack.isEmpty()){
            value += stack.pop();
        }
        return value;
    }
}