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

코드 플러스

🚩 문제 설명

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

1935번: 후위 표기식2

BJ1935

⏱️ 시간 복잡도
▪ 알파벳을 숫자로 치환해야하기 때문에
▪ 주어지는 후위표기식에서 알파벳의 수를 M, 주어지는 숫자의 갯수를 N이라고 가정하면
▪ 시간복잡도는 O(MN)을 따른다.

◾ 후위표기식으로 문제가 주어질 때 식을 계산하여 출력하는 문제

◾ 중위 표기식 (Infix Notation)

• 일반적으로 사용하는 표기식
• 연산자를 피연산자들 사이에 두는 방식
• ex) 2+1, 3x4

◾ 후위 표기식 (Posifix Notation, Reverse Polish Notation)

• 연산자를 피연산자의 다음에 두는 방식
• ex) 21+, 34x

◾ 후위 표시식 계산 알고리즘

1. 피연산자는 스택에 넣는다.
2. 연산자를 만나면
- 피연산자 2개를 스택에서 꺼내 계산한다.
- 계산한 결과를 다시 스택에 넣는다.

 

 

 

---

 

 

 

✅ 입출력

1) 피연산자의 개수가 주어진다. (여기서 피연산자는 영대문자이다.)
2) 두번째 줄에 계산해야할 식이 주어진다.
3) 세번째 줄 부터 각 피연산자에 대응하는 값들이 주어진다.
return ➡️ 계산한 값을 소수점 둘째자리 까지 출력한다.

✔️ 예제 1

5
ABC*+DE/-
1
2
3
4
5

6.20

 

✔️ 예제 2

1
AA+A+
1

3.00

 

 

 

---

 

 

 

📑 문제 풀이

with 파이썬 (Python)

import sys

N = int(sys.stdin.readline())
exp = sys.stdin.readline()
stack = []  # 스택 배열

# 알파벳 숫자 치환
nums = {}
for n in range(N):
    for e in exp:
        if ord(e) in range(ord('A'), ord('Z') + 1) and e not in nums:
            nums[e] = int(sys.stdin.readline())

# 후위 표기식 계산
for e in exp:
    if ord(e) in range(ord('A'), ord('Z') + 1):
        stack.append(nums[e])
    else:
        if len(stack) == 1:
            break

        n2 = stack.pop()
        n1 = stack.pop()
        if e == '+':
            stack.append(n1 + n2)
        elif e == '*':
            stack.append(n1 * n2)
        elif e == '-':
            stack.append(n1 - n2)
        else:
            stack.append(n1 / n2)

print(f'{stack[0]:.02f}')

💬 Point

➡️  딕셔너리를 활용하여 알파벳을 숫자로 치환한다.
➡️  ord() 함수

◾ 딕셔너리를 활용하여 nums 딕셔너리에 알파벳을 키로하여 숫자를 입력받는다. 

◾ range(ord('A'), ord('Z') + 1) 을 활용하여 알파벳을 확인할 수 있다.

◾ 만약 피연산자라면 스택에 넣는다.

◾ 만약 연산자라면 스택에서 값을 두개 꺼내서 계산하고 다시 스택에 넣는다.

◾ 마지막에 스택에 남은 값이 계산 결과가 된다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

# 코드 플러스 후위 표기식2

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

# 백준 후위표기식2

# 백준 1935 후위표기식2 파이썬

---