(파이썬)백준 알고리즘 1287번 할 수 있다

백준 알고리즘 저지 1287번 문제 (https://www.acmicpc.net/problem/1287)

 

 

연산자의 우선순위와 스택을 이용한 구현

후위 표현식의 꼴로 바꿔서 계산기를 구현했고 발견된 연산자가 기존 연산자보다 우선순위가 높을 경우 연산?이 발생함.

 

작성당시 참고한 사이트가 있었는데 못찾겠음

 

 

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
·¬
def·rank(op):¬
····if·op·==·'(':¬
········if·flag==0:¬
············return·20¬
········else·:¬
············return·0¬
····elif·op·==·')':return·19¬
····elif·op·in·'*/':return·15¬
····elif·op·in·'+-':return·14¬
¬
def·calc(A,B,op):¬
····if·op=='+':¬
········return·A+B¬
····elif·op=='-':¬
········return·A-B¬
····elif·op=='*':¬
········return·A*B¬
····elif·op=='/':¬
········sA=str(A)¬
········sB=str(B)¬
········if·len(sA)-len(sB)>15:¬
············real=A//B¬
············#asdf=¬
········return·A//B¬
¬
flag=0¬
input=input()#'1+(3-(+2+4))'#1*(2+3)¬
origin=[]¬
stackA=[]¬
stackB=[]¬
text=''¬
op=1¬
try:¬
····for·i·in·input:#토크나이저¬
········if·i·in·'+-*/()':¬
············if·text!='':#이걸로·()의·예외·제어¬
················origin.append(int(text))¬
············origin.append(i)¬
············text=''¬
········else·:¬
············text+=i¬
····if·text!='':¬
········origin.append(int(text))¬
····###############################print(origin)¬
····'''¬
····5*(6*7+8)¬
¬
····5·6·7·*·8·+·*¬
¬
····5·6·7·*·8¬
····*·(·+······)¬
+(1+2+(2+3)¬
····(5*6)+3¬
····5·6·*¬
····(······)¬
····5·6·*·3·+¬
····'''¬
····for·i·in·origin:¬
········#print(i)¬
········if·op>=2·or·op==-1·:·print(10/0)¬
········if·type(i)==type(1):¬
············op-=1¬
············stackA.append(i)¬
········else:¬
¬
············if·i=='(':¬
················if·op==0:print(10/0)¬
················stackB.append(i)¬
················flag+=1¬
············elif·i==')':¬
················if·op==1:print(10/0)¬
················flag-=1¬
················#print(stackB)¬
················while·stackB[len(stackB)-1]!='(':¬
····················stackA.append(stackB.pop())¬
················stackB.pop()¬
············elif·len(stackB)·<=·0:¬
················op+=1¬
················stackB.append(i)¬
············else·:¬
················op+=1¬
················if·rank(stackB[len(stackB)-1])>=rank(i):¬
····················stackA.append(stackB.pop())¬
····················stackB.append(i)¬
················else:¬
····················stackB.append(i)¬
¬
····del(origin)#메모리확보¬
····'''¬
····for·i·in·origin:¬
········#print(i)¬
········if·type(i)==type(1):¬
············stackA.append(i)¬
········else·:¬
············if·len(stackB)<=0·:¬
················stackB.append(i)¬
················#print(i)¬
············else:¬
················if·rank(stackB[len(stackB)-1])>=rank(i):¬
····················stackA.append(stackB.pop())¬
····················stackB.append(i)¬
················else:¬
····················stackB.append(i)¬
····'''¬
····#print(stackA)¬
····#print(stackB)¬
····while·stackB:stackA.append(stackB.pop())¬
····##############################print(stackA)¬
¬
····for·i·in·stackA:#stackB를·결과로·재활용¬
········if·type(i)==type(1):¬
············stackB.append(i)¬
········else:¬
············B=stackB.pop()¬
············A=stackB.pop()¬
············stackB.append(calc(A,B,i))¬
····del(stackA)¬
····#print(9999999999999999999999999999999999999999999999999999999999999999999999999999999999/9)¬
····print(stackB.pop())¬
¬
except:¬
····print('ROCK')¬
¶
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX