[백준] 1918 후위 표기식 - 자료구조 + 스택 JAVA

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

1918번: 후위 표기식

코드설명

자료구조로 스택을 활용하여 진행합니다.

 

문제애 대한 로직입니다.

1. 'A'~'Z'까지의 값이 들어오면 stringbuilder에 바로 넣어줍니다.
2. 연산자 '+', '-', '*', '/' 가 들어올경우 현재 stack값과의 연산자 우선순위값을 비교하여 만약 현재 ( STACK값의 PEEK() >=  현재 연산자의 우선순위 ) 라면, Stack이 비어있을떄까지 계속해서 sb에 넣어줍니다.
3. '(' 연산자가 들어오면 스택에 넣습니다.
4.  ')' 괄호가 들어왔을때는 '('괄호가 나올때까지 연산자 스택에 담아둔 연산을 모두 꺼내어 출력한 후 '(' 괄호는 출력하지 않고 꺼내줍니다.
5. 마지막에 연산이 종료되었다면 stack에 남아있는 값들을 모두 sb에 넣어줍니다. 이떄 '(' 같은경우 ')' 일때 모두 뺴내었으므로 상관없이 빼내어도 됩니다.

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
import java.util.regex.Pattern;

public class Main {
	public static int V, E, K;
	public static int answer = 0;
	public static String str;
	public static Stack<Character> stack = new Stack<>();
	public static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	
    	str = st.nextToken();
    	
    	for(int i=0;i<str.length();i++) {
    		char nowChar = str.charAt(i);
    		
    		// 'A' ~ 'Z' 일 경우
    		if(nowChar >= 'A' && nowChar <='Z') {
    			sb.append(nowChar);
    		}
            
            //+, -, *, / ( 연산자일경우 )
    		else if(nowChar == '+' || nowChar == '-' || nowChar == '*' || nowChar == '/') {
    			while(!stack.isEmpty() && calculatePriority(stack.peek()) >= calculatePriority(nowChar)) { //만약 
    				sb.append(stack.pop());
    			}
    			stack.add(nowChar);
    		}
            
            // '(' 일경우 그냥 넣습니다.
    		else if(nowChar == '(') {
    			stack.add(nowChar);
    		}
            
            // ')' 일경우 '(' 가 나올때까지 모두 sb에 넣어주고, '('는 그냥 삭제합니다.
    		else if(nowChar == ')') {
    			while(!stack.isEmpty() && stack.peek() != '(') {
    				sb.append(stack.pop());
    			}
    			stack.pop(); //'('는 사용하지 않고 제거
    		}
    		
    	}
        
        //stack에 남아있는 모든 연산자들을 뺴옵니다. 이떄 '(' 는 ')'일경우 모두 빠져나오게 되어있으니 신경쓰지않습니다.
    	while(!stack.isEmpty()) {
    		sb.append(stack.pop());
    	}
    	
    	System.out.println(sb.toString());
    	
    }
    
    public static int calculatePriority(char operand) {
    	if(operand == '*' || operand == '/') return 100; // * 와 / 가 가장 큰 100의 우선순위입니다.
    	else if(operand =='+' || operand == '-') return 10; // + 와 - 가 10의 우선순위입니다.
    	else if(operand == '(' ) return 0; 
    	return 0;
    }
    
}