백준 1935번 후위표기식2 :: 마이구미

이번 글은 백준 알고리즘 문제 1935번 "후위표기식2" 를 다뤄본다.

1918번 "후위표기식" 문제는 중위표기식에서 후위표기식으로 변환하는 문제였다. - 관련 링크

이번 문제는 후위표기식을 계산하는 문제로써, 1918번 문제를 푼 후, 풀어보면 좋은 문제가 된다.

중위표기식에서 후위표기식 변환 문제도 사실상 방법만 알면 간단했다.

후위표기식의 계산 또한, 단순하다.

1. 피연산자는 스택에 push 한다.
2. 연산자가 나오면 스택에 있는 수를 2번 pop 한다.
3. pop한 두 수를 연산자에 맞게 계산한 후, 다시 push 한다.
4. 모든 계산이 끝나면, 스택의 top이 최종 계산 값이 된다.

for (int i = 0; i < len; i++) {
    char ch = s[i];

    switch(ch) {
        case '+':
        case '-':
        case '*':
        case '/':
            cal(stack, stack.pop(), stack.pop(), ch);
            break;
        default: 
            stack.push(array[ch - 'A']);
            break;
    }
}

위 흐름대로 코드를 구현하면, 끝이다.

컴퓨터 또한, 이렇게 단순하게 계산하기 때문에, 후위표기식을 사용한다.

실제 스택의 이용 사례를 보여주고 있는 문제이기 때문에, 좋은 문제라 생각한다.

본인은 스택에 있어서, 1918번과 1935번 후위표기식에 관한 문제를 푸는 것을 지향한다.

Github - https://github.com/hotehrud/acmicpc/blob/master/algorithm/stack/1935.java

private void solve() {
        // http://mygumi.tistory.com/184
        int n = sc.nextInt();
        char[] s = sc.next().toCharArray();
        int len = s.length;
        double[] array = new double[n];
        Stack<Double> stack = new Stack<Double>();
 
        for (int i = 0; i < n; i++) {
            array[i] = sc.nextInt();
        }
 
        for (int i = 0; i < len; i++) {
            char ch = s[i];
            
            switch(ch) {
            case '+':
            case '-':
            case '*':
            case '/':
                cal(stack, stack.pop(), stack.pop(), ch);
                break;
            default: 
                stack.push(array[ch - 'A']);
                break;
            }
        }
        System.out.format("%.2f", stack.peek());
    }
 
    public static void cal(Stack<Double> stack, double a, double b, char op) {
        switch(op) {
        case '+':
            stack.push(b + a);
            break;
        case '-':
            stack.push(b - a);
            break;
        case '*':
            stack.push(b * a);
            break;
        case '/':
            stack.push(b / a);
            break;
        }
    }