[코딩 테스트 RUN] SWEA 수업 : 1224.계산기3

 

 

⚠️ 주의!
SWEA에서 낸 코딩 문제에 대한 해답이 들어있습니다.
열람 시 주의해주세요.

 

[SW Expert Academy] 1224. 계산기3

SW Expert Academy

 

기본적인 원리는 계산기1을 참조할 것.

 

[코딩 테스트 RUN] SWEA 수업 : 1222.계산기1

[코딩 테스트 RUN] SWEA 수업 : 1222.계산기1

 

여기는 + * 연산자 외에도 괄호 연산이 추가된다. 이 부분에 대한 해설만 추가한다. 괄호가 들어간다는 것은 기본적으로 괄호 안을 우선적으로 계산하겠다는 의도가 담겨있다. 중위의 괄호는 해체되어 전위나 후위에서는 괄호가 사실상 사용되지 않는다고 볼 수 있다. 따라서 후위 계산식을 만드는 것을 잘하게 된다면 실제 계산은 계산기1과 계산기2와는 크게 차이점이 없다.

 

특히 이렇게 전위/후위로 만든 식의 경우 괄호를 사용하지 않기 때문에, 괄호 계산에 있어서 중위를 그대로 계산하는 거보다는 더 수식을 짜기 쉬워진다.

 

그러면 어떻게 후위로 변환할까? 후위표기법에 대해서 이해하고 있다면 쉽겠지만, 그렇지 않은 사람들을 위해서(계산기1에서도 이해가 안갔다면) 말하자면, 일단 후위가 연산자를 뒤로 돌리는 것을 이해하고, 여기서 괄호가 이 덩어리를 묶는다는 의미라는 걸 이해해야한다. 즉, A+B 라는 식이 있다면, AB+ 가 되는데, 여기에 괄호로 묶어 식을 (A+B)*C 라고 쳤을 경우, 이 AB+ 에다가 *C 를 적용한다. 따라서 AB+C* 라는 형태로 변환된다고 볼 수 있다.

 

그렇다면 이걸 이 문제에서는 어떻게 할까? 나의 경우 일단 Deque를 하나 만든 뒤, 거기에 괄호 안을 넣어두기로 했다. 즉 여는 괄호는  op.push()  로 넣고 이후 연산자들이 들어오면 처리하게 되는데, +가 특별하다는 건 계산기2에서 설명을 했었다.

 

[코딩 테스트 RUN] SWEA 수업 : 1223.계산기2

[코딩 테스트 RUN] SWEA 수업 : 1223.계산기2

 

다만 한 가지 제약이 더 추가되는데, 바로 괄호에 부딪힌다는것. 여는 괄호에 부딪히게 될 때까지 처리를 하고, * 연산은 스택 탑이 *일 때만 꺼내도록 처리를 한다. 왜냐하면 우선순위가 높거나 같은 연산자들을 빼내야하는데, 곱셈은 자신이 가장 높기 때문이다.

 

그렇게해서 연산자들을 처리하고, 괄호를 닫게 되면, 괄호 안에 있는 연산자들을 뽑아내어 후위로 처리해야한다. 이에 따라 여는 괄호를 만날 때까지 연산자들을 빼낸다. 그리고 전부 빼낸 뒤에는 여는 괄호 또한 빼내야하므로, 한번 더 pop()을 실행하면 된다.

 

 

정답

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Deque;

public class Solution {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = 10;

        for (int test_case = 1; test_case <= T; test_case++) {
            int N = Integer.parseInt(br.readLine());
            Deque<Character> op = new ArrayDeque<>();

            StringBuilder num = new StringBuilder();
            for(char c : br.readLine().toCharArray()){
                if(Character.isDigit(c)){
                    num.append(c);
                } else if(c == '('){
                    op.push(c);
                } else if(c == ')'){
                    while (!op.isEmpty() && op.peek() != '(') {
                        num.append(op.pop());
                    }
                    op.pop();
                }  else if(c == '*') {
                    while(!op.isEmpty() && op.peek() == '*') { num.append(op.pop()); }
                    op.push(c);
                } else if(c == '+') {
                    while(!op.isEmpty() && op.peek() != '(') { num.append(op.pop()); }
                    op.push(c);
                }
            }

            while(!op.isEmpty()) { num.append(op.pop()); }

            Deque<Integer> stack = new ArrayDeque<>();
            for(char c : num.toString().toCharArray()){
                if(c == '*'){
                    stack.push(stack.pop() * stack.pop());
                }
                else if(c == '+') {
                    stack.push(stack.pop() + stack.pop());
                }
                else {
                    stack.push(c - '0');
                }
            }

            sb.append("#").append(test_case).append(" ").append(stack.pop()).append("\n");

        } //테스트 케이스 종료

        System.out.print(sb.toString());
    }
}