leetcode hard : Basic Calculator

https://leetcode.com/problems/basic-calculator/description/

Basic Calculator - LeetCode

 

엄밀히 하려면 스택을 이용해서 후위표기식으로 바꾸고

후위표기식을 ㄱㅖ산하면 된다.

그러면 괄호, 곱하기 등 관계 없이 정확한 계산이 가능하다.

근데 코딩인터뷰때 중위->후위 변환을 구현하기는 여간 쉽지 않다.

그래서 이 문제는 곱하기랑 나누기를 고려하지 않아도 풀 수 있게 해줬고

괄호는 recursion으로 해결하면된다.

 

아래는 다른 사람의 모범 솔루션

class Solution:
    def calculate(self, s):    
        def calc(it):
            def update(op, v):
                if op == "+": stack.append(v)
                if op == "-": stack.append(-v)
        
            num, stack, sign = 0, [], "+"
            
            while it < len(s):
                if s[it].isdigit():
                    num = num * 10 + int(s[it])
                elif s[it] in "+-":
                    update(sign, num)
                    num, sign = 0, s[it]
                elif s[it] == "(":
                    num, j = calc(it + 1)
                    it = j - 1
                elif s[it] == ")":
                    update(sign, num)
                    return sum(stack), it + 1
                it += 1
            update(sign, num)
            return sum(stack)

        return calc(0)

이전에 만났던 연산자를 sign에 저장해두고

새 연산자를 만나거나(숫자가 끝나거나) 문자열의 끝을 만나면

숫자에 그 연산자를 붙여서 스택에 넣는다.

예를 들어 xxx - 10 + ... 에서 s[it]가 +를 가리킨다면

스택엔 [xxx]가 있는 상태일거고 sign은 이전 연산자인 +일것이다.

그러면 -에 10을 붙인 -10을 스택에 넣으면 된다. [xxx, -10]

그리고 +는 다시 sign에 넣고 다음숫자를 기다린다.

 

시간복잡도는 O(N)

공간복잡도도 O(N)

 

표기법 변환후 계산하는 방법은 https://www.crocus.co.kr/1703 다른분의 블로그 참고