후위 표기식 ( 1918번 )

1918번: 후위 표기식

 

나의 풀이

import sys

def _main(n_string):
    answer, stack = [], []
    for i in n_string:
        if i.isalpha():
            answer.append(i)
        elif (i == '('):
            stack.append(i)
        elif (i == '+') or (i == '-'):
            while stack and (stack[-1] != '('):
                answer.append(stack.pop())
            stack.append(i)
        elif (i == '*') or (i == '/'):
            while stack and (stack[-1] in ('*', '/')):
                answer.append(stack.pop())
            stack.append(i)
        elif (i == ')'):
            while stack and (stack[-1] != '('):
                answer.append(stack.pop())
            stack.pop()

    for idx in range(len(stack)-1, -1, -1):
        answer.append(stack[idx])
        
    return ''.join(answer)

n_string = sys.stdin.readline().rstrip()
print(_main(n_string))

 

시간 복잡도

for i in n_string : 문자열을 순회 ( 선형 시간 복잡도 )
    elif : 조건 만족시 stack을 뺴서 append ( 선형 시간 복잡도 )

해당 알고리즘 시간 복잡도 : 이차형 시간 복잡도 ( O(n ** 2) )