“This is the 15th day of my participation in the December Gwen Challenge. See details: The Last Gwen Challenge 2021”

227. Basic Calculator II

Power button link

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

Tip:

  • 1 <= s.length <= 3 * 105
  • S consists of integers and operators (‘+’, ‘-‘, ‘*’, ‘/’) separated by Spaces
  • S represents a valid expression
  • All integers in the expression are non-negative integers and are in the range [0, 231-1]
  • The problem data guarantees that the answer is a 32-bit integer

The stack

Train of thought

For this problem we use the idea of a stack to step through expressions

We need one here

The ope variable holds the operator (+ – * /), and uses a num to hold the number from the current scan of the string, and adds the current string item and num if they are consecutive numbers.

So if we get theta

  • Ope =’+’ and a num, putting num directly on the stack

  • Ope =’-‘ and a num, putting -num directly on the stack

If we add two values, we simply add the number to the stack. If we subtract, we treat it as -num and put the negative of num on the stack

So if we get theta

  • Ope =’ * ‘and a num, so you need to pop the top element on the stack and push the result in

  • Ope =’/’ and a num, then pop the top element of the stack and push the result in.

Because multiplication and division has a higher priority than addition and subtraction, when it comes to multiplication and division, we need to take out the value to the left of the multiplication and division symbol from the top of the stack, and put the result of the operation into the stack after calculating with the value to the right of the current one.

  • Ope =’+’ num=’3′ is required when iterating to the end of the expression 3, so the condition I ===s.length-1 is added

Each push or operation is performed on the operator and num before the next operator is encountered, but there are no operators at the end of the expression, only numbers, so the operation begins when the last digit is iterated

In addition to pay attention to retain only integer division integer part, so here we are using the | operator to keep the integer part.

Finally, we add up all the elements in the stack to get our result

var calculate = function (s) {
    // Remove Spaces on both sides and in the middle
    s = s.trim()
    s = s.replaceAll(' '.' ')
    var stack = []
    var num = ' '
    var ope = '+'
    for (var i = 0; i < s.length; i++) {
        var item = s[i]
        if (!isNaN(Number(item))) {
            num += item
        }
        if (isNaN(Number(item)) || i === s.length - 1) {
            switch (ope) {
                case '+':
                    stack.push(+num)
                    break
                case The '-':
                    stack.push(-num)
                    break
                case The '*':
                    stack.push(stack.pop() * num)
                    break
                case '/':
                    stack.push(stack.pop() / num | 0)
            }
            ope = item
            num = ' '}}var res = 0
    while (stack.length) {
        res += stack.pop()
    }   
    return res
};
Copy the code