[SWEA] 1224. 계산기3 (Java)

문제

SW Expert Academy

 

풀이

0. 문제 해석

스택을 이용하여 우선순위에 따라 식을 처리해주면 중위 표기식을 후위 표기식으로 변경할 수 있다.

 

입력 값을 크게 연산자와 피연산자로 나눌 수 있는데

이 문제에서는 연산자가 괄호, +, * 밖에 없다.

 

1. 피연산자

• 그대로 출력

 

2. 연산자

• 스택이 비어있으면 자신 추가
• '(' : 스택에 항상 추가
• '*' : 스택에 항상 추가 (나누기가 없으므로)
• '-', '+' : stack의 top이 자신보다 우선순위가 낮을 때 ( '(' ) 까지 pop 하여 출력 후 자신 추가
•  ')' : stack의 top이 '(' 일때 까지 pop하여 출력

 

위 규칙대로 구현하면 된다.

 

후위수식의 계산은 반대로

 

1. 피연산자

• 스택에 항상 추가

2. 연산자

• 스택에서 2개 pop 후 계산 하여 다시 push

로 구현할 수 있다.

 

 

1. 후위표기식 변환

위 규칙대로

후위표기식으로 변환해준다.

 

2. 후위표기식 계산

 

3. 전체 코드

// [SWEA] 1224. 계산기3 (Java)
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;

public class Solution {
	static int l; // 테스트 케이스 길이
	static String str; // 계산식 (중위 표기법)
	static String result; // 변환식 (후위 표기법)
	static Stack<Character> stack; // 변환 위한 스택
	static Stack<Integer> calStack; // 변환식 계산 스택
	static int resultValue; // 계산 결과
	
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	for(int t = 1; t <= 10; t++) {
    		stack = new Stack<>();
    		calStack = new Stack<>();
    		result = "";
    		resultValue = 0;
    		
    		l = Integer.parseInt(br.readLine());
    		str = br.readLine();
    		
    		// 현재 문자 변환
    		for(int i = 0; i < l; i++) {
    			conversion(str.charAt(i)); 
    		}
    		
    		// 스택이 빌 때 까지 변환식에 넣음
    		while(!stack.isEmpty()) {
    			result += stack.pop();
    		}
    		
    		// 후위 표기식 계산
    		for(int i = 0; i < result.length(); i++) {
        		calculate(result.charAt(i));
        	}
    			
    		resultValue = calStack.pop();
    		System.out.println("#" + t + " " + resultValue);
    	}
    }
    
    public static void conversion(char cur) {
    	// '(' => 무조건 stack 에 쌓음
		if(cur == '(') {
			stack.push(cur);
		}
		// ')' => '(' 만날때 까지 stack의 내용 pop 하여 변환식에 넣음, '(' 는 버림
		else if(cur == ')') {
			while(!stack.isEmpty()) {
				if(stack.peek() == '(') {
					stack.pop();
					break;
				}
				else {
					result += stack.pop();
				}
			}
		}
		// '*' => 무조건 stack 에 쌓음 (*보다 우선순위인 연산자가 없음)
		else if(cur == '*') {
			stack.push(cur);
		}
		// '+' => 비어 있다면 stack 에 쌓음, 비어있지 않다면 '(' 만날때 까지 stack pop 하여 변환식에 넣음
		else if(cur == '+') {
			if(stack.isEmpty()) {
				stack.push(cur);
			}
			else{
				while(!stack.isEmpty()) {
					if(stack.peek() == '(') {
						stack.push(cur);
						break;
					}
					else {
						result += stack.pop();
					}
				}
			}
		}
		// 피연산자일 때 => 변환식에 넣음
		else {
			result += cur;
		}	
    }
    
    // 연산자가 아니라면 stack 에 넣음, 연산자면 스택 2개 pop 후 계산 후 다시 push 
    public static void calculate(char cur) {	
    	if(cur == '*') {
    		int tmp = calStack.pop() * calStack.pop();
    		calStack.push(tmp);
    	}
    	else if(cur == '+') {
    		int tmp = calStack.pop() + calStack.pop();
    		calStack.push(tmp);
    	}
    	else {
    		calStack.push(cur - '0');
    	}
    }
}