[백준 JAVA] 1918 후위표기식

1918 후위표기식

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

 

처음으로 골드 문제를 푸는데 성공했다!! 오래 걸렸지만 뭐 어때 ㅎㅎ 파이팅!

문제설명

stack을 사용해서 후위표기식 변환

 

우리 사람은 중위표기식 (A+B) 컴퓨터는 후위표기식 (AB+) 을 사용한다고 한다.

우리가 사칙연산을 할때 A+B*C 를 A+(B*C) 로 계산한다면

후위 표기식은 *와 +의 계산 우선순위를 고려하지 않고

순서대로만 계산하기 때문에기계가 연산하기 적합한것 같음.

 

결과를 똑같이 출력하려면 연산자의 우선순위를 고려하는 추가 작업을 거쳐줘야겠지만 말이다.

접근방식

O(n) 선형 시간복잡도

 

중위 표기식을 한번씩 순회하면서 각 문자의 피연산자, 연산자, 괄호를 처리한다.

각 문자를 스택에 push하거나 pop하고 결과에 넣기 때문에 각 연산은 상수시간에 처리된다.ㅣ

 

따라서, o(n x 1) 이므로 o(n)과 같다.

문제 조건 분석 과정

 

stack의 후입선출을 이용하여

1. 피연산자는 바로 buffer에 담는다

2. case 1. '(' 스택에 담는다

3. case 2. ')' 스택에 담아둔 연산자를 출력한다.

4. 연산자들의 우선순위를 부여하여 계산한다.

 

자료구조

Stack (Stack<Character> st):

• 스택은 연산자를 임시로 저장하고 후위 표기법으로 변환한다.
• 후위 표기법 변환 과정에서, '('와 ')'를 처리하거나 연산자의 우선 순위를 비교하여 적절한 위치에 연산자를 삽입한다.
• 연산자 우선 순위 비교에 따라 스택에서 pop하여 결과 문자열에 추가하거나, 현재 연산자를 스택에 push한다.

틀린이유

잘 틀릴 수 있는 경우에 대해 설명해보겠다.

 

괄호 처리 오류

 (는 push 하고 )는 (가 나올 때까지 스택에서 pop하는 식으로 후입선출 도입해서 생각하기. 그림을 그려보는게 좋음

 

입출력 오류

출력 형식이 맞지 않는 경우... 정수형을 문자열로 잘못 입력하거나, 형변환을 잘못 해주는 경우

은근 자주 실수한다. 아니면 공백 처리

 

예외 상황 처리

stack을 쓸때 pop이나 push가 empty인 경우에 대해 처리를 해야함

올바른 접근 방식 및 해결 방식

후위표기식에 대해 알면 쉽게 풀 수 있는 문제다.

자료구조 때문에 그렇지 체감상 실버 문제가 더 어려웠다...

전체코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] calc = br.readLine().toCharArray(); //입력된 수식
        Stack<Character> st = new Stack<>(); //연산자를 담을 스택
        StringBuilder sb = new StringBuilder(); //후위 표기법으로 변환

        for (int i = 0; i < calc.length; i++) { //후위 표기법으로 변환
            // 피연산자(알파벳)인 경우 바로 결과 문자열에 추가
            if (calc[i] >= 'A' && calc[i] <= 'Z') {
                sb.append(calc[i]);
            } else if (calc[i] == '(') { // '('인 경우 스택에 push
                st.push(calc[i]);
            } else if (calc[i] == ')') { // ')'인 경우 '('가 나올 때까지 스택에서 pop하여 결과 문자열에 추가
                while (!st.isEmpty() && st.peek() != '(') {
                    sb.append(st.pop());
                } if (!st.isEmpty()) st.pop(); // '('를 스택에서 제거
            } else { // 연산자인 경우
                // 스택의 top에 있는 연산자의 우선 순위가 더 크거나 같으면 pop하고 결과 문자열에 추가
                while (!st.isEmpty() && precedence(st.peek()) >= precedence(calc[i])) {
                    sb.append(st.pop());
                }
                st.push(calc[i]); // 현재 연산자를 스택에 push
            }
        }

        while (!st.isEmpty()) { //비어있는 경우의 예외처리, 스택이 빌때까지 반복된다
            sb.append(st.pop()); //sb 문자열에 저장
        }
        System.out.println(sb);
    }

    //연산자 우선순위 부여
    public static int precedence(char st) {
        if (st == '*' || st == '/') return 2; //*또는 /일 경우 우선순위 2
        else if (st == '+' || st == '-') return 1; //+또는 -일 경우 우선순위 1
        else return 0; // 0 반환
    }
}