[JAVA/1918번] 후위표기식

문제

입력 및 출력

풀이

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

class Main {
    // 우선순위를 통해, 열린괄호일 경우 0순위 더하기나 빼기일 경우 1순위 그 외의 경우 2순위로 선정
    static int precedence(char ch) {
        if (ch == '(') {
            return 0;
        }
        if (ch == '+' || ch == '-') {
            return 1;
        } else {
            return 2;
        }
    }
    public static void main(String args[]) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 사용자로부터 문장을 입력받아 문자별로 배열에 넣는다.
        char[] charArray = br.readLine().toCharArray();

        // 출력을 위한 StringBuilder
        StringBuilder sb = new StringBuilder();

        // 후입선출의 특징을 갖는 자료구조 스택 선언
        Stack < Character > stack = new Stack < > ();\


        // charArray의 길이만큼 반복문 수행
        for (int i = 0; i < charArray.length; i++) {
            // 배열의 i번째 원소가 A-Z사이일 경우
            if ('A' <= charArray[i] && charArray[i] <= 'Z') {
                // sb에 넣는다.
                sb.append(charArray[i]);
                // 배열의 i번째 원소가 열린 괄호일 경우
            } else if (charArray[i] == '(') {
                // 스택에 넣는다.
                stack.push(charArray[i]);
                // 배열의 i번째 원소가 닫힌 괄호일 경우
            } else if (charArray[i] == ')') {
                // 스택이 비어있지 않고, 스택의 최 상단이 열린 괄호일 경우
                while (!stack.isEmpty()) {
                    if (stack.peek() == '(') {
                        // pop을 수행하고 반복문을 빠져나온다.
                        stack.pop();
                        break;
                    }
                    // 그 외의 경우 sb에 pop을 수행한 값을 넣는다.
                    sb.append(stack.pop());
                }
            }
            // 그 외의 경우
            else {
                // 스택이 비어있지 않고, 스택의 최상단에 있는 값에 대한 우선순위와 배열의 i번째 값의 우선순위를 비교한다.
                while (!stack.isEmpty() && precedence(stack.peek()) >= precedence(charArray[i])) {
                    sb.append(stack.pop());
                }
                // 그 외의 경우 스택에 넣는다.
                stack.push(charArray[i]);
            }
        }

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

        // 결과 값 출력
        System.out.println(sb);
    }
}

결과 및 해결방법

[결과]

[정리]

해결방법

• 처음 문제를 풀땐, 열린 괄호와 닫힌 괄호를 제외하고 +,-,*,/의 우선순위를 정해 문제를 해결하였다.

  하지만, 괄호가 들어가고 난 이후 예상 밖의 경우의 수가 너무 많이 발생했고 문제에 대해 다시한번 생각해 보았다.

  나는 문제를 해결하기 위해 3가지로 우선순위를 설정하였다.

  1. *, /는 1순위이다.
  2. +, -는 2순위이다.
  3. (는 3순위이다.

  위 우선순위를 구현하기 위해 메소드 precedence를 구현하였고 리턴 값으로 숫자를 받아 서로 비교할 수 있도록 설정하였다.

• 배열의 길이만큼 반복문을 수행하고, 배열의 인덱스가 A-Z사이일 경우 sb에 넣어주었다.

  배열의 인덱스가 열린 괄호일 경우 스택에 넣어주었다.

  배열의 인덱스가 닫힌 괄호일 경우 스택이 비어있지 않을 경우 열린괄호가 나올 때 까지 sb에 pop시킨 데이터를 넣어주었다.

  배열의 인덱스가 연산자일 경우 스택이 비어있지 않다면 우선순위 비교를 통해 sb에 넣어주었고 그 외의 경우는 스택에 넣어주었다.