[Leetcode] 224. Basic Calculator - JS

https://leetcode.com/problems/basic-calculator/description/?envType=study-plan-v2&envId=top-interview-150

 

1. 문제 분석

문제분석
--------------------
- 유효한 표현식을 나타내는 문자열 s가 주어지면 이를 평가하고 평가결과를 반환하라
- eval()과 같이 문자열을 수학 표현식으로 평가하는 내장 함수는 사용할 수 없다.

제한조건
--------------------
- 1 <= s.length <= 3 * 10^5
- s는 숫자, '+', '-', '(', ')', ' '으로 구성된다.
- s는 유효한 표현식이다.
- +'는 단항 연산으로 사용되지 않습니다(예: "+1" 및 "+(2 + 3)"는 유효하지 않음).
- '-'는 단항 연산으로 사용될 수 있습니다(예: "-1" 및 "-(2 + 3)"가 유효함).
- 입력에는 두 개의 연속된 연산자가 없습니다.
- 모든 숫자와 실행 중인 계산은 부호 있는 32비트 정수에 맞습니다.

 

2. 접근 방법

접근방법
--------------------
' '은 제거하여 모두 붙여준다.

num = 0
	- 숫자값 저장
numStack = [] 초기화
    - 현재 또는 이전의 계산값 저장
opStack = [] 초기화
    - 연산자와 numStack 값 저장
sign = 1
	- 연산자 부호 저장 (1이면 +, -1이면 -)
    
1. 숫자 저장

예를 들어, '123' 숫자가 있을 때, 반복문에서 '1', '2', '3' 순서로 순회하기 때문에
num에 정확한 숫자값을 저장하기 위해선 이전 값에 * 10을 해준뒤 더해줘야 자릿수까지 고려할 수 있다.

2. 연산자 고려

연산자 등장 시 이전에 저장된 숫자 값(num)을 연산자 부호(sign)에 맞게 numStack에 추가해준다.
그리고나서 num과 sign을 갱신해준다.

3. '(' 열린 괄호

열린 괄호 등장 시 새로 연산을 시작해야 하므로 numStack을 초기화 해줘야한다.
초기화 해주기 전에 저장된 numStack, sign 값을 opStack에 추가한다.

❗️단, opStack에 추가시 연산 순서 고려하여 numStack, sign 순서를 잘 지키자.

4. ')' 닫힌 괄호

닫힌 괄호 등장 시 이전에 저장된 숫자 값(num)을 연산자 부호(sign)에 맞게 numStack에 추가해준뒤
괄호안의 연산 결과인 numStack의 합을 구한다.

괄호 안의 연산결과와 괄호 등장 전의 숫자값과 연결 시켜야 하므로
opStack에서 sign과 numStack을 순서대로 빼내어준다.

이전 numStack에 괄호 안의 연산 결과를 추가한다.

5. 반복문 종료

반복문 종료 시 이전 숫자값(num)이 추가되지 못한 경우가 있을 수 있으니 numStack에 추가해준다.

결과값은 numStack의 모든 값을 더해주면 된다.

 

 

3. 코드

var calculate = function(s) {
    s = s.replace(/ /g, '');

    let numStack = []; // 계산값 저장
    let opStack = []; // numStack, 연산자 저장
    let num = 0; // 숫자 저장
    let sign = 1; // 연산자 부호 저장 (1이면 양수, -1이면 음수)

    for (let ch of s) {
        // Number.isNaN()은 isNaN()과 달리 매개변수를 숫자로 변환하는 로직 없다. 
        // 즉, NaN가 아니면 언제나 false 반환
        // 때문에 여기선 숫자로 변환하여 판단해야하므로 isNaN()이 적절
        if (!isNaN(ch)) { 
            num = num * 10 + Number(ch);
        } else if (ch === '+' | ch === '-') {
            numStack.push(sign * num);
            num = 0;
            sign = (ch === '+') ? 1 : -1
        } else if (ch === '(') {
            opStack.push(numStack)
            opStack.push(sign);
            numStack = []
            sign = 1
        } else if (ch === ')') {
            numStack.push(sign * num);
            num = 0;

            let sum = numStack.reduce((acc, cur) => acc + cur, 0);
            sign = opStack.pop();
            numStack = opStack.pop();

            numStack.push(sign * sum)
        }
    }
    numStack.push(sign * num)
    return numStack.reduce((acc, cur) => acc + cur, 0)
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(n)

 

곱하기와 나누기 연산을 하지 않은 단순한 +, - 연산과 ()만 포함되었는데도 큰 구조를 제대로 잡지 못하니 예외처리가 늘어나며 코드가 복잡해져서 어디서 부터 손봐야할 지 막막했다.

결국 GPT의 도움을 받아 공부를 했다.

 

stack 자료구조를 2개로 숫자와 괄호 및 연산자를 담당하는 stack으로 구분하는 것까진 알았다.

하지만, 어떤 순서로 조건을 처리하는게 까다로웠던 문제다.

 

한줄한줄 코드의 의미를 파악해가며 공부하니 조금은 이해가 되는 것 같다.

여러번 반복해서 풀어봐야 오래 기억에 남을 것 같다.

 

p.s. isNaN() 과 Number.isNaN() 차이를 배웠다.

isNaN()은 파라미터를 숫자로 변환하는 로직이 내부적으로 포함되어 있지만, Number.isNaN()은 그렇지 않다.

그러므로, Number.isNaN()의 파라미터로 NaN을 전달하지 않는 이상 false만 반환한다.