김낭만

재밌거나 필요하다고 생각하는 걸 만듭니다.

백준(BOJ) 1918 후위 표기식 파이썬(Python)

문제 링크

연산자 표기법에 관련된 문제이다.
굉장히 기초적인 주제이고, 나도 분명 이전에 전공 수업에서 배운 내용이었지만, 기억이 가물가물해서 새로운 마음으로 풀 수 있었다.

기본적으로 스택을 사용한다는 것은 기억하고 있었기 때문에, 우선 스택을 만들었다.
그 후, 변환 과정에서 괄호를 사용한다는 점에서 연산자의 우선순위를 고려해야 한다는 것을 착안, 우선순위 테이블을 만들었다.
들어오는 연산자의 우선순위를 스택의 마지막 원소와 비교해서 출력하거나 스택에 넣는 과정을 반복하도록 했다.
여는 괄호가 등장하면 스택에 넣고, 닫는 괄호가 등장하면 여는 괄호를 만날 때까지 스택에서 꺼내도록 하였다.
피연산자는 순서대로 그대로 출력하면 된다.
마지막으로, 식이 끝까지 진행된 이후 스택에 남은 연산자를 출력해주었다.

exp = input()

stack = []
# 우선순위, 여는 괄호는 닫는 괄호를 만날 때까지 유지되어야 하므로 가장 마지막 우선순위를 가진다.
prio = {'*': 1, '/': 1, '+': 2, '-':2, '(':3}
for e in exp:
    if e == '(':					# 여는 괄호인 경우
        stack.append(e)
    elif e == ')':					# 닫는 괄호인 경우
        while 1:
            if stack[-1] == '(':
                stack.pop()
                break
            print(stack.pop(), end = '')
    elif e in prio:					# 연산자인 경우
        if not stack:
            stack.append(e)
        else:
            while 1:
                if prio[e] >= prio[stack[-1]]:
                    print(stack.pop(), end= '')
                else:
                    stack.append(e)
                    break
                if not stack:
                    stack.append(e)
                    break
    else:						# 피연산자인 경우
        print(e, end = '')

while stack:						# 스택에 남은 연산자 출력
    print(stack.pop(), end = '')

print('')

2024

맨 위로 이동 ↑

2023

세그먼트 트리

개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...

벨만-포드 알고리즘

개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...

다익스트라 알고리즘

개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...

맨 위로 이동 ↑