후위 표기식

문제

알고리즘

1. A~Z까지 피연산자가 나오면 더해준다.
2. 스택이 비어있고 연산자가 나오면 스택에 추가한다.
3. 스택이 비어있지 않다면 스택의 top과 현재 연산자와의 우선순위를 비교한다.
   3.1 만약 현재 연산자 우선순위가 더 크다면 스택에 그냥 넣어준다.
   3.2 만약 현재 연산자 우선순위가 같거나 작다면 top을 pop하여 더해준다.
4. 위 과정을 우선순위가 더 클 때나, ( 가 나올 때 까지 반복한다.
5. 그리고 )을 제외한 현재 연산자를 스택에 추가한다.

코드로 나타내기

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

public class Solution {
	
	static HashMap<String, Integer> dict = new HashMap<>();
	
    public static void main(String[] args) throws IOException {
//        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedReader br = new BufferedReader(new FileReader("./input.txt"));
//        StringTokenizer st = new StringTokenizer(br.readLine());
        
    	// init
    	dict.put("+", 1);
    	dict.put("-", 1);
    	dict.put("*", 2);
    	dict.put("/", 2);
    	dict.put("(", 3);
    	dict.put(")", 3);
    	
    	
        String[] command = br.readLine().split("");
        
        Stack<String> stack = new Stack<>();
        
        String ans = "";
        boolean isOpen = false;
        for (String cmd : command) {
        	int num = (int)cmd.charAt(0);
        	
            // 1. 피연산자는 그대로 넣기
        	if (num >= 65 && num <= 90) {
        		ans += cmd;
        		continue;
        	}
        	
            //2. 스택이 비어있다면 그대로 넣기
        	if (stack.isEmpty()) stack.push(cmd);
        	else {
        		while(!stack.isEmpty()) {
        			String top = stack.peek();
        			
                    // 닫는 괄호 나오면 여는 괄호 나올 때까지 더해주기
        			if (cmd.equals(")")) {
        				while(true) {
        					
        					String top1 = stack.pop();
        					if (top1.equals("(")) break;
        					ans += top1;
        				}
        				break;
        			}
        			// 3. 스택이 비어있지 않다면 우선순위 비교하기
        			if (compare(top, cmd) || top.equals("(")) break;
                    // 4. 현재 연산자의 우선순위가 작거나 같으면
        			ans += stack.pop();

        		}
                //5. 현재 연산자 추가하기
        		if (!cmd.equals(")")) stack.push(cmd);
        		
        	}
        	
        }
        
        while (!stack.isEmpty()) ans += stack.pop();
        System.out.println(ans);
        
    }  
    
    static boolean compare(String top, String cmd) {
    	return dict.get(top) < dict.get(cmd);
    }
}