17. 1918번 후위표기식

후위표기식에서 구분되어야 할 점은

1. 단순 알파벳의 경우에는 모두 그대로 출력되어야 하며

2. 연산자일 경우에는

• 스택이 비어있을 때
• 스택의 최상단이 '(' 열린 괄호일때
• 스택의 최상단 보다 들어갈 연산자의 우선순위가 높을때

스택에 PUSH 해주고 그외에는 TOP을 POP 하고 값을 PUSH 해준다

 

*우선순위는 MAP을 이용해 각 연산자를 키로 그리고 값으로는 수치를 지정해주어 비교한다.

( 의 값을 0

+,- 의 값을 1  

*,/ 의 값은 2를 주어 비교한다

( 열린괄호까지 우선순위를 주는 이유는 연산자만 주게 될경우 

( 열린괄호가 없을때의 경우에 따로 처리해주어야 하기 때문 한번에 하기위해 ( 또한 0으로 처리했다.

 

3. '(' 열린 괄호 일경우 스택에 담아준다.

4. 이후 ')' 닫힌 괄호가 나올경우 스택의 최상단이 '(' 열린괄호 이거나  스택이 빌때까지 POP해준다.

 

EX) (A+B/C*(D+E))

Char	Stack	value
(	(
A	(	A
+	(+
B	(+	AB
/	(+/
C	(+/	ABC
*	(+*	ABC/
*	(+*(
D	(+*(	ABC/D
+	(+*(+
E	(+*(+	ABC/DE
)	(+*  (+)	ABC/DE+
)	(+*)	ABC/DE+*+

 

이후 모든 문자열을 돌았으면 남은 스택이 빌때까지 모두 POP해서 출력한다

 

코드를 짜보자

 

1. 알파벳의 경우 모두 출력

 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String string = br.readLine();
        StringBuilder sb = new StringBuilder();
        Stack<Character> st = new Stack<>();
        for (int i = 0; i < string.length(); i++) {
            char c = string.charAt(i);
            if('A'<= c && c <='Z'){
                sb.append(c);
            }

2. 연산자들의 우선순위 설정

HashMap<Character, Integer> map=new HashMap<>();
		map.put('(', 0);
		map.put('+', 1);
		map.put('-', 1);
		map.put('*', 2);
		map.put('/', 2);

3. 문자열 탐색중 연산자일경우 거쳐야할 조건문

 

3-1 '(' 여는 괄호 일때

if(c =='('){
    st.push(c);
    continue;
}

 

3-2 ')' 닫는 괄호 일때

if(c==')'){
    while(!st.isEmpty() && st.peek() != '('){
    sb.append(stack.pop());
    }
    if(!st.isEmpty() && st.peek() == '('){
    st.pop();
    }
}

닫는 괄호일때 스택에 여는 괄호를 만날때까지 스택을 pop 해서 sb에 넣는다

ex) (A+B) 색칠된 부분

Char	Stack	Value
(	(
A	(	A
+	(+	A
B	(+	AB
)	(+ )	AB+

단 '(' 여는 괄호는 값에 들어가지않으니 '(' 여는 괄호를 만났을 때에는 sb에 넣지않고 pop만 시켜준다

 

3-3 스택의 최상단이 연산자 일때 ( 기존에 스택에 담긴 연산자가 지금 돌고있는 연산자보다 우선순위가 높을때 )

EX) A*B+C

while(!st.isEmpty() && map.get(st.peek())>=map.get(c)){
    sb.append(st.pop());
}
st.push(c);

스택의 최상단의 값이 지금 돌고있는 문자열의 연산자 값보다 높을 경우 스택에서 뽑아 sb로 보내고

지금의 연산자를 다시 push해준다

ex) (A*B+C) 색칠된 부분을 보면되겠다 

* 값 2 >= + 값 1

따라서 우선순위가높은 *를 뽑아 값으로 넣고 지금돌고 있는 +를 스택에 쌓는다

Char	Stack	Value
(	(
A	(	A
*	(*
B	(*	AB
+	(* +	AB*
C	(+	AB*
)	(+)	AB*+

 

*연산자들의 우선순위 ( 번째가 아니라 값의 크기로 보면된다. )

따라서 2의 값을 가진 *,/ 가 1의 값을 가진 +,- 보다 높은 우선순위를 가짐

Key	Value
+	1
-	1
*	2
/	2

 

*이때 우선순위가 높은 경우에는 

 sb.append(st.pop());

while문 내부의 이 코드를 거치고 나오고 아닌경우에는 아래의

st.push(c);

스택에 c를 push하는 과정으로 간다

 

 

 

4. 모든 문자열을 탐색하고 난 후 스택이 빌때까지 뽑아 sb에 넣는다

while(!st.isEmpty()){
    sb.append(st.pop());
}

 

5. 이후 출력

System.out.println(sb.toString());

코드 전문

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashMap;
import java.util.Stack;

public class training {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String string = br.readLine();
        StringBuilder sb = new StringBuilder();
        Stack<Character> st = new Stack<>();
        int n = string.length();

        HashMap<Character, Integer> map = new HashMap<>();
        map.put('(', 0);
        map.put('+', 1);
        map.put('-', 1);
        map.put('*', 2);
        map.put('/', 2);

        for (int i = 0; i < n; i++) {
            char c = string.charAt(i);
            if ('A' <= c && c <= 'Z') {
                sb.append(c);
                continue;
            }

            if (c == '(') {
                st.push(c);
                continue;
            }

            if (c == ')') {
                while (!st.isEmpty() && st.peek() != '(') {
                    sb.append(st.pop());
                }
                if (!st.isEmpty() && st.peek() == '(') {
                    st.pop();
                }
                continue;
            }

            while (!st.isEmpty() && map.get(st.peek()) >= map.get(c)) {
                sb.append(st.pop());
            }
            st.push(c);
        }
        while (!st.isEmpty()) {
            sb.append(st.pop());
        }
        System.out.println(sb.toString());
    }
}

결과