문제/백준
백준 1918번 후위 표기식 [JAVA]
javaju
2022. 4. 26. 22:49
1918번: 후위 표기식
첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의
www.acmicpc.net
풀이 방법
연산자에 우선순위를 부여하여 HashMap에 저장해 연산자 비교를 쉽게 할 수 있도록 했습니다.
만약 숫자라면 출력하고,
연산자라면 스택에 있는 연산자와 비교하여 우선순위를 이용해 스택에 저장할지 아님 출력할지를 결정했습니다.
또한 ')'인 경우에는 반복문을 돌면서 '('가 나올 때까지 출력했습니다.
그리고 for문이 끝난 뒤에는 stack에 저장된 값이 있다면 stack이 빌 때까지 출력해주었습니다.
코드
|
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
|
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Stack;
public class Main_BJ_1918_후위표기식 {
static HashMap<Character, Integer> hm = new HashMap<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
Stack<Character> stack = new Stack<>();
hm.put('*', 3); hm.put('/', 3);
hm.put('+', 2); hm.put('-', 2);
hm.put('(', 1); hm.put(')', 1);
String line = br.readLine();
for(int i=0;i<line.length();i++) {
char c = line.charAt(i);
if(c=='(') stack.push(c);
else if(c>=65 && c<=90) sb.append(c);
else if(c=='+' || c=='-' || c=='*' || c=='/') {
while(!stack.isEmpty()) {
if(priority(c)<=priority(stack.peek())) {
sb.append(stack.pop());
}else break;
}
stack.push(c);
}else if(c==')') {
while(!stack.isEmpty()) {
char top = stack.pop();
if(top=='(') break;
else sb.append(top);
}
}
}
while(!stack.isEmpty()) sb.append(stack.pop());
System.out.println(sb.toString());
}
public static int priority(char key) {
return hm.get(key);
}
}
|
cs |