227. Basic Calculator II

The title

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

Their thinking

Analog implementation

There are only four operations: ‘+’, ‘-‘, ‘*’, and ‘/’. According to the priority of the four operations, multiplication and division should be calculated first, then addition and subtraction should be calculated

Simulation calculation process;

Suppose you have

s = "3+2*2"
Copy the code

Apply for an empty array list; Store data in a list; const list = [‘3′,’+’,’2′,’*’,2]; First step: enumerate array list, and put the result of the multiplication and division calculation in the array list in place;

List = [‘3′,’+’,’4′]

Step 2: Enumerate the array again, adding and subtracting from the list

List = [4];

Return the result

Edit the code as follows:


var calculate = function (s) {
  const string = s.replace(/^\s+|\s+$/g.' ');
  let len = string.length;
  const list = [];
  let t = ' ';
  for (let i = 0; i < len; i++) {
    const c = string[i];
    if (['+'.The '-'.The '*'.'/'].includes(c)) {
      list.push(t, c);
      t = ' ';
    } else{ t += c; }}if (t) {
    list.push(t);
  }
  //console.log('list', list);

  // compute the multiplication;
  len = list.length;
  if (len === 1) return list[0];
  const array = [];
  for (let i = 0; i < len; i++) {
    const t = array[array.length - 1];
    if (t === The '*') {
      array.pop();
      const after = array.pop();
      const n = after * list[i];
      array.push(n);
    } else if (t === '/') {
      array.pop();
      const after = array.pop();
      const n = Math.floor(after / list[i]);
      array.push(n);
    } else{ array.push(list[i]); }}let result = 0;
  let sign = 1;
  for (let i = 0; i < array.length; i++) {
    const n = array[i];
    if (n === '+') {
      sign = 1;
    }
    if (n === The '-') {
      sign = -1;
    }
    if(! ['+'.The '-'].includes(n)) { result += sign * n; }}return Math.floor(result);
};
Copy the code

The idea is right, but the code is too tedious to write; You need to iterate over and over again; First calculate multiplication and division, then calculate addition and subtraction; Can you optimize the code?

Of course:

The optimized code is as follows:

Optimized multiplication and division, when enumerating strings for the first time, the operation of multiplication and division is carried out at the same time, and the result of multiplication and division is put in the array; Enumerating the array again simply sums over the data to get the answer


var calculate = function(s) {
    s = s.trim();
    const stack = new Array(a);let preSign = '+';
    let num = 0;
    const n = s.length;
    for (let i = 0; i < n; ++i) {
        if (!isNaN(Number(s[i])) && s[i] ! = =' ') {
            num = num * 10 + s[i].charCodeAt() - '0'.charCodeAt();
        }
        if (isNaN(Number(s[i])) || i === n - 1) {
            switch (preSign) {
                case '+':
                    stack.push(num);
                    break;
                case The '-':
                    stack.push(-num);
                    break;
                case The '*':
                    stack.push(stack.pop() * num);
                    break;
                default:
                    stack.push(stack.pop() / num | 0);
            }   
            preSign = s[i];
            num = 0; }}let ans = 0;
    while (stack.length) {
        ans += stack.pop();
    }
    return ans;
};
Copy the code