<Algorithm> 11. Queue&Stack 계산기(후위표기)
by BFine반응형
Queue&Stack 계산기(후위표기)
- 음수입력을 제외한 계산기
- 중위표기식-> 후위표기식으로 변환 (큐에 저장) -> 큐에 들어있는 후위표기식을 하나씩 pull 한 후 연산자를 만날 경우에 연산 후 스택에 저장
- 위를 반복하여 마지막에 스택에 들어있는 결과가 결과값
|
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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
Stack stack=new Stack();
Queue queue=new LinkedList<>();
Queue res=new LinkedList<>();
String cont="";
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
String sig=br.readLine();//중위표현식 입력
for(int i=0;i<sig.length();i++) { // N자리수의 숫자 판단 후 큐에 offer
if(sig.charAt(i)=='*'||sig.charAt(i)=='/'||sig.charAt(i)=='+'||sig.charAt(i)=='-'||
sig.charAt(i)==')'||sig.charAt(i)=='('){
if(!cont.equals("")) {
queue.offer(cont);
queue.offer(sig.charAt(i));
cont="";
continue;
}else {
queue.offer(sig.charAt(i));
continue;
}
}
if(i==sig.length()-1) { // 마지막이면 무조건 offer
cont+=sig.charAt(i);
queue.offer(cont);
break;
}
cont+=sig.charAt(i); // N자리수 만큼 추가
}
System.out.println(queue);
int size_que=queue.size();
for(int i=0;i<size_que;i++){//반복
String str=queue.poll()+"";
switch (str){
case "(": // (가 들어올경우 바로 스택에 push
stack.push(str);
break;
case ")": // )가 들어올경우
while(true){ // 스택에 있는 모든 연산자 출력
if(stack.peek().equals("(")){
stack.pop();
break;}//(경우 반복종료
res.offer(stack.pop());
}
break;
case "*":
case "/":
case "+":
case "-":
while(!stack.isEmpty()&&priority((String)stack.peek())>=priority(str)){
res.offer(stack.pop());
}
stack.push(str);
break;
default:
res.offer(str);
break;
}
}
while(!stack.isEmpty()){
res.offer(stack.pop());
}
System.out.println(res);
double fin=calc(res); //연산결과
if(fin%1==0) { // 정수형 판단
System.out.println((int)fin);
}else {
System.out.println(fin);
}
}
public static int priority(String ch){ //우선순위
int pri=0;
switch (ch) {
case "(":
case ")":
pri=1; // 가장낮은 우선순위 '('은 ')'만날때까지 출력하면 안됨
break;
case "+":
case "-":
pri=2;
break;
case "*":
case "/":
pri=3; //가장 높은 우선순위
break;
default:
pri=0;
break;
}
return pri;
}
public static double calc(Queue queue) {
Stack stack=new Stack();
double num1=0;
double num2=0;
int size_queue=queue.size();
for(int i=0;i<size_queue;i++) {
String str=(String)queue.poll();
switch (str) {// 먼저 들어있는게 num2가 된다
case"*":
num1=Double.parseDouble(stack.pop()+"");
num2=Double.parseDouble(stack.pop()+"");
stack.push(num2*num1);
break;
case"/":
num1=Double.parseDouble(stack.pop()+"");
num2=Double.parseDouble(stack.pop()+"");
stack.push(num2/num1);
break;
case"+":
num1=Double.parseDouble(stack.pop()+"");
num2=Double.parseDouble(stack.pop()+"");
stack.push(num2+num1);
break;
case"-":
num1=Double.parseDouble(stack.pop()+"");
num2=Double.parseDouble(stack.pop()+"");
stack.push(num2-num1);
break;
default:
stack.push(Double.parseDouble(str));
break;
}
}
return Double.parseDouble(stack.pop()+"");
}
}
|
|
cs |
실행
반응형
'공부(2018~2019) - 스킨변경전 > Algorithm' 카테고리의 다른 글
| <Algorithm> 13. 1463번 1로 만들기 (0) | 2018.07.24 |
|---|---|
| <Algorithm> 12. 2747번 피보나치 (0) | 2018.07.24 |
| <Algorithm> 10. 1918번 후위표기식 (0) | 2018.04.20 |
| <Algorithm> 9. 2583번 영역구하기 (0) | 2018.04.15 |
| <Algorithm> 8. 좌표평면을 2차원배열로 표현 (0) | 2018.04.14 |
블로그의 정보
57개월 BackEnd
BFine