Buckle 227-227. Basic calculator II

This problem is similar to the general computational solution, which can be solved by stack, and the particularity of the problem itself can be used for optimization.

Original question

Implement a basic calculator to evaluate the value of a simple string expression.

String expressions contain only four operators and spaces: nonnegative integers, +, -, *, / and. Integer division keeps only the integer part.

Example 1:

Input: "3 + 2 * 2"
Output: 7

Example 2:

Input: "3 / 2"
Output: 1

Example 3:

Input: "3 + 5 / 2"
Output: 5

Explain:

  • You can assume that all the expressions given are valid.
  • Do not use the built-in library function eval.

Original question url: https://leetcode-cn.com/problems/basic-calculator-ii

Answer

Stack

The first thing I think of about this problem is to use two stacks to store operators and numbers. When traversing, first put the corresponding characters on the stack. When encountering high-level operations (for example, / higher than +, -), directly put them on the stack. Otherwise, press out the numbers for calculation.

Let's look at the code:

class Solution {
    public int calculate(String s) {
        // Symbol stack
        Stack<Character> signStack = new Stack<>();
        // Digital stack
        Stack<Integer> numStack = new Stack<>();
        // Level used to store operators
        Map<Character, Integer> signLevelMap = new HashMap<>(6);
        // +, - is a low-level operator
        signLevelMap.put('+', 1);
        signLevelMap.put('-', 1);
        // *, / are high-level operators
        signLevelMap.put('*', 2);
        signLevelMap.put('/', 2);

        // ergodic
        int tempNum = 0;
        for (char charS : s.toCharArray()) {
            // Skip space
            if (charS == ' ') {
                continue;
            }

            Integer level = signLevelMap.get(charS);
            // If it's a number
            if (level == null) {
                tempNum = charS - '0' + tempNum * 10;
                continue;
            }

            // If the current is a symbol, press the previous number into numStack
            numStack.push(tempNum);
            tempNum = 0;

            // If there is no symbol before, press the current symbol directly into the stack
            if (signStack.empty()) {
                signStack.push(charS);
                continue;
            }

            // If there's a sign before, look at the two levels
            Character signBefore = signStack.peek();
            int levelBefore = signLevelMap.get(signBefore);
            // If current level > previous level
            if (level > levelBefore) {
                // Push the current symbol directly into the stack
                signStack.push(charS);
                continue;
            }

            // If the current level is less than or equal to the previous level, the previous symbol can be calculated directly
            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;
                }
                // Push the result into the stack again
                numStack.push(result);

                if (signStack.empty()) {
                    break;
                }
                signBefore = signStack.peek();
                levelBefore = signLevelMap.get(signBefore);
            }
            // Press symbol into signStack
            signStack.push(charS);
        }
        // Press the last number into numStack
        numStack.push(tempNum);

        // Calculate all the data in the stack
        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;
            }
            // Push the result into the stack again
            numStack.push(result);
        }
        return numStack.pop();
    }
}

The submission is successful, but the execution time only beats 43.97% of java submission records, which can definitely be optimized.

Combined with topic characteristics

The reason why the above is slow should be related to stack pressing and stack pushing, because this is equivalent to repeated calculation, traversal of the content that has been traversed, and re traversal. So what's the way to directly traverse and end it all at once?

There are only four operators +, -, *, / in the title. If they are +, -, they can't be calculated directly, because it's possible that the next operator is *, \, and the higher level operators will take precedence. But if it is *, /, it can be calculated directly, because there is no higher level than them.

So how to solve the direct calculation of +, -? In fact, we can treat the expression after +, - as a whole until we encounter +, -. As a whole, there are two situations:

  1. It's just a number
  2. The expression connected by *, / in this case, the result can be calculated directly, which is also a number.

In this way, we can guarantee that we can directly calculate the answer by traversing it once. Let's look at the code:

class Solution {
    public int calculate(String s) {
        // Find the first number first
        int[] resultArray = findNum(0, s);
        int result = resultArray[0];
        // Start traversal
        for (int i = resultArray[1] + 1; i < s.length(); i++) {
            char charS = s.charAt(i);
            // Skip spaces
            if (charS == ' ') {
                continue;
            }
            // *Directly calculate
            if (charS == '*' || charS == '/') {
                resultArray = findNum(i + 1, s);
                i = resultArray[1];
                result = (charS == '*') ? (result * resultArray[0]) : (result / resultArray[0]);
                continue;
            }
            // +, - take the later as a whole, and then calculate
            if (charS == '+' || charS == '-') {
                resultArray = findWholeNum(i + 1, s);
                i = resultArray[1];
                result = (charS == '+') ? (result + resultArray[0]) : (result - resultArray[0]);
            }
        }
        return result;
    }

    /**
     * Consider the following expression as a whole.
     * Returns an array, the subscript 0 represents the result of the expression, and the subscript 1 represents the subscript at the end of the expression.
     */
    public int[] findWholeNum(int index, String s) {
        // First number found
        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;
            }
            // End with +, -
            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;
    }

    /**
     * Find the next number.
     * Returns an array in which the subscript 0 represents the value of the number and the subscript 1 represents the subscript at the end of the number.
     */
    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};
    }
}

Submit OK, which takes 96.66% more time to execute than the java submission record, so it should be OK.

summary

The above is my answer to this question. I don't know if you understand it. This problem can be solved by stack or by the particularity of the problem itself.

If you are interested, you can visit my blog or pay attention to my official account and headline. Maybe there will be some surprises.

https://death00.github.io/

The official account: the way of healthy development

134 original articles published, 46 praised, 230000 visitors+
Private letter follow

Tags: calculator Java less github

Posted on Tue, 10 Mar 2020 20:38:36 -0700 by FRSH