알고리즘

[BOJ] 1918 후위표기식 - 문자열, 스택

DDANDARA 2020. 11. 2. 20:16

www.acmicpc.net/problem/1918

 

1918번: 후위 표기식

첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식

www.acmicpc.net

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
'''
BOJ - 후위 계산식 - 문자열, Stack
    = 연산자의 우선순위를 나눈 뒤, 일반 항은 바로 Answer에 추가시키고, 괄호나 연산자가 오면 스택에서 우선순위에 따라 처리한다.
'''
import sys
 
 
n = sys.stdin.readline().strip()
 
def prior(opr):
    if opr == '*' or opr == '/':
        return 4
    elif opr == '+' or opr == '-':
        return 2
    else:
        return 0
 
stack = []
 
operator = ['+', '-', '*', '/']
answer = ''
 
for i in range(len(n)):
    if n[i] in operator:
        if stack:
            if prior(stack[-1]) >= prior(n[i]): # 스택의 top이 지금 연산자보다 우선순위가 큰 경우 빼내서 바로 answer에 붙여준다
                answer += stack.pop()
                if stack:
                    if prior(stack[-1]) == prior(n[i]):
                        answer += stack.pop()
                        stack.append(n[i])
                    else:
                        stack.append(n[i])
                else:
                    stack.append(n[i])
            else:
                stack.append(n[i])
        else:
            stack.append(n[i])
 
    elif n[i] == '(': # 여는 괄호는 바로 stack에 넣어준다
        stack.append(n[i])
 
    elif n[i] == ')': # 닫는 괄호를 받으면 스택에서 여는 괄호가 나올때까지 모두 answer에 붙여준다
        while True:
            if stack[-1] == '(':
                stack.pop()
                break
            else:
                answer += stack.pop()
 
    else:
        answer += n[i]
 
 
while stack:
    answer += stack.pop()
 
 
print(answer)
cs