# 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

### 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;
// Start traversal
for (int i = resultArray + 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;
result = (charS == '*') ? (result * resultArray) : (result / resultArray);
continue;
}
// +, - take the later as a whole, and then calculate
if (charS == '+' || charS == '-') {
resultArray = findWholeNum(i + 1, s);
i = resultArray;
result = (charS == '+') ? (result + resultArray) : (result - resultArray);
}
}
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;
int newIndex = resultArray + 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;
result = (charS == '*') ? (result * resultArray) : (result / resultArray);
}
}
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+

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