[자료구조(참고)] [BJ1918] 후위 표기식

코드 플러스

🚩 문제 설명

https://www.acmicpc.net/problem/1918

1918번: 후위 표기식

BJ1918

⏱️ 시간 복잡도
▪ 문자열의 길이를 N이라고 가정한다면 대략적으로 O(N^2)의 시간복잡도가 걸린다.

◾ 중위 표기식을 후위 표기식으로 변환하는 문제

◾ 차량기지 알고리즘 (Shunting-yard Algorithm)

• 중위 표시식을 후위 표기식으로 바꾸는 알고리즘이다.
• 연산자를 저장하는 스택을 기반으로 이루어져 있다.

1. 연산자는 스택에 push 한다.
2. 해당 연산자 우선순위 <= top의 우선순위 라면
- 스택에 있는 연산자 pop 한다.
- 여는 괄호가 나온다면 닫는 괄호가 나올 때 까지 스택에서 pop 한다.
3. 모든 연산자/피연산자 처리가 끝나면, 스택에 있는 연산자를 하나씩 pop 한다.

 

 

 

---

 

 

 

✅ 입출력

1) 중위 표기식이 주어진다.
return ➡️ 주어진 중위 표기식을 후위 표기식으로 변환하여 출력한다.

✔️ 예제 1

A*(B+C)

ABC+*

 

✔️ 예제 2

A+B

AB+

 

✔️ 예제 3

A+B*C

ABC*+

 

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

import sys

exp = list(sys.stdin.readline().strip())
stack = []  # 연산자 담는 스택 배열
ans = ''  # 출력 문자열

for e in exp:
    if 'A' <= e <= 'Z':
        ans += e
    else:
        if e == '(':
            stack.append(e)
        elif e == ')':
            while stack:
                if stack[-1] == '(':
                    stack.pop()
                    break
                ans += stack.pop()
        elif e == '+' or e == '-':
            while stack and stack[-1] != '(':
                ans += stack.pop()
            stack.append(e)
        else:
            while stack and (stack[-1] == '*' or stack[-1] == '/'):
                ans += stack.pop()
            stack.append(e)

while stack:
    ans += stack.pop()

print(ans)

💬 Point

➡️  경우의 수를 나눈다.

◾ 만약 ( 괄호가 나온다면 stack에 넣는다.

◾ 만약 ) 괄호가 나온다면 ( 괄호가 나올때까지 pop() 한다.

◾ +, - 는 제일 우선순위가 작기 떄문에 stack의 top에 어떤 값이 있어도 안의 값을 다 꺼낸다.

◾ *, / 는 우선순위가 높기 때문에 만약 stack에 *와 /가 있으면 꺼내고 그렇지 않으면 스택에 push 한다.

◾ stack에 남아있는 값들을 다 꺼낸다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

# 코드플러스 후위 표기식 파이썬 python

# 백준 1918 후위 표기식 파이썬 python

---