문제

https://www.acmicpc.net/problem/1918
골드 II

코드 (Java)

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

public class Main {

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String ori_equation = br.readLine();
        StringBuilder sb = new StringBuilder();
        int idx = 0;
        Stack<Character> op_stack = new Stack<>();
        while (idx < ori_equation.length()) {
            switch(ori_equation.charAt(idx)) {
                case '(':
                    op_stack.push(ori_equation.charAt(idx));
                    break;
                case ')':
                    while (op_stack.peek() != '(') {
                        sb.append(op_stack.pop());
                    }
                    op_stack.pop();
                    break;
                case '*':
                case '/':
                    if (!op_stack.isEmpty() && (op_stack.peek() == '*' || op_stack.peek() == '/')) {
                        sb.append(op_stack.pop());
                    }
                    op_stack.push(ori_equation.charAt(idx));
                    break;
                case '+':
                case '-':
                    while (!op_stack.isEmpty() && (op_stack.peek() != '(')) sb.append(op_stack.pop());
                    op_stack.push(ori_equation.charAt(idx));
                    break;
                default:
                    sb.append(ori_equation.charAt(idx));
            }
            ++idx;
        }

        while (!op_stack.isEmpty()) {
            sb.append(op_stack.pop());
        }

        System.out.print(sb);

    }

}

풀이

• 문제 설명에서 괄호를 만들고 뒤에 배치하면 된다고 했는데 딱히 이를 위해 괄호를 생성하진 않았다.

• 결국 앞에서부터 진행시 현재 연산자가 앞의 연산자 대비 우선순위가 얼마나 있냐를 따지는게 중요하다.

• 이는 괄호가 없는 경우에는 단순히 곱셈/나눗셈이 덧셈/뺄셈보다 우선순위가 있다만 고려해서 곱셈/나눗셈의 경우 본인 앞의 연산자가 곱셈/나눗셈인지를 확인 (if문), 덧셈/뺄셈의 경우 본인 앞의 여러 연ㅅ나자들이 곱셈/나눗셈인지 혹은 덧셈/뺄셈도 존재하는지를 확인하면 된다. (while문)

• 문제는 괄호 때문에 저 while문이 현 괄호 안의 식에 대해서만 적용되도록 설정해야 해서 괄호에 관한 조건들이 위처럼 추가가 되었다.

• 마지막에 while문으로 남은 연산자들도 다 처리해야한다는 점 유의

• 골드II치곤 쉬운것 같다.