[1224] 계산기3

✔ 계산기3

[SWEA 1224]

문제 분석하기

피연산자일 경우 문자열에 저장, 연산자일 경우 스택이 비었을 경우 스택에 저장

이후 다른 연산자가 들어오기 전에 꺼내어 후위 표기 연산으로 변경

이때 괄호, *, +가 존재하며 괄호, *, + 순으로 우선순위가 높으므로 괄호 )가 존재할 경우 괄호 (부터 넣은 연산자를 모두 나오도록 함 

그리고 만들어진 후위 표기 연산에 대해 피연산자일 경우 스택에 넣고, 연산자일 경우 앞의 두 피연산자를 꺼내 계산

손으로 풀어보기

1. 문자열을 저장
2. 문자열을 후위 표기식으로 변환
   • 피연산자라면 결과 문자열에 저장
   • ( 연산자라면 스택에 저장
   • ) 연산자라면 ( 괄호 전까지의 연산자들을 문자열에 저장
   • * 연산자라면 스택에 저장
   • + 연산자라면 스택에 이미 연산자가 있다면 꺼내서 결과 문자열에 저장 후 연산자를 저장
     이때 (가 존재한다면 (까지만 연산자를 꺼내서 문자열에 저장
3. 후기 표기식으로 변환한 연산을 계산
   • 피연산자라면 스택에 저장
   • 연산자라면 앞의 두 개의 피연산자를 꺼내 계산한 후 다시 스택에 저장
4. 계산 결과 반환

슈도코드 작성하기

T(테스트 케이스 수) = 10
for(T만큼) {
    n(테스트 케이스의 길이)
    s = 문자열 저장
    result(연산 저장 문자열) = 후위표기식 변환 함수(s)
    answer(계산 결과) = 연산 계산 함수(result)
    #T와 answer 반환
}

후위표기식 변환 함수 {
    result(후기표기식 결과)
    stack(연산자 저장 스택)
    for(i -> n만큼) {
        c(i번째 문자)
        if(피연산자라면) {
            result += String.valueOf(c)
        }
        else if ('(' 연산자라면) {
            stack.push(c)
        }
        else if (')' 연산자라면) {
            while(stack일 빌 때까지) {
                if(stack.peek == (라면) {
                    ( 꺼내기
                }
                else {
                    result += String.valueOf(stack.pop())
                }
            }
            stack.pop
        }
        else if ('*' 연산자라면) {
            stack.push(c)
        }
        else if ('+' 연산자라면) {
            if(stack이 비었다면) {
                stack.push(c)
            }
            else {
                while(stack일 빌 때까지) {
                    if(stack.peek == (라면) {
                        멈춤
                    }
                    result += String.valueOf(stack.pop())
                }
                stack.push(c)
            }
        }
    } 
    while(!stack.isEmpty()) {
        result += String.valueOf(stack.pop())
    }
}

계산 함수 {
    result(계산 결과)
    stack(연산 계산 스택)
    for (i -> n만큼) {
        c(i번째 문자)
        if(c가 피연산자라면) {
            stack.push(c - '0')
        }
        else {
            stack.push(피연산자 두 개를 꺼내와 연산)
        }
    }
    result = stack.pop()
}

코드 구현하기

/**
 * 1224) 계산기3
 */
public class D003_1224 {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        // T(테스트 케이스 수) = 10
        int T = 10;
        // T만큼
        for (int test_case = 1; test_case <= T; test_case++) {
            // n(테스트 케이스의 길이)
            int n = sc.nextInt();
            // s = 문자열 저장
            String s = sc.next();
            // result(연산 저장 문자열) = 후위 표기식 변환 함수(s)
            String result = postfix(s);
            // answer(계산 결과) = 연산 계산 함수(result)
            int answer = calculate(result);
            // #T와 answer 반환
            System.out.println("#" + test_case + " " + answer);
        }
    }

    // 후위 표기식 변환 함수
    private static String postfix(String expression) {
        // result(후기표기식 결과)
        String result = "";
        // stack(연산자 저장 스택)
        Stack<String> stack = new Stack<>();
        for (int i = 0; i < expression.length(); i++) {
            // c(i번째 문자)
            char c = expression.charAt(i);
            // 피연산자라면
            if (c - '0' >= 0 && c - '0' <= 9) {
                // 피연산자를 후위표기식 결과에 저장
                result += c;
            }
            // ( 라면
            else if (c == '(') {
                stack.push(String.valueOf(c));
            }
            // ) 라면
            else if (c == ')') {
                // stack일 빌 때까지
                while (!stack.isEmpty()) {
                    // '('일 경우
                    if (stack.peek().equals("(")) {
                        // '(' 꺼내서 버리기
                        stack.pop();
                        // () 사이의 연산자들을 모두 꺼냈으므로 멈춤
                        break;
                    }
                    // 현재 스택에 있는 연산자를 후위표기식 결과에 저장
                    else {
                        result += stack.pop();
                    }
                }
            }
            // * 연산자라면
            else if (c == '*') {
                // 스택에 연산자 저장
                stack.push(String.valueOf(c));
            }
            // + 연산자라면
            else if (c == '+') {
                // stack이 비었다면
                if (stack.isEmpty()) {
                    // 스택에 연산자 저장
                    stack.push(String.valueOf(c));
                }
                // stack이 비어있지 않다면
                else {
                    // stack일 빌 때까지
                    while (!stack.isEmpty()) {
                        // '('가 있을 경우
                        if (stack.peek().equals("(")) {
                            // (와 + 사이의 연산자들을 모두 꺼냈으므로 멈춤
                            break;
                        }
                        // 현재 스택에 있는 연산자를 후위표기식 결과에 저장
                        result += stack.pop();
                    }
                    // 스택에 연산자 저장
                    stack.push(String.valueOf(c));
                }
            }
        }
        // 스택이 비어있지 않다면
        while (!stack.isEmpty()) {
            System.out.print(stack.peek());
            // 남은 연산자를 후위표기식 결과에 저장
            result += stack.pop();
        }
        return result;
    }

    // 계산 함수
    private static int calculate(String expression) {
        // result(계산 결과)
        int result = 0;
        // stack(연산 계산 스택)
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < expression.length(); i++) {
            // c(i번째 문자)
            char c = expression.charAt(i);
            // 피연산자라면
            if (c - '0' >= 0 && c - '0' <= 9) {
                // 피연산자를 스택에 저장
                stack.push(c - '0');
            }
            // 연산자라면
            else {
                // 피연산자 두 개를 스택에서 꺼내와 연산
                int num1 = stack.pop();
                int num2 = stack.pop();
                // 연산한 결과 피연산자를 다시 스택에 저장
                if (c == '+') {
                    stack.push(num1 + num2);
                } else if (c == '*') {
                    stack.push(num1 * num2);
                }
            }
        }
        // 마지막 결과를 스택에서 꺼내 계산 결과로 반환
        result = stack.pop();
        return result;
    }
}