[BOJ_1918/JAVA] 후위 표기식

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

1918번: 후위 표기식

문제

풀이

해당 문제는 스택으로 푼다.

 

1. 연산자를 만났을 경우

2. 피연산자를 만났을 경우

3. 괄호를 만났을 경우

로 크게 나눈다.

 

연산자를 만났을 경우 연산자들 간의 우선순위를 정하여 스택에 들어오려는 연산자가 더 클 경우 push하고 peek한 연산자가 더 클 경우 pop을 해준다.

피연산자를 만났을 경우 StringBuilderd에 바로 추가해준다.

괄호를 만났을 경우 '('면 push해주고 ')'면 '('나올때까지 pop을 해준다.

 

코드

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

public class BOJ1918 {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		Stack<Character> stack = new Stack<>();
		
		String input = br.readLine();
		
		for(int i=0;i<input.length();i++) {
			char c = input.charAt(i);
			
			switch(c) {
			case '+' :
			case '-' :
			case '*' :
			case '/' :
				while(!stack.isEmpty() && prior(stack.peek()) >= prior(c)) {
					sb.append(stack.pop());
				}
				stack.push(c);
				break;
			case '(' :
				stack.push(c);
				break;
			case ')' :
				while(!stack.isEmpty() && stack.peek()!='(') {
					sb.append(stack.pop());
				}
				stack.pop();
				break;
			default : 
				// 피연산자일때
				sb.append(c);
			}
		}
		
		while(!stack.isEmpty()) {
			sb.append(stack.pop());
		}
		
		System.out.println(sb);
	
	}
	
	public static int prior(char c) {
		if(c=='(' || c==')') {
			return 0;
		}else if(c=='+'||c=='-') {
			return 1;
		}else if(c=='*'||c=='/'){
			return 2;
		}
		return -1;
	}

}