1918번: 후위 표기식
첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식
www.acmicpc.net
입력은 중위 표기식으로 주어지고 후위 표기식으로 출력하는 문제입니다.
우선 A ~ Z까지의 문자는 바로 출력입니다.
'('는 스택에 바로 push하시면 되고
')'가 나오면 스택에 '('가 나올때까지 pop한 것을 출력해줍니다.
+, -가 나오면 자신보다 우선순위가 낮은 연산자가 없으므로 괄호를 만날때까지 pop한 것을 출력해줍니다.
*, /가 나오면 자신보다 우선순위가 낮은 +, -가 나오거나 괄호를 만날때까지 pop한 것을 출력해줍니다.
마지막에 남아있는 연산자를 모두 출력합니다.
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuffer sb = new StringBuffer();
static Stack<Character> s = new Stack<>();
static char ch[];
static void func() {
for (char x : ch) {
if ('A' <= x && x <= 'Z')
sb.append(x);
else if (x == '(')
s.push(x);
else if (x == ')') {
while (s.peek() != '(')
sb.append(s.pop());
s.pop();
} else if (x == '+' || x == '-') {
while (!s.isEmpty() && s.peek() != '(')
sb.append(s.pop());
s.push(x);
} else {
while (!s.isEmpty() && (s.peek() == '*' || s.peek() == '/'))
sb.append(s.pop());
s.push(x);
}
}
while (!s.isEmpty())
sb.append(s.pop());
System.out.println(sb.toString());
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
ch = st.nextToken().toCharArray();
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
'algorithm > data-structure' 카테고리의 다른 글
| boj 9372 상근이의 여행 (0) | 2021.02.09 |
|---|---|
| boj 1158 요세푸스 문제 (0) | 2021.02.09 |
| boj 1935 후위 표기식2 (0) | 2021.02.05 |
| boj 2493 탑 (0) | 2021.02.04 |
| boj 6416 트리인가? (0) | 2021.02.04 |