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
'1. Programming > BaekJoon' 카테고리의 다른 글
[Baekjoon/Python] 14940번: 쉬운 최단거리(BFS) (0) | 2024.10.06 |
---|---|
[Baekjoon/Python] 11724번: 연결 요소의 개수(BFS) (0) | 2024.10.05 |
[Baekjoon/Python] 1931번: 회의실 배정(Greedy) (0) | 2024.10.05 |
[Baekjoon/Python] 2178번: 미로 탐색(BFS) (2) | 2024.09.26 |
[Baekjoon/Python] 1697번: 숨바꼭질(BFS) (2) | 2024.09.26 |