当前位置:   article > 正文

力扣227——227. 基本计算器 II

力扣227——227. 基本计算器 II

这道题类似于一般计算式解答,可以用栈解决,优化的时候可以利用题目本身的特殊性。

原题

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

字符串表达式仅包含非负整数,+, - ,*,/ 四种运算符和空格  。 整数除法仅保留整数部分。

示例 1:

输入: "3+2*2"
输出: 7
  • 1
  • 2

示例 2:

输入: " 3/2 "
输出: 1
  • 1
  • 2

示例 3:

输入: " 3+5 / 2 "
输出: 5
  • 1
  • 2

说明:

  • 你可以假设所给定的表达式都是有效的。
  • 请不要使用内置的库函数 eval。

原题url:https://leetcode-cn.com/problems/basic-calculator-ii

解答

这道题第一眼让我想到的,就是利用两个栈存储运算符和数字,遍历的时候先将相应字符入栈,当遇到运算等级高的(比如 、/ 相对于 +、-,等级更高),直接入栈,否则就压出数进行计算。

让我们看看代码:

class Solution {
    public int calculate(String s) {
        // 符号栈
        Stack<Character> signStack = new Stack<>();
        // 数字栈
        Stack<Integer> numStack = new Stack<>();
        // 用来存储运算符的等级
        Map<Character, Integer> signLevelMap = new HashMap<>(6);
        // +、-是低等级运算符
        signLevelMap.put('+', 1);
        signLevelMap.put('-', 1);
        // *、/是高等级运算符
        signLevelMap.put('*', 2);
        signLevelMap.put('/', 2);

        // 遍历
        int tempNum = 0;
        for (char charS : s.toCharArray()) {
            // 跳过空格
            if (charS == ' ') {
                continue;
            }

            Integer level = signLevelMap.get(charS);
            // 如果当前是数字
            if (level == null) {
                tempNum = charS - '0' + tempNum * 10;
                continue;
            }

            // 如果当前是符号,就把之前的数字压入numStack
            numStack.push(tempNum);
            tempNum = 0;

            // 如果之前没有符号,则直接将当前符号压入栈
            if (signStack.empty()) {
                signStack.push(charS);
                continue;
            }

            // 如果之前有符号,看看两者等级
            Character signBefore = signStack.peek();
            int levelBefore = signLevelMap.get(signBefore);
            // 如果当前等级 > 之前的等级
            if (level > levelBefore) {
                // 将当前符号直接压入栈
                signStack.push(charS);
                continue;
            }

            // 如果当前等级 <= 之前的等级,则可以直接计算之前的符号
            while (level <= levelBefore) {
                signStack.pop();
                int num2 = numStack.pop();
                int num1 = numStack.pop();
                int result = 0;
                switch (signBefore) {
                    case '+':
                        result = num1 + num2;
                        break;
                    case '-':
                        result = num1 - num2;
                        break;
                    case '*':
                        result = num1 * num2;
                        break;
                    case '/':
                        result = num1 / num2;
                        break;
                }
                // 将result再次压入栈中
                numStack.push(result);

                if (signStack.empty()) {
                    break;
                }
                signBefore = signStack.peek();
                levelBefore = signLevelMap.get(signBefore);
            }
            // 将符号压入signStack
            signStack.push(charS);
        }
        // 将最后一个数字压入numStack
        numStack.push(tempNum);

        // 将栈中所有数据进行计算
        int result = 0;
        while (!signStack.empty()) {
            char sign = signStack.pop();
            int num2 = numStack.pop();
            int num1 = numStack.pop();
            switch (sign) {
                case '+':
                    result = num1 + num2;
                    break;
                case '-':
                    result = num1 - num2;
                    break;
                case '*':
                    result = num1 * num2;
                    break;
                case '/':
                    result = num1 / num2;
                    break;
            }
            // 将result再次压入栈中
            numStack.push(result);
        }
        return numStack.pop();
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111

提交成功,但执行用时只战胜了43.97%的 java 提交记录,肯定是可以优化的。

结合题目特性

上面之所以慢,应该和压栈、入栈有关,因为这就相当于在重复计算,已经遍历过的内容,又重新遍历。那有什么办法可以直接一次性遍历完并结束呢?

题目里说只有+、-、*、/四种运算符,如果是+、-,是不可以直接计算的,因为有可能下一个运算符是*、\,等级高的会优先计算。但如果是*、/,就可以直接计算,因为不存在比它们等级更高的了。

那么到底该怎么解决+、-的直接计算呢?其实我们可以+、-之后的表达式看做一个整体,直到再次遇到+、-。针对这个整体,会有2种情况:

  1. 只是一个数字
  2. *、/连接的表达式,而这种情况其实可以直接计算出结果,这样也是一个数字了。

这样就可以保证只需遍历一遍就可以直接计算出答案了。接下来看看代码:

class Solution {
    public int calculate(String s) {
        // 先找到第一个数字
        int[] resultArray = findNum(0, s);
        int result = resultArray[0];
        // 开始遍历
        for (int i = resultArray[1] + 1; i < s.length(); i++) {
            char charS = s.charAt(i);
            // 空格就跳过
            if (charS == ' ') {
                continue;
            }
            // *、/ 就直接计算
            if (charS == '*' || charS == '/') {
                resultArray = findNum(i + 1, s);
                i = resultArray[1];
                result = (charS == '*') ? (result * resultArray[0]) : (result / resultArray[0]);
                continue;
            }
            // +、- 就将之后看成一个整体,再计算
            if (charS == '+' || charS == '-') {
                resultArray = findWholeNum(i + 1, s);
                i = resultArray[1];
                result = (charS == '+') ? (result + resultArray[0]) : (result - resultArray[0]);
            }
        }
        return result;
    }

    /**
     * 将之后的表达式看成一个整体。
     * 返回数组,下标0代表表达式的结果,下标1代表表达式结尾的下标。
     */
    public int[] findWholeNum(int index, String s) {
        // 找到第一个数
        int[] resultArray = findNum(index, s);
        int result = resultArray[0];
        int newIndex = resultArray[1] + 1;
        for (; newIndex < s.length(); newIndex++) {
            char charS = s.charAt(newIndex);
            if (charS == ' ') {
                continue;
            }
            // 遇到 +、- 就结束
            if (charS == '+' || charS == '-') {
                break;
            }

            if (charS == '*' || charS == '/') {
                resultArray = findNum(newIndex + 1, s);
                newIndex = resultArray[1];
                result = (charS == '*') ? (result * resultArray[0]) : (result / resultArray[0]);
            }
        }
        resultArray = new int[]{result, newIndex - 1};
        return resultArray;
    }

    /**
     * 找出下一个数字。
     * 返回数组,下标0代表数字的值,下标1代表数字结尾的下标。
     */
    public int[] findNum(int index, String s) {
        int num = 0;
        int newIndex = index;
        for (; newIndex < s.length(); newIndex++) {
            char charS = s.charAt(newIndex);
            if (charS == ' ') {
                continue;
            }

            if (charS > '9' || charS < '0') {
                break;
            }

            num = charS - '0' + num * 10;
        }
        return new int[]{num, newIndex - 1};
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80

提交OK,执行用时战胜了96.66%的 java 提交记录,这样应该也可以了。

总结

以上就是这道题目我的解答过程了,不知道大家是否理解了。这道题可以利用栈解答,也可以利用题目本身的特殊性进行更加高效的解答。

有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。

https://death00.github.io/

公众号:健程之道

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/秋刀鱼在做梦/article/detail/848187
推荐阅读
相关标签
  

闽ICP备14008679号