[BOJ] 1918번: 후위 표기식 (Java)

이정음·2022년 4월 15일
0

알고리즘

목록 보기
2/44

문제


1918번: 후위 표기식


코드(JAVA)

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuffer sb = new StringBuffer();
		Stack<Character> operator = new Stack<>();
		
		String formula = br.readLine();
		
		for(int i = 0 ; i < formula.length() ; i++) {
			char op = formula.charAt(i);
			if('A'<=op && op<='Z') {
				sb.append(op);
			}
			else {
				if(op == '(') {
					operator.push(op);
				}
				else if(op == ')') {
					char c;
					while((c = operator.pop()) != '(') sb.append(c);
				}
				else {
					while(!operator.isEmpty() && Priority(operator.peek())>= Priority(op)) sb.append(operator.pop());
					operator.push(op);
				}
			}
		}
		while(!operator.isEmpty()) sb.append(operator.pop());
		System.out.println(sb.toString());
	}
	
	public static int Priority(char c) {
		if(c == '*' || c=='/') return 2;
		else if(c == '+' || c=='-') return 1;
		else return 0;
	}
}

풀이

피연산자: 바로 출력

연산자: 스택 활용

연산자를 만나면 우선 스택에 넣어주는 것을 기본으로 한다.

이때, stack.peek()이 자신보다 높거나 같은 우선순위의 연산자라면 이를 모두 pop(출력)한 후 자신을 push한다.

이는 자신보다 높은 우선순위의 연산자는 말그대로 먼저 연산을 해줘야 하기 때문에 먼저 출력한다는 개념이다.

괄호 연산자

"(": 스택에 넣는다. 연산자 우선순위에서는 맨 아래 단계에 있게 된다(괄호를 거슬러서 출력하면 안되기 때문!)

")": "("를 만날 때까지, 연산자들을 pop한다.

profile
코드먹는 하마

0개의 댓글