SWEA 1223번 문제: 계산기2 | 포스트

문제 링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV14nnAaAFACFAYD

풀이

후위 표기법으로 계산하는 방법은 스택을 사용하는 것이지만, 중위 표기법에서 후위 표기법으로 변환하는 방법도 스택을 사용하는 것이다.
중위 표기법에서 후위 표기법으로 바꾸는 방법은 다음과 같다.
1. 피연산자의 경우, 바로 출력한다.
2. 연산자의 경우, 자기보다 우선순위가 높거나 같은 것들을 pop하여 출력하고 자기 자신을 스택에 push한다.
  - 우선순위가 높다는 건 *를 +보다 먼저 연산한다는 것과 같은 의미이다.
3. 여는 괄호(()를 만나면 무조건 스택에 push한다.
4. 닫는 괄호())를 만나면 여는 괄호(()를 만날 때까지 스택에서 pop하여 출력한다.
후위 표기법을 계산하는 방법은 다음과 같다.
1. 피연산자를 만나면 스택에 push한다.
2. 연산자를 만나면 스택에서 두 개의 피연산자를 pop해서 연산한 다음, 그 결과를 다시 스택에 push한다.
3. 연산을 모두 마치고 스택에 남아있는 하나의 피연산자가 연산의 수행 결과이다.
이 문제에서는 괄호(())가 나오지 않기 때문에 +와 *의 경우만 판단하면 된다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * SW Expert Academy 1223번 문제: 계산기2
 */
public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int T = 10;
        for (int tc = 1; tc <= T; tc++) {
            Stack<String> stack = new Stack<>();
            List<Character> postfix = new ArrayList<>();
            
            int length = Integer.parseInt(br.readLine());
            String formula = br.readLine();
          
            // 후위 표기법으로 변환
            for (int i = 0; i < length; i++) {
                char curr= formula.charAt(i);
                
                if (curr == '+') {
                    while (!stack.isEmpty()) {
                        postfix.add(stack.pop().charAt(0));
                    }
                    stack.push(String.valueOf(curr));
                } else if (curr == '*') {
                    while (!stack.isEmpty() && stack.peek() == "*") {
                        postfix.add(stack.pop().charAt(0));
                    }
                    stack.push(String.valueOf(curr));
                } else {
                    postfix.add(curr);
                }
            }
            while (!stack.isEmpty()) postfix.add(stack.pop().charAt(0));
          
            // 후위 표기법 계산
            for (char c : postfix) {
                if (c == '+') {
                    stack.push(String.valueOf(Integer.parseInt(stack.pop()) + Integer.parseInt(stack.pop())));
                } else if (c == '*') {
                    stack.push(String.valueOf(Integer.parseInt(stack.pop()) * Integer.parseInt(stack.pop())));
                } else {
                    stack.push(String.valueOf(c));
                }
            }
            
            System.out.println("#" + tc + " " + stack.pop());
        }
        
        br.close();
    }
}

아래 코드도 제출 시 Pass가 뜨지만, 후위 표기법으로 올바르게 변환되지 않는다. +에서의 조건과 *에서의 조건을 반대로 지정했기 때문이다.

소스 코드 (후위 표기법 오답)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * SW Expert Academy 1223번 문제: 계산기2
 */
public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int T = 10;
        for (int tc = 1; tc <= T; tc++) {
            Stack<String> stack = new Stack<>();
            List<Character> postfix = new ArrayList<>();
            
            int length = Integer.parseInt(br.readLine());
            String formula = br.readLine();
          
            // 후위 표기법으로 변환
            for (int i = 0; i < length; i++) {
                char curr= formula.charAt(i);
                
                // 아래처럼 구현하면 결과는 같으나 후위 표기법이 올바르지 않게 나타남
                if (curr == '+') {
                    while (!stack.isEmpty()) {
                        if (stack.peek() == "+") break;
                        postfix.add(stack.pop().charAt(0));
                    }
                    stack.push(String.valueOf(curr));
                } else if (curr == '*') {
                    stack.push(String.valueOf(curr));
                } else {
                    postfix.add(curr);
                }
            }
            while (!stack.isEmpty()) postfix.add(stack.pop().charAt(0));
          
            // 후위 표기법 계산
            for (char c : postfix) {
                if (c == '+') {
                    stack.push(String.valueOf(Integer.parseInt(stack.pop()) + Integer.parseInt(stack.pop())));
                } else if (c == '*') {
                    stack.push(String.valueOf(Integer.parseInt(stack.pop()) * Integer.parseInt(stack.pop())));
                } else {
                    stack.push(String.valueOf(c));
                }
            }
            
            System.out.println("#" + tc + " " + stack.pop());
        }
        
        br.close();
    }
}