13주차. 후위표기식

1935. 후위표기식2

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

1935번: 후위 표기식2

📌문제

- 예제1

  📝입력

A*(B+C)

  💻출력

ABC+*

📌풀이

1. +,- 연산이 기준이 됐을 때, stack에 *,/ 연산이 있다면 이 연산부터 pop해야한다.(우선순위가 있다는 의미)

2. 여는 괄호가 들어오면 닫는 괄호가 나오기 전 연산들을 pop해야한다.

 

이 내용을 토대로 주석처리한대로 처음이 코드를 짜다가 stakc의 top 비교하는 부분의 우선순위가 계속 변함을 알아차리고 우선순위를 부여해주는 함수를 따로 빼서 만들어줌.

 

이 문제를 풀 때 도움이 됐던 반례가 있다.

input: G*(A-B*(C/D+E)/F)

output: GABCD/E+*F/-*

거의 반례를 보며 디버깅하면서 풀어버린 셈..

 

120ms 14156kb

package week13;

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

public class 후위표기식 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        Stack<Character> stack = new Stack<>();
        StringBuilder sb = new StringBuilder();

        for(char c : str.toCharArray()){
            switch (c){
                case '(':
                    stack.push(c);
                    break;
                case ')':
                    while(!stack.isEmpty() && stack.peek() != '(') sb.append(stack.pop());
                    stack.pop();
                    break;
                case '*':
                case '/':
                case '+':
                case '-':
                    /* while(!stack.isEmpty() && (stack.peek() == '*' || stack.peek() == '/')) sb.append(stack.pop());
                    */
                    while (!stack.isEmpty() && getPriority(stack.peek()) >= getPriority(c)) sb.append(stack.pop());
                    stack.push(c);
                    break;
                default:
                    sb.append(c);
            }
        }

        while(!stack.isEmpty()) sb.append(stack.pop());
        System.out.println(sb);
    }

    public static int getPriority(char c){
        switch (c){
            case '*':
            case '/':
                return 2;
            case '+':
            case '-':
                return 1;
            default:
                return 0;
        }
    }
}