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:

- It's just a number
- 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.

The official account: the way of healthy development