[SWEA] 1223번 계산기2 (Java)

문제

SWEA(SW Expert Academy) 1223번 계산기2 [D4]

풀이

스택을 이용하여 후위표기식을 작성/계산하는 문제

 

후위표기식 변환

만약 숫자일 경우, 바로 출력(여기에는 후위표기식 문자열carr에 저장)하고 

연산자일 경우, 우선순위에 따라 스택에 pop/push.

스택에서 자신보다 낮은 우선순위 연산자가 나올 때까지 계속 pop하여 출력한다.

즉, 자신보다 높거나 같은 우선순위 연산자를 모두 pop

현재 문제에서는 +, *밖에 없으므로 +는 스택에 있는 모든 연산자를 출력하고, *는 peek()값이 *일 때 출력한다.

우선순위에 따른 연산자 출력 후, 자기 자신을 push

 

후위표기식 계산

문자열배열(carr)을 순회하며

숫자일 경우 stack에(이전과 다른 스택 사용) push하고 연산자일 경우, 현재 스택에서 숫자 두개를 pop하여 연산.

연산 후, 결과를 다시 push.

문자열 배열을 순회를 완료하면, 스택에는 결과값 단 하나만이 저장되어 있으므로 이를 pop하여 결과 출력.

 

코드

package stack;

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

public class Solution_d4_1223_계산기2 {
	static Stack<Character> stack ;
	static Stack<Integer> res ;
	static int n;
	static char[] carr;
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		for(int T = 1 ; T<=10 ; T++) {
			n = Integer.parseInt(br.readLine());
			carr = new char[n];
			stack = new Stack<>();
			res = new Stack<>();
			toPostfix(br.readLine());
			sb.append("#").append(T).append(" ").append(Cal()).append("\n");			
		}
		System.out.println(sb.toString());
	}
    //후위표기식 계산
	private static int Cal() {
		for(int i =0 ; i < n ; i++) {
			if(carr[i] == '+') res.push(res.pop()+res.pop());
			else if(carr[i] == '*') res.push(res.pop()*res.pop());
			else res.push(carr[i]-'0');
		}
		return res.pop();
	}
    //후위표기식으로 변경
	private static void toPostfix(String str) {
		int idx =0;
		for(int i =0 ; i < n ; i++) {
			if(str.charAt(i)=='+' || str.charAt(i)=='*') {
				while(!stack.isEmpty() && canPop(str.charAt(i))) {
					carr[idx++] = stack.pop(); 
				}
				stack.push(str.charAt(i));
			}
			else carr[idx++] = str.charAt(i);
		}
		while(!stack.isEmpty()) carr[idx++] = stack.pop();
	}
    //우선순위 확인
	private static boolean canPop(char c) {	
		if(c == '+') return true;
		if(stack.peek() == '*') return true;
		else return false;
	}
}