“This is the 20th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

[topic address]

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
  • sIntegers and operators(' + ', '-', '*', '/')Is separated by some Spaces
  • sSaid aValid expression
  • All integers in the expression are non-negative integers and are in range[0, 231-1) 内
  • The problem data guarantees that the answer is a 32-bit integer

This problem requires us to return the operation result of the input string. We can maintain the current operator and value through two stacks, and take out the top element of the stack each time for calculation. The specific solution is as follows:

  1. Create operator stack to store operators
  2. Create a value stack to store values
  3. Iterate over the input string expression, pushing the corresponding operator and value onto the stack
  4. The precedence of an operator is maintained by a function that pushes each new operator onto the stack with a weight greater than or equal to it
  5. The calculated values are the top two values of the stack, and the calculated results are pushed onto the stack
  6. When the operator stack is empty, the value stack will be larger than one value, which is what we want

The code is as follows:

Var Calculate = function(s) {// Operators = ['&'], // operators = []; Let num = 0 for(let I = 0; i<s.length; I++) {/ / record values the if (s [I] > = '0' && s [I] < = '9') {num = 10 + num * s [I] * 1} else if (s = = = [I] '+' | | s [I] = = = '-' | | s [I] = = = '*' | | s [I] = = = '/'){// push nums.push(num); num = 0; While (getWeight(operators[operate.length-1])>=getWeight(s[I])){const num2 = nums.pop(), num1 = nums.pop(), operator = operators.pop(); Nums. push(calc(num1,operator,num2))} operators. Push (s[I])} While (nums.length>1){const num2 = nums.pop(), num1 = nums.pop(); Nums. push(calc(num1, operator.pop (),num2))} return nums[0] function getWeight(operator){ switch(operator){ case '*': case '/': return 2; case '+': case '-': return 1; default: return 0; Function calc(num1,operator,num2){if(operator === '+'){return num1+num2; }else if(operator === '-'){ return num1-num2 }else if(operator === '*'){ return num1*num2 }else{ return Math.floor(num1/num2) } } };Copy the code

Here we use the trick of inserting & at the bottom of the stack and setting its weight to 0 to avoid the empty stack

At this point we are done with Leetcode-227 – Basic Calculator II

If you have any questions or suggestions, please leave a comment!