본문 바로가기

1. Programming/BaekJoon

[Baekjoon/Python] 1541번: 잃어버린 괄호(Parshing)

728x90

# Baekjoon 1541번: 잃어버린 괄호
import sys
input = sys.stdin.readline

equation = input().strip()
token = []
num = ""

for i in range(len(equation)): # 파싱 알고리즘 토큰화
    if equation[i] == '-' or equation[i] == '+':
        token.append(equation[i])
    else:
        num += equation[i]
        if i <= len(equation)-2:
            if equation[i+1] == '-' or equation[i+1] == '+':
                token.append(int(num))
                num = ""
        else:
            token.append(int(num))

ans = token[0]
del token[0]
temp_ans = 0
minus_flag = False


for i in range(len(token)):
    
    if token[i] == '-':
        minus_flag = True
    else:
        if type(token[i]) == int:
            if minus_flag == True:
                temp_ans += token[i]
            else:
                ans += token[i]

print(ans-temp_ans)
            
        


파싱(Parshing)은 의미를 알 수 없는 문자열을 분해, 분석하여 의미 있는 형태로 변환한다. 이때 데이터를 분해, 분석하는 프로그램이 파서(parser)이다. 많은 분야에서 사용되며 하향식(Top-Down), 상향식(Bottom-Up) 파싱 기법이 있다.


파싱(Parshing)은 구문 분석이라고 할 수 있다. 하나로 이어진 문자열을 정해진 규칙에 따라 성분들로 분해하고 분해된 성분들을 서로 다른 등급으로 나눠 관계를 분석해 의미 있는 형태로 변환하는 것이다.

이 알고리즘 문제에서는 파스 트리(Parse Tree) 형태까지는 만들 필요가 없었고, 원본 문자열을 토큰화한 것으로 문제에서 요구한 최솟값을 찾을 수 있었다.

token 배열의 원소가 ‘-’일때와 그렇지 않을 때를 구분하고, '-'일 경우에는 minus_flag라는 bool형 data를 True로 바꾸도록 했다. 그 후 원소가 int형일 때 minus_flag가 True인지 False인지에 따라 다른 행동을 하도록 구현했다.
그래서 '-' 이후의 원소들은 temp_ans에 모두 담아냈고, ‘+' 이후의 원소들은 ans에 모두 담아낸 후 마지막에 ans - temp_ans로 답을 구할 수 있었다.

728x90