SWEA 1223 - 계산기2

Java

1223 번 - 계산기2

문제

접근 방법

중위 표기식을 후위 표기식으로 바꾸어 계산하는 법을 연습하는 문제이다.
참고사이트를 통해 알고리즘을 배우고 스스로 코드를 짜 보았다.

구현

후위 표기식을 담을 ArrayDeque, 연산자를 일시적으로 담아 놓을 Stack을 생성한다.

1. 중위 표기식을 앞에서 부터 탐색한다.
2. 숫자가 나오면 바로 후위 표시식에 넣는다.
3. 연산자는 지금 넣으려는 연산자가 stack의 top의 우선 순위보다 높으면(+ < x) 후위 표기식에 담는다. 만일 더 작거나 같으면 (x < + or + == +) stack의 top 우선 순위가 높은것을 만날 때까지 pop하여 후위 표기식에 담는다.

위 이유는, 3+4*4인 경우, 곱하기를 먼저 수행해야 하므로 곱하기 연산자를 먼저 후위 표기식에 담고, 마지막에 + 연산자를 넣는다.

후위 표기식을 ArrayDeque으로 사용하는 이유는 front와 end에 add, pop을 해야하기 때문이다.

이후 바꾼 후위 표기식을 계산한다.
앞에서 부터 탐색하여 연산자를 만나면, 2개의 피연산자를 pop하여 계산하여 계산 결과를 front에 다시 넣는다.

코드

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

class Solution {	
	public static void main(String []args) throws Exception {  
		System.setIn(new FileInputStream("res/input.txt"));	//제출 할 때 주석해야함
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	int result = 0;
    	StringTokenizer stk;
    	int tc = 10;
    	ArrayDeque<Character> st = new ArrayDeque<Character>();			// ArrayDeque을 쓴 이유는
    	Stack<Character> op = new Stack<Character>();
    	Stack<Integer> cal = new Stack<Integer>();
    	for(int idx = 1; idx <= tc; idx++) {
    		int n = stoi(br.readLine());
    		String str = br.readLine();
    		
    		// 중위 표기식을 후위 표기식으로 변환하는 과정
    		for(int i = 0; i < n; i++) {
    			char curC = str.charAt(i);
    			if(0 <= curC - '0' && curC - '0' <= 9) {
    				st.addLast(curC);
    			}
    			else {
    				// 연산자의 우선순위를 비교하여, 입력 하려는 연산자가 저장
    				while(!op.empty() && prec(curC) <= prec(op.peek())) {
    					st.addLast(op.pop());
    				}
    				op.add(curC);
    			}
    		}
    		while(!op.empty()) {
				st.addLast(op.pop());
			}

    		
    		// 변환한 후위 표기식을 계산한다.
    		int size = st.size();    		
    		int n1, n2;
    		for(int i = 0; i < size; i++) {
    			char curC = st.pop();
    			switch(curC) {
    			case '+':
    				n2 = cal.pop();
    				n1 = cal.pop();
    				cal.push(n2 + n1);
    				break;
    			case '*':
    				n2 = cal.pop();
    				n1 = cal.pop();
    				cal.push(n2 * n1);
    				break;
				default:
					cal.add(curC - '0');
					break;
    			}
    		}
    		result = cal.pop();
    		System.out.println("#" + idx + " " + result);
    	}
    	
	}
	
	static int prec(char ch) {
		switch(ch) {
		case '+':
			return 1;
		case '*':
			return 2;
		}
		return 0;
	}
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

난이도

★★★★★

후기

알고리즘을 공부한다고 생각하고 풀이를 학습하였다.

개선할 점

()가 추가된 계산기3도 풀어본다.
계산기3