JAVA)1918번 후위 표기식 - 스택(Stack)

해당 문제를 해결하기 위해

괄호에 의한 우선 순위 뿐만 아니라

사칙연산의 연산자들 간의 우선 순위도 고려해야 한다.

(괄호) > *, / (곱셈, 나눗셈)  > +, - (덧셈, 뺄셈)

 

# 알고리즘

모든 수식의 입력들 처리할 때까지 반복

1. 입력이 피연산자(알파벳)이면

바로 출력문에 append()

2. 입력이 열린 괄호 "("이면

바로 출력문에 append()

3. 입력이 + 또는 - 이면 

   1) 스택이 비어있다면 바로 push()

   2) 스택이 비어있지 않다면 계속 pop()하고 append()

      a) 스택이 비면 중지

      b) 열린 괄호 "("를 만나면 중지

      a 또는 b 과정 끝나면 입력된 연산자 push

4. 입력이 * 또는 / 이면

   1) 스택이 비어있다면 바로 push()

   2) 스택이 비어있지 않다면 계속 pop()하고 append()

      a) 스택이 비면 중지

      b) 열린 괄호 "("를 만나면 중지

      c) 우선순위 낮은 연산자 + 또는 - 를 만나면 중지

      a 또는 b 또는 c 과정 끝나면 입력된 연산자 push

5. 입력이 닫힌 괄호 ")"이면

스택에서 열린 괄호 "("가 나올 때까지 pop()하고 append()

 

모든 수식의 입력들을 처리한 후에

스택에 남아있는 연산자가 있다면 모두 pop()하고 append()

 

완성된 출력문 출력

 

아래는 문제를 해결하는 코드이다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Stack<String> stack = new Stack<>();
        Scanner sc = new Scanner(System.in);
        String inorder = sc.next();
        String[] each = inorder.split("");
        StringBuilder sb = new StringBuilder();
        for (String x : each) {
            if (x.equals(")")) { // 닫힌 괄호가 들어오면 stack에 열린 괄호가 나올 때까지 pop하고 식에 append 해줌
                while (!stack.peek().equals("(")) {
                    sb.append(stack.pop());
                }
                stack.pop(); // "(" stack에서 제거
            } else if (x.equals("+") || x.equals("-")) {
                // +,-연산자가 들어올 때
                // stack이 비거나 열린 괄호가 나오거나
                // stack에 있는 우선 순위가 같은 +, - 연산자들은 append 해준다. (stack에는 열린 괄호와 연산자만 들어감)
                if (stack.empty()) {
                    // stack이 비어있으면
                    stack.push(x);
                } else {
                    // stack이 비어있지 않으면
                    while (!stack.empty()) {
                        // 열린 괄호를 만나면 pop과 append 중지
                        if (stack.peek().equals("(")) break;
                        // 아니라면 stack이 빌때까지 pop하고 append
                        sb.append(stack.pop());
                    }
                    stack.push(x);
                }
            } else if (x.equals("*") || x.equals("/")) {
                if (stack.empty()) {
                    // stack이 비어있으면
                    stack.push(x);
                } else {
                    // stack이 비어있지 않으면
                    while (!stack.empty()) {
                        // 열린 괄호를 만나면 pop과 append 중지
                        if (stack.peek().equals("(")) break;
                        // *, /보다 우선 순위가 낮은 +, - 연산자를 만나면 pop과 append 중지
                        else if (stack.peek().equals("+") || stack.peek().equals("-")) break;
                        // 아니라면 pop하고 append
                        sb.append(stack.pop());
                    }
                    stack.push(x);
                }
            } else if (x.equals("(")) {
                // 열린 괄호가 들어와도 stack에 넣어준다.
                stack.push(x);
            } else {
                // 피연산자가 들어오면 바로 append
                sb.append(x);
            }
        }
        // 반복문을 다 돌고도 stack에 남아있는 연산자가 있다면
        // -> 열림 괄호 없이 들어온 연산자가 있었을 경우 처리
        while (!stack.empty()) sb.append(stack.pop());

        System.out.print(sb);
    }
}

 

문제 출처 : https://www.acmicpc.net/problem/1918