[백준] 알고리즘 분류(자료구조,JAVA)1918번, 후위 표기식

문제 링크

1918번: 후위 표기식

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 중위 표기식 형태의 수식이 주어집니다.

2. 수식을 후위 표기식 형태로 변경한 뒤 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 중위 표기식의 형태를 후위 표기식의 형태로 변경합니다.

 

3. 후위 표기식 형태의 수식을 결과로 출력합니다.

 

 

후위 표기식으로 변경!

 

중위 표기식을 후위 표기식으로 바꿀 때 규칙을 발견하실 수 있습니다.

 

현재 값이 'A' ~ 'Z'의 알파벳일 때

 

그대로 출력!

 

현재 값이 '+', '-', '/', '*' 일 때

 

사칙연산의 우선순위에 따라 진행됩니다.

 

' + '  == ' - ' < ' * ' == ' / '

 

연산자의 값을 Stack을 통해 저장하는데

 

현재 연산자 우선순위가 Stack에 Peek()값보다 작거나 같은 경우 : 우선순위가 작은 연산자가 나올 때까지 Pop()!

 

현재 연산자 우선순위가 Stack에 Peek()값보다 큰 경우 : 그대로 Stack에 Push()!

 

예를 들어

 

*

+

연산자 ' / '가 입력된 경우

 

' / ' == ' * ' 성립!

' * ' Pop()!

+

 

' / ' > ' + ' 성립!그대로 Stack에 Push()!

/

+

 

현재 값이 ' ( ' 일 때

 

괄호임을 시작함을 확인하기 위해 그대로 Stack에 Push()!

 

현재 값이 ' ) ' 일 때

 

Stack에 ' ( '을 만날 때까지 연산자들을 Pop()!

: 괄호가 끝나므로 괄호 안에 있던 연산자들이 먼저 계산되야 하기 때문!

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

A*(B+C)

 

2. 중위 표기식의 형태를 후위 표기식의 형태로 변경합니다.

 

A*(B+C)

 

현재 값이 'A' ~ 'Z'의 알파벳

후기 표기식 : A

 

A*(B+C)

 

현재 값이 '+', '-', '/', '*' 일 때

후기 표기식 : A

 

Stack

*

 

A*(B+C)

 

현재 값이 ' ( ' 일 때

후기 표기식 : AB

 

Stack

(

*

 

A*(B+C)

 

현재 값이 'A' ~ 'Z'의 알파벳

후기 표기식 : AB

 

A*(B+C)

 

현재 값이 '+', '-', '/', '*' 일 때

후기 표기식 : AB

 

Stack

+

(

*

 

A*(B+C)

 

현재 값이 'A' ~ 'Z'의 알파벳

후기 표기식 : ABC

 

A*(B+C)

 

현재 값이 ' ) ' 일 때

후기 표기식 : ABC+

 

Stack

*

 

남은 연산자 출력!

 

후기 표기식 : ABC+*

 

3. 후위 표기식 형태의 수식을 결과로 출력합니다.

 

ABC+* 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• Stack을 이용하여 중위 표기식을 탐색하여 후위 표기식으로 변경을 진행합니다.
• 탐색으로 얻은 후위 표기식의 수식을 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• operatorPriority함수는 연산자의 우선순위를 결정해줍니다.

 

결과코드

 

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

public class Main {
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String str  = br.readLine();
        Stack<Character> operator = new Stack<>();	//연산자 저장 Stack
        StringBuilder sb = new StringBuilder();
        //중위 표기식 수식 탐색!
        for(int i=0;i<str.length();i++){
            char c = str.charAt(i);
            if(c >= 65 && c <= 90)	//알파벳일 때
                sb.append(c);	//그대로 출력!
            else if(c == '('){	//'('일 때 
                operator.push(c);	//Stack에 Push!
            }else if(c == ')'){		//')'일 때
                //'('만날 때까지 Stack Pop!
                while(!operator.isEmpty()){
                    char temp = operator.pop();
                    if(temp == '(')
                        break;
                    else
                        sb.append(temp);
                }
            }else{		// +, -, *, / 일 때
               //첫 연산자일 경우 그대로 Push!
               if(operator.isEmpty()) {
                   operator.push(c);
                   continue;
               }
               //우선순위 확인 Stack값 Push, Pop 진행!
               int c_priority = operatorPriority(c);
               while(!operator.isEmpty()){
                   int priority = operatorPriority(operator.peek());
                   if(priority >= c_priority)	//우선순위가 낮거나 같을 때
                       sb.append(operator.pop());
                   else
                       break;
               }
               operator.push(c);	//현재 연산자 저장!
            }
        }
        while(!operator.isEmpty())	//남은 연산자 존재하면 Pop!
            sb.append(operator.pop());
        bw.write(sb.toString());		//후위 표기식 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //연산자 우선순위 결정해주는 함수
    static int operatorPriority(char c){
        if(c == '+' || c == '-')		// + , - : 1
            return 1;
        else if(c == '*' || c == '/')	// * , / : 2
            return 2;
        else		// ( : 0
            return 0;
    }
}