Basic Calculator

Basic Calculator

문제 내용

숫자, 더하기, 빼기, 중괄호 '(' ')' 그리고 ' ' 스페이스로만 구성된 계산식을 계산 하시오

 

풀이 방법

기본적으로 후위연산을 통해서 해당 문제를 푸는게 학교에서 배우는 방법이다.

자세한 내용은 

www.programmersought.com/article/93565454512/

여기를 참고 하면 되는데 간단하게 순서를 설명하자면 아래와 같다.

1. Stack을 2개로 유지한다

2. 1번 Stack은 숫자와 Operand(연산자) 로 이루어진 Stack이다.

3. 2번 Stack은 Operand(연산자)와 '(' 왼쪽 대괄호로 이루어진 Stack이다.

4. 2번 Stack에서 ')' 좌측 대괄호를 만나면 2번 Stack에 있던 Operand를 1번 Stack으로 옮긴다.

5. 2번 Stack에서 '(' 오른쪽 대괄호를 만나면 정지한다.

Post-order를 완료 했다면 

- Operand를 만날때까지 Stack에 값을 넣고

- Operand를 만나면 마지막 2개의 값을 Pop해서 Operand 처리를 해준다

최종적으로 3이 나오는 것을 볼 수 있다.

그런데 이렇게 문제를 풀자니 너무 어렵다.

그래서 문자열을 뒤집어서 처리하는 방식으로 쉽게 처리가 가능하다.

착안은 다음과 같다.

Stack을 쌓아 가는 방향은 왼쪽에서 오른쪽이 되고 Stack의 마지막으로 보이는 ')' 중괄호를 만나고 계산을 시작하면 Stack 특성상 `2+1` 을 먼저 처리 하게 된다. 

이는 -1로 사용되어야 하는 값을 잘못 계산한 것과 같다.

그래서 String을 Reverse 해줌으로써 Stack을 쌓는 방향과 Stack을 읽는 방향을 맞춰 준다.

계산 순서를 보면 중괄호의 끝이 되는 '('를 기준 점으로 

` 3 - 1` 이 계산 되고

`(3-1 결과값) + 2` 가 계산 되고

최종적으로

`((3-1 결과값) + 2 결과값) + 1`

을 하는 것으로 계산방향과 Stack을 쌓는 방향이 동일하게 맞추고 계산이 가능하다.

이것 말고 Operand의 뒷쪽을 보고 계산 하는 방식이 더 짧긴 하지만, 아무래도 이게 더 이해하기 쉬워서 이 방식으로 설명했다.

Stack으로 1회 채우고 Pop 함으로 O(N)이다.

코드는 아래와 같다.

import java.util.Stack;

public class BasicCalculator {

    //evaluate until matching with ')'
    private int evaluateStack(Stack<Object> stack) {
        int result = 0;

        while(stack.size() > 0 && !(stack.peek() instanceof Character && (char)stack.peek() == ')')){
            Object obj = stack.pop();

            if (obj instanceof Character) {
                if ('+' == (char)obj) {
                    result += (Integer)stack.pop();
                } else {
                    result -= (Integer)stack.pop();
                }

            } else {
                result += (Integer)obj;
            }
        }

        return result;
    }

    public int calculate(String s) {

        Stack<Object> stack = new Stack<>();

        int accumulated = 0;
        int numOfDigits = 0;

        //reverse string
        for (int i = s.length() - 1; 0 <= i; i--) {
            char chr = s.charAt(i);

            if (Character.isDigit(chr)) {
                accumulated += Math.pow(10, numOfDigits) * (int)(chr - '0');
                numOfDigits++;
            } else if (chr != ' ') {
                if (0 < numOfDigits) {
                    stack.push(accumulated);
                    accumulated = 0;
                    numOfDigits = 0;
                }

                if (chr == '(') {
                    int result = evaluateStack(stack);
                    stack.pop();
                    stack.push(result);
                } else {
                    stack.push(chr);
                }
            }
        }

        if (0 < numOfDigits) {
            stack.push(accumulated);
        }

        return evaluateStack(stack);
    }


    public static void main(String[] args) {
        BasicCalculator basicCalculator = new BasicCalculator();

        System.out.println(basicCalculator.calculate("(1+(4+5+2)-3)+(6+8)"));
    }
}