224. Basic Calculator

224. Basic Calculator

 

https://youtu.be/zsJ-J08Qgdk?si=dx5-25hz18eqybAv

 

이 문제는 **스택(Stack)**을 사용하여 중위 표기법(expression)을 평가하는 방식으로 풀 수 있습니다. 주어진 수식에서 괄호와 연산자 우선순위를 처리하기 위해 스택이 필요합니다. 아래는 문제를 해결하기 위한 접근 방법과 코드입니다.

---

해결 방법:

1. 스택 사용:
   • 숫자와 현재 연산자를 저장하여 괄호나 이전 연산 결과를 처리.
2. 연산 처리:
   • '+'와 '-' 연산자를 처리하고 숫자를 누적 계산.
3. 괄호 처리:
   • '('가 나타나면 현재 계산 상태를 스택에 저장.
   • ')'가 나타나면 스택에서 이전 상태를 가져와 현재 결과에 합산.
4. 공백 무시:
   • 수식에 포함된 공백은 건너뛰기.

---

알고리즘:

1. sign을 초기화하여 현재 연산을 추적. 기본값은 +.
2. 숫자를 만나면 연산자(sign)에 따라 결과를 누적.
3. '('를 만나면 현재 result와 sign을 스택에 저장.
4. ')'를 만나면 스택에서 이전 상태를 복원하고 현재 결과에 반영.
5. 모든 문자 처리가 끝나면 결과를 반환.

class Solution:
    def calculate(self, s: str) -> int:
        stack = []  # 스택을 사용하여 이전 상태 저장
        result = 0  # 현재 계산 결과
        number = 0  # 현재 처리 중인 숫자
        sign = 1    # 현재 연산자, 1은 '+'를, -1은 '-'를 의미

        for char in s:
            if char.isdigit():  # 숫자일 경우
                number = number * 10 + int(char)  # 숫자 이어 붙이기
            elif char in '+-':  # '+' 또는 '-' 연산자일 경우
                result += sign * number  # 이전 숫자 처리
                number = 0  # 숫자 초기화
                sign = 1 if char == '+' else -1  # 현재 연산자 설정
            elif char == '(':  # '(' 괄호일 경우
                stack.append(result)  # 현재 결과를 스택에 저장
                stack.append(sign)    # 현재 연산자도 스택에 저장
                result = 0  # 새로운 괄호 내부의 결과 초기화
                sign = 1    # 괄호 내부는 '+'부터 시작
            elif char == ')':  # ')' 괄호일 경우
                result += sign * number  # 괄호 내부 계산 완료
                number = 0  # 숫자 초기화
                result *= stack.pop()  # 괄호 이전의 연산자 반영
                result += stack.pop()  # 괄호 이전의 결과 반영

        # 마지막 숫자 처리 (루프 종료 후 남은 숫자)
        result += sign * number
        return result

 

시간 및 공간 복잡도:

1. 시간 복잡도: O(n)
   • 문자열을 한 번 순회하며 모든 문자 처리.
2. 공간 복잡도: O(n)
   • 스택에 괄호와 관련된 상태를 저장.

 

코드  number = number * 10 + int(char)

여러 자리 숫자를 처리하기 위한 코드입니다. 이 코드는 현재 숫자를 왼쪽으로 한 자리 밀어내고 새로 들어온 숫자를 추가하는 방식으로 작동합니다.

 

이유: 여러 자리 숫자 처리

• char.isdigit()은 숫자(0~9)인지 확인합니다.
• 여러 자리 숫자를 처리하기 위해 숫자를 10의 자리씩 확장합니다.

예제:

• 문자열 s = "123"가 있을 때:
  • 처음에는 1을 처리합니다 → number = 0 * 10 + 1 = 1.
  • 다음으로 2를 처리합니다 → number = 1 * 10 + 2 = 12.
  • 마지막으로 3을 처리합니다 → number = 12 * 10 + 3 = 123.

결과적으로, 숫자가 자리수에 따라 확장되며 최종적으로 123이 됩니다.

 

elif char == ')': # ')' 괄호일 경우 result *= stack.pop() # '괄호 이전의 연산자 반영' 이 부분은 왜 있는 거야?

해당 코드 부분은 괄호 내부 계산이 끝난 후, 괄호 이전에 저장된 연산자와 계산 결과를 올바르게 연결하기 위해 필요한 작업입니다.

---

상황 설명:

수식에 괄호가 있을 때, 괄호 안의 연산이 먼저 수행됩니다.
따라서 stack에 괄호 이전의 상태(계산 결과와 연산자)를 저장해 두고, 괄호 내부 계산 결과를 그 상태와 연결해야 합니다.

예제:

수식: 2 - (3 + 4)

1. 괄호 이전 상태:
   • 현재 계산 결과는 2.
   • 연산자는 -.
   • 이 상태를 stack에 저장: stack = [2, -1].
2. 괄호 내부 계산:
   • 내부 계산 결과는 3 + 4 = 7.
3. 괄호 처리:
   • result *= stack.pop()에서:
     • stack.pop()은 이전 연산자 -1을 가져옵니다.
     • 괄호 내부 계산 결과 7에 -1을 곱해, 부호를 반영한 -7이 됩니다.
4. 이전 결과와 연결:
   • result += stack.pop()에서:
     • 이전 계산 결과 2를 가져옵니다.
     • 2 + (-7)로 최종 결과는 -5가 됩니다.

 

마지막 숫자 처리는 왜 있는거야?

 

• 마지막 숫자 처리는 루프가 끝난 뒤 마지막으로 읽은 숫자를 결과에 반영하기 위해 필요합니다. 문자열을 왼쪽에서 오른쪽으로 순회하는 동안, 숫자가 하나씩 읽히지만, 그 숫자는 항상 연산자나 괄호를 만나야 계산에 반영됩니다.
• 문제는 문자열이 끝날 때 마지막 숫자는 연산자를 만나지 않고 끝날 가능성이 있다는 점입니다. 따라서 마지막 숫자는 특별히 처리해야 합니다.

따라서, 

 

결론:

마지막 숫자 처리가 없다면, 마지막 숫자가 계산에서 누락되어 올바른 결과를 얻을 수 없습니다.
루프 종료 후 result += sign * number를 추가하는 것은 필수적인 안전 장치입니다.