BOJ - 후위 표기식 1918번 (JAVA)

❓ 문제 - 백준 후위 표기식 1918번 - JAVA 풀이법

 

출처 

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

1918번: 후위 표기식

 

 

 

📝 문제해결법

1. 문제 해석

• 일반적으로 사용하는 중위 표기식을 조건에 맞추어 후위 표기식으로 변환하라
  • A+B 처럼 피연산자+연산자+피연산자에 괄호를 치고 피연산자피연산자(괄호 오른쪽)연산자 구조로 후위 표기식을 변환하면 된다.

2. 이 문제는 스택으로 해결하였습니다.

• 피연산자는 그대로 표시하고, 연산자는 stack에 넣어 우선순위에 맞춰 표시할 수 있도록한다. 
• 우선순위 (, )는 0, +, - 은 1, *, /은 2로 우선순위를 부여한다.
• 4가지 연산자중 스택에 자신보다 우선순위가 크거나 같을 경우의 우선순위가 있을 경우 먼저 계산해야 하므로 stack에서 pop하여 우선순위 표시를 반복한다.
• ( 은 무조건 stack에 넣는다.
• )은 (가 나오기 전까지 모두 pop해서 연산자를 표기하고, 마지막에 (은 표기없이 pop 처리한다.

3. 느낀점

• 테스트 케이스 하나하나 분석해보면서 연산자에 맞춰 구현방식이 달라지는 것을 확인해서 직접 구현해보았는데.. 소스코드도 너무 길어지고 몇 개의 테케가 통과가 안됐다.
• 거의 2시간동안 수정하다가.. 블로그를 참조하니 중위 -> 후위 연산으로 바꿀 때 연산자에 우선순위를 부여하여 처리한다는 방법을 보고 그대로 구현하였더니 통과하였다.
• 스택을 활용하여 푸는 문제는 몇 번 풀어보고 공부하면 대략적인 처리 로직을 배울 수 있을 것 같다.

 

💻 소스코드 

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

import java.util.Stack;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        char[] array = br.readLine().toCharArray();

        Stack<Character> stack = new Stack<>();

        for(int i=0;i<array.length;i++){
            char c = array[i];
            if(c == '+' || c == '-' || c == '*' || c == '/'){
                while (!stack.isEmpty() && priority(stack.peek()) >= priority(c)){
                    sb.append(stack.pop());
                }
                stack.push(c);
            } else if(c == '('){
                stack.push(c);
            } else if(c == ')'){
                while (!stack.isEmpty() && stack.peek() != '('){
                    sb.append(stack.pop());
                }
                stack.pop();
            } else {
                sb.append(c);
            }


        }

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

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

    }

    public static int priority(char c){
        if(c == '(' || c == ')'){
            return 0;
        } else if(c == '+' || c == '-'){
            return 1;
        } else if(c == '/' || c == '*'){
            return 2;
        }
        return -1;
    }
}