“This is the 27th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

The title

227. Basic Calculator II

Given a string expression s, you implement a basic calculator to evaluate and return its value.

Integer division preserves only integer parts.

Example 1:

Input: s = "3+2*2" Output: 7Copy the code

Example 2:

Input: s = "3/2" Output: 1Copy the code

Example 3:

Input: s = "3+ 5/2" Output: 5Copy the code

solution

Stack data structure

Train of thought

We get a whole string, and we have to know where a number is, where a symbol is, and where a space is to skip, and then we can add, subtract, multiply and divide.

  1. It’s easy to check if it’s a sign, just use isNaN(a). Since Spaces aren’t NaN either, satisfying NaN must be a sign here.
  2. We need to know how long the string of digits is. We start from the beginning, and each time we encounter a number (i.e! isNaN(a) && a ! = ' '), then we add the previous number *10 to the current number, such as 321 is 3*10 +2, and then 32*10 + 1 next time. And then when it comes to the next symbol, it stops adding and enters the calculation.

Since the operation has priority, multiplication and division takes precedence over addition and subtraction, we should first complete all the multiplication and division operations, save the results of the operation, and finally add up all the remaining numbers.

The specific steps are as follows:

  1. We declare a stack to store the data to be accumulated after processing. By default, the first digit is pushed into the stack with the operator “+”.
  2. Iterate through the string, get the complete number according to the above method, and push it according to the operator before the number. If it is “+”, push it directly; if it is “-“, push the negative number; if it is “* or/”, take out the top element of the stack and calculate the current number, and push it again. Since the complete number is determined when the next symbol is encountered, we will save the next symbol for the next number operation.
  3. Once we’re done, we walk through the stack, adding up all the numbers.

code

/ * * *@param {string} s
 * @return {number}* /
var calculate = function(s) {
    s = s.trim();
    let stack = [];
    let preSymbol = '+';
    let num = 0;
    for(let i=0; i<s.length; i++){// isNaN(' ') == false
        if(!isNaN(s[i]) && s[i] ! = =' '){
            num = num*10 + Number(s[i]);
        }
        if(isNaN(s[i]) || i == s.length -1) {switch(preSymbol){
                case '+': 
                    stack.push(num);
                    break;
                case The '-': 
                    stack.push(-num);
                    break;
                case The '*':
                    stack.push(stack.pop()*num);
                    break;
                case '/':
                    stack.push(parseInt(stack.pop()/num));
                    break;

            }
            preSymbol = s[i]
            num = 0; }}let res = 0;
    while(stack.length>0){
        res += stack.pop();
    }
    return res;
};
Copy the code

Complexity analysis

Time complexity: O(n), the first time through the entire string processing O(n), the second time summing up the worst case is O(n/2), so the total is still O(n).

Space complexity: O(n), requires a stack to maintain the numbers to be added, the worst case is O(n/2), therefore O(n).