(224 - Basic Calculator) 사칙연산 + 괄호 식 parsing

다 풀고 느꼈던 핵심 아이디어만 정리

 

operator, number 각각 스택 만들어서 저장해두고, 계산할때 꺼내는 방식.. 복잡함.

계산 결과 저장해둘 result = 0 만들고, 거기에 계산 결과 처리

 

핵심 1) Operator 만났을 때, 그 전까지의 결과를 처리

ex) "1*2 + 3"

* 만났을 땐 '1'을 처리

+ 만났을 땐 '*2'를 처리

 

★ 곱셈, 나눗셈 precedence 구현을 위해, +- 단위로 식을 끊을 수 있음 (= 스택에 지금까지의 결과 집어넣고 새로 시작)

https://leetcode.com/problems/basic-calculator/discuss/1456850/Python-Basic-Calculator-I-II-III-easy-solution-detailed-explanation

 

 

핵심 2) 숫자 string을 char 단위로 받을 때, 여러 자리 숫자 쉽게 얻는 방법

num에 지금까지 모은 숫자 progress 저장. 새 digit 만날 때마다, 기존 num에 10 곱해서 자릿수 올려주기

if c.isdigit():
    num = (num * 10) + int(c)

 

핵심 3) 괄호 처리

방법 1. 재귀 활용

argument 괄호 시작 이후의 계산식 string (string 넘겨주면 O(N) 추가 소모할 수도 있기에, index를 넘겨주는 방식 선호)

return 괄호 안의 식 계산값, 괄호가 끝나는 위치

 

방법 2. stack 활용

'괄호는 sign을 바꿔주는 역할'로만 해석

 

ex) "-(1+2)"

- 만나서 result에 이전 계산값(없음) 0 더해주고,

sign만 -1로 바꾼 뒤 stack에 넣고, context 초기화하고 괄호 계산

괄호 계산 끝났을 때 - 즉 ')' 만났을 때, stack에 넣어뒀던 괄호 바깥 sign 꺼내서 적용

 

https://leetcode.com/problems/basic-calculator/discuss/62361/Iterative-Java-solution-with-stack