[JAVA] 백준 1918 - 후위 표기식

 

https://www.acmicpc.net/problem/1918

중위 표기식으로 주어진 식을 후위 표기식으로 바꾸는 문제이다.

괄호나 연산자 우선순위를 결정하는 문제는 주로 스택을 많이 사용하는데, 나한텐 정말 어려웠다.

스택을 어떻게 활용해야하지 한참 고민하다가 결국 GPT에게 아웃라인을 받아서 풀었다,,

알파벳인 경우는 그냥 출력하고, 연산자나 여는 괄호의 경우 스택에 넣는다.

+, - -> 스택이 비어 있으면 스택에 삽입, 스택이 차 있다면 스택이 빌 때까지, 또는 괄호를 만날 때까지 연산자를 꺼낸 후 만난 +, - 를 삽입한다. 지금까지 만난 연산자 중 우선순위가 가장 후순위이기 때문이다.

*,/ -> 스택이 비어 있으면 스택에 삽입 스택이 차 있다면 하나 꺼내서 +나 -일 경우 다시 집어넣고 *,/를 만났을 경우 해당 연산자를 출력한다. 괄호를 만나면 멈춘다.

( -> 스택에 넣는다.

) -> 스택에 넣지않고 (가 나올때까지 들어간 모든 연산자를 출력한다.

 

마지막으로 스택에 남은 모든 연산자를 뒤에 출력한다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Solved1918 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();
        Stack<Character> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c >= 65 && c <= 91) sb.append(c);
            if(c=='('){
                stack.push(c);
            }
            if(c==')'){
                while(!stack.isEmpty()){
                    char temp = stack.pop();
                    if(temp!='('){
                        sb.append(temp);
                    }else break;
                }
            }
            if (c == '+' || c == '-') {
                if (stack.isEmpty()) {
                    stack.push(c);
                }else {
                    while(!stack.isEmpty()){
                        char temp = stack.pop();
                        if (temp == '+' || temp == '-') {
                            sb.append(temp);
                        } else if(temp=='*'||temp=='/') {
                            sb.append(temp);
                        } else {
                            stack.push(temp);
                            break;
                        }
                    } stack.push(c);
                }
            }
            if (c == '*' || c == '/') {
                if (stack.isEmpty()) {
                    stack.push(c);
                } else {
                    while(!stack.isEmpty()){
                        char temp = stack.pop();
                        if (temp == '+' || temp == '-') {
                            stack.push(temp);
                            break;
                        } else if(temp=='*'||temp=='/') {
                            sb.append(temp);
                        }else {
                            stack.push(temp);
                            break;
                        }
                    }
                    stack.push(c);
                }
            }
        }
        while(!stack.isEmpty()){
            sb.append(stack.pop());
        }
        System.out.println(sb);
    }
}

 

스택 너무 어렵다 ㅠㅠ