[Java] 백준 1918번 문제 (후위 표기식)

문제설명

 

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
public class Main {
    public static int priority(char operator)
    {
        if (operator == '+' || operator == '-') return 1;
        if (operator == '*' || operator == '/') return 2;
        return 0;
    }
    public static void main(String[] args) throws Exception
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Stack<Character> stack = new Stack<>();
        String prefix = br.readLine();
        StringBuilder postfix = new StringBuilder();
        for (int i = 0; i < prefix.length(); ++i) 
        {
            char ch = prefix.charAt(i);
            if (ch == '(') stack.push(ch);
            else if (ch == ')') 
            {
                while (!stack.isEmpty() && stack.peek() != '(') postfix.append(stack.pop());
                stack.pop(); // Pop '('
            } 
            else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') 
            {
                while (!stack.isEmpty() && priority(ch) <= priority(stack.peek())) postfix.append(stack.pop());
                stack.push(ch);
            }
            else postfix.append(ch);
        }
        while (!stack.isEmpty()) postfix.append(stack.pop());
        System.out.print(postfix.toString());
    }
}

 

설명

• priority(char operator) 메소드 : 연산자의 우선순위를 반환하는 메소드. '*'와 '/' 연산자의 우선순위가 높고, '+'와 '-' 연산자의 우선순위가 낮다.
• 중위 표현식(prefix)을 받아와 후위 표현식으로 변환.
  이때 스택을 사용하여 연산자들을 임시로 저장한다.
  코드의 실행 흐름은 다음과 같다.
• 문자열을 한 글자씩 읽어가면서 처리한다.

1. '(' 괄호를 만나면 스택에 푸시
2. ')' 괄호를 만나면 '(' 괄호가 나올 때까지 스택에서 연산자를 pop하여 postfix에 추가, 이후  '(' 괄호를 스택에서 제거.
3. 연산자를 만날경우
   3-1. 스택의 맨 위에 있는 연산자보다 현재 연산자보다 우선순위가 낮거나 같은 경우, 우선순위가 높은 연산자를 만날 때까지 스택에서 pop하여 postfix에 추가. 이후 현재 연산자를 스택에 푸시.
   3-2. 스택의 맨 위에 있는 연산자보다 현재 연산자가 우선순위가 높은 경우, 스택에 현재 연산자를 push 
4. 피연산자를 만나면 바로 postfix에 추가.

• 참고로 예제는 다 맞았지만 틀렸다고 나오는 경우, G*(A-B*(C/D+E)/F)를 입력했을 때 GABCD/E+*F/-*가 출력되는지 확인해보는 것이 좋다.

(A+(BXC-D)+E)-(F+G)/H

그림 출처 : https://charles098.tistory.com/10