[백준 1918번 Java] 후위 표기식 - Stack

문제 난이도

GOLD II (문제 링크)

 

 

풀이

사칙연산에서의 연산 우선순위의 특징과 스택을 활용해서 풀 수 있다.

 

다들 알겠지만 리마인드하고 넘어가자면,

1. 곱셈과 나눗셈은, 덧셈과 뺄셈보다 우선으로 연산된다.

2. 괄호가 존재할 경우, 가장 먼저 처리된다.

3. 우선순위가 같을 경우, 좌결합성의 특성에 따라 왼쪽의 수식을 우선처리한다.

출처: MDN

 

 

 

또한 문제의 예제와, 그림표기된 것을 보고도 방법을 캐치할 수 있는데,

 

 

 

사칙 연산의 우선순위 특징을 리마인드했고, 어떻게 문제를 풀어나가야할지 통해 정리해볼 수 있다.

 

• 연산은 선출력하는 것이 아니라, 이전 연산자가 존재할 경우, 이전 연산과의 우선순위를 판별해서 출력 여부를 결정해야한다.
• 괄호는 우선 연산이 되기때문에, 괄호 시작 부분을 만났을 경우에, 괄호가 끝나는 시점에서 괄호 시작부분까지의 모든 연산을 강제로 출력해주면 된다. 괄호가 중간중간에 있는 경우 앞서 설명한 대로, 연산자의 우선순위를 따르며 괄호 안의 연산을 우선적으로 처리한다.

 

직전 연산자과 비교할 수 있고, 계속해서 연산들을 저장하기 위해 스택을 활용해야한다.

스택을 활용해서 괄호 시작지점 또한 저장해서, 괄호가 언제 끝나는지 쉽게 알 수 있다. 또한 괄호 시작지점이 여러 개일 경우에도 처리가 가능하다.

 

 

문제의 해결방법을 생각했으니, 이제 코드로 나열해보자.

if (isOperator(cur)) {
    while (!stack.isEmpty() && precedence(stack.peek()) >= precedence(cur)) {
        bw.write(stack.pop());
    }
    stack.push(cur);
}


//연산자인지?
private static boolean isOperator(char c) {
    return c == '+' || c == '-' || c == '*' || c == '/';
}

//연산자 우선순위
private static int precedence(char op) {
    switch (op) {
        case '+': case '-':
            return 1;
        case '*': case '/':
            return 2;
    }
    return -1;
}

 

연산자일 경우, 선출력하는 것이 아니라 이전 연산자와의 비교를 거쳐 우선순위를 정해야한다.

 

 

else if (cur == '(') {
    stack.push(cur);
}
else if (cur == ')') {
    while(!stack.isEmpty() && stack.peek() != '(') {
        bw.write(stack.pop());
    }
    stack.pop();
}

 

괄호일경우, 스택을 통해 하나의 괄호가 온전히 처리될 수 있도록 한다. 괄호가 길어져도 연산자일 경우의 처리를 위에서 했기 때문에 신경쓰지 않아도 된다.

 

 

전체 코드

import java.io.*;
import java.util.Stack;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String word = br.readLine();
        int len = word.length();
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        Stack<Character> stack = new Stack<>();


        for (int i = 0; i < len; i ++) {
            char cur = word.charAt(i);

            if (isOperator(cur)) {
                while (!stack.isEmpty() && precedence(stack.peek()) >= precedence(cur)) {
                    bw.write(stack.pop());
                }
                stack.push(cur);
            }
            else if (cur == '(') {
                stack.push(cur);
            }
            else if (cur == ')') {
                while(!stack.isEmpty() && stack.peek() != '(') {
                    bw.write(stack.pop());
                }
                stack.pop();
            }
            else bw.write(cur);

        }

        while(!stack.isEmpty()) {
            bw.write(stack.pop());
        }

        bw.flush();
        bw.close();
    }

    private static boolean isOperator(char c) {
        return c == '+' || c == '-' || c == '*' || c == '/';
    }

    private static int precedence(char op) {
        switch (op) {
            case '+': case '-':
                return 1;
            case '*': case '/':
                return 2;
        }
        return -1;
    }
}

 

 

 

 

 

참조

연산자 우선순위 - JavaScript | MDN