[leetCode/JS] 224. Basic Calculator

문제 설명

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

 

 

입출력 예

Example 1:

Input: s = "1 + 1"
Output: 2

 

Example 2:

Input: s = " 2-1 + 2 "
Output: 3

 

Example 3:

Input: s = "(1+(4+5+2)-3)+(6+8)"
Output: 23

 

Constraints

• 1 <= s.length <= 3 * 105
• s consists of digits, '+', '-', '(', ')', and ' '.
• s represents a valid expression.
• '+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
• '-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
• There will be no two consecutive operators in the input.
• Every number and running calculation will fit in a signed 32-bit integer.

---

내 솔루션

• s = s.replace(/\s+/g, '').replace(/[\())]/g, '').replaceAll('--','+');
• 처음엔 위 코드처럼 괄호도 지우고 중복된 --부호는 +로 바꿔서 처리 하려고 했다.
• 조건에 있던 마이너스 단항 연산자가 들어있는 -(4+2+4) 이런 문제가 나오면서 좌절.
• 열기 괄호가 나오면 지금까지 했던 연산 합과 다음 이어진 부호를 저장한다.
• 닫기 괄호가 나오면 스택에 저장된 값, 수식으로 그동안 계산 되었던 sum에 더하는 작업을 한다.

// 2 + 5 - (4 + 2)
var calculate = function(s) {
  s = s.replace(/\s+/g, '');
  let sum = 0;
  let sign = 1;
  const stack = [];
  for(let i = 0; i < s.length; i++){
    if(s[i] === '+'){
      sign = 1
    } else if (s[i] === '-'){
      sign = -1;
    } else if (s[i] === '('){
      stack.push(sum); // 7
      stack.push(sign); // -1
      // stack : [7, -1]
      sum = 0;
      sign = 1;
    } else if (s[i] === ')'){
      sum = stack.pop() * sum; // -1 * 6
      sum += stack.pop(); // -6 + 7
    } else {
      let num = 0;
      // i를 +1 씩하면서 다음 숫자를 받아와서 숫자를 계산한다.
      while(s[i] >= '0' && s[i] <= '9') {
        num = (num*10) + Number(s[i])
        i++;
      }
      sum = sum + (num * sign)
      i--;
    }
  }
  return sum;
};

감상평

• 하드 다운 문제였다.
• 여러자리의 숫자를 어떻게 가져올지, 괄호들을 어떻게 처리할지 고민이 많이 되었다.
• 다른 솔루션들은 regex를 적극적으로 사용하거나 여러 stack에 나눠서 처리하던데 많이 복잡해서 코드 보자마자 꺼버렸다.