[백준] Q1918 후위 표기식 JAVA

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

1918번: 후위 표기식

 

1. 문제의 이해와 유형

 Stack

수식의 표현 방식에는 prefix, infix, postfix 방식이 있다. 연산자 위치에 따라 이를 구분하는데,

우리가 보통 쓰는 a + b 와 같이 operator가 가운데 위치한 방식을 infix라고 하며, 

ab+ 를 postfix, +ab를 prefix라고 부른다.

수식을 트리로 표현하였을 때 preorder, inorder, postorder 방식으로 순회하였을 때 각각 prefix, infix, postifx가 된다.

 

a+b의 트리 형태

문제에서 중위 표기식을 후위표기식으로 바꾸는 방법으로 '주어진 중위 표기식을 연산자의 우선순위에 따라 묶어준 다음, 괄호안의 연산자를 괄호의 오른쪽으로 옮겨준다'고 되어있다.

'연산자의 우선순위에 따라 묶어주고' -> 연산자의 결과값을 활용하여 나온 값을 기록하고 다시, 밖의 괄호를 처리한다 (재귀)라고 생각했다가, 문자열을 읽으면서 필요한 연산자를 스택에 저장해두었다가 꺼내는 방식을 생각했다.

 

2. 문제 접근 방식

'스택'에 저장해 두고 꺼내는 방식이라고 생각한 다음, 걸렸던 것은 우선순위에 관련된 문제였다.

계산 시 우선순위는 *, / > +,- 이고, ()의 경우 새로운 또 하나의 수식이다.

정리하자면, 우선순위가 높을 수록 먼저 계산되어야 한다.

우선순위가 높은 순서대로 계산을 하다가 낮은 순서가 나온다면 거기서 값이 하나 정리되어 나와야한다.

괄호의 경우 또 하나의 수식이자 새로운 값이라고 생각한다. 

스택에 시작하는 지점인 '(' 를 넣어두고 새로운 수식에 대해 같은 방식을 적용한다. 이후에 ')'가 나오면 해당 작은 수식이 끝이 났기 때문에 '('를 만날 때 까지 빼내어내야 '(  ~~ )'의 수식에 대해 하나의 값으로 처리가 된것이다.

정리)

 1. 스택을 사용한다.

 2. 계산순서에 우선순위를 부여한다.

 3-1. 값(문제에서는 A, B...)를 만났을 때는 바로 기록을 한다.

 3-2. 연산자

    3-2-1. stack이 비어있다면 연산자를 삽입한다.

    3-2-2. 비어있지 않다면 연산을 지금 계산해야하는지 여부를 확인하기 위해 stack의 top에 위치한 연산자와 비교한다.

    3-2-3. 3-2-2의 과정을 나보다 먼저 연산되어야 하는 애들이 없을 때 까지 반복한다.

     추가) 즉, +가 들어왔을 때, 이제 더해질거니까 앞에 곱해진거나 나눠진거 또는 먼저 계산해야 될거 있으면 계산해!
         하는 것과 같다.

4. 수식을 다 읽은 후 남아있는 연산자들에 대해 stack에서 꺼내 마무리한다.

 

우선순위

+,- < *,/  우선순위가 자기보다 높은 애들을 다 빼버리기 때문에 '('를 만났을 때 그 밑으로 내려가지 못하도록 더 낮은 값을 부여한다.

 

/*
2022.01.07
문제번호 : Q1918_Review
이름 및 난이도 : 후위 표기식. Gold III
문제이해 
-----------------
우선순위에 따른 . stack 사용.
  + (우선순위가 낮음)
  * + *  >> 우선순위가 높은 걸 먼저 계산해야함.
  낮은 것이 온다면 그 전에 계산해주어야할 것을 미리 계산해주어야한다.
접근 방법 :
제한 조건 : 
*/

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Character> op = new Stack<Character>();
        char[] expression = br.readLine().toCharArray();
        char[] postfix = new char[expression.length];
        int idx = 0;
        for (int i = 0; i < expression.length; i++) {
            if (expression[i] >= 'A' && expression[i] <= 'Z') {
                postfix[idx++] = expression[i];
                continue;
            }
            // () 는 새로운 하나의 식 따로 계산해주어야함.
            if (expression[i] == '(') {
                op.push(expression[i]);
            } else if (expression[i] == ')') {
                // 밀려있는 계산 마무리.
                while (op.peek() != '(') {
                    postfix[idx++] = op.pop();
                }
                op.pop();
            } else {
                if (op.isEmpty()) {
                    op.push(expression[i]);
                } else {
                    int curPriority = getPriority(expression[i]);
                    while (!op.isEmpty()) {
                        int prevPriority = getPriority(op.peek());
                        if (prevPriority >= curPriority) {
                            postfix[idx++] = op.pop();
                        } else {
                            break;
                        }
                    }
                    op.push(expression[i]);
                }
            }
        }
        while (!op.isEmpty()) {
            postfix[idx++] = op.pop();
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < idx; i++) {
            sb.append(postfix[i]);
        }
        System.out.println(sb.toString());
    }

   //우선순위
    public static int getPriority(char a) {
        if (a == '+' || a == '-')
            return 1;
        else if (a == '*' || a == '/')
            return 2;
        else if (a == '(')
            return 0;
        return -1;
    }
}

 

3. 얻은 점

반복적으로 무언가 계산되는데 그 때, 우선순위가 있다면 우선순위를 활용하여 stack을 사용할 수 있겠다.