[BOJ] 1918번 - 후위 표기식, 1935번 - 후위 표기식2

1918번: 후위 표기식

1935번: 후위 표기식2

모두 성공

import java.util.*;

public class prob1918 {
    static int precedence(char ch) {
        if (ch == '(') {
        	return 0;
        }
        if (ch == '+' || ch == '-') {
        	return 1;
        }
        return 2;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        StringBuilder ans = new StringBuilder();
        Stack<Character> ops = new Stack<>();
        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch) {
                ans.append(ch);
            } else if (ch == '(') {
                ops.push(ch);
            } else if (ch == ')') {
                while (!ops.isEmpty()) {
                    char op = ops.pop();
                    if (op == '(') break;
                    ans.append(op);
                }
            } else {
                while (!ops.isEmpty() && precedence(ops.peek()) >= precedence(ch)) {
                    ans.append(ops.pop());
                }
                ops.push(ch);
            }
        }
        while (!ops.isEmpty()) {
            ans.append(ops.pop());
        }
        System.out.println(ans);
    }
}

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

public class prob1935 {
    static int N;
    static int[] arr;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws NumberFormatException, IOException {
        N = Integer.parseInt(br.readLine());
        String str = br.readLine();
        arr = new int[N];

        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        System.out.printf("%.2f", calPostfix(str));

    }

    public static double calPostfix(String input) {
        Stack<Double> stack = new Stack<>();
        int len = input.length();

        for (int i = 0; i < len; i++) {
            char op = input.charAt(i);

            if (op >= 'A' && op <= 'Z') {
                stack.push((double) arr[op - 'A']);
            } else {
                double op2 = stack.pop();
                double op1 = stack.pop();
                switch (op) {
                    case '+':
                        stack.push(op1 + op2);
                        break;
                    case '-':
                        stack.push(op1 - op2);
                        break;
                    case '*':
                        stack.push(op1 * op2);
                        break;
                    case '/':
                        stack.push(op1 / op2);
                        break;
                }
            }
        }
        return stack.pop();
    }
}

---

문제 후기

스택의 자료구조를 어떻게 활용해야 하는지 잘 알면 쉬운 문제이지만 그걸 모르면 어려운 문제이다. 그러나 어떻게 스택을 활용해야 하는지 알게 되면 아주 스택스택한 문제들이다. 이번에는 모든 코드를 혼자의 힘으로 작성하지 못했다. 허나 좋은 예제 하나를 공부했다고 생각한다. 앞으로 스택을 다룰 때 아주 많은 도움을 준 문제이다.

 

문제풀이

1918번은 중위 표기식을 후위 표기식으로 작성하는 것이다.

식을 작성하는 법을 정리하자면 다음과 같다.

1. 후위 표기법을 저장하는 배열 A와 연산자와 괄호를 담아둘 스택 S가 있다.
2. 중위 표기식을 앞에서부터 하나씩 탐색한다.
3. 피연산자인 경우 A에 무조건 넣어준다.
4. 연산자는 스택에 저장한다.
   • 스택이 비어있다면 연산자를 저장한다.
   • 비어있지 않다면, 이미 저장된 연산자 a와 저장할 연산자 b의 우선순위를 비교한다.
   • a의 우선순위가 더 낮다면, b를 그냥 S에 저장한다.
   • a의 우선순위가 크거나 같다면 , a를 A에 넣어주고, b를 S에 저장한다.
   • 여는 괄호는 우선순위가 가장 낮다고 가정한다. 그리고 S에 저장한다.
   • 만약 닫는 괄호가 나오면 여는 괄호가 나올 때까지 연산자들을 스택에서 pop 해서 A에 넣어준다.
   • 단, 여는 괄호와 닫는 괄호는 A에 옮기지 않는다.

조금 복잡하다면 괄호가 없는 식을 먼저 처리해보고, 괄호가 있는 식을 처리하는 순서로 해결하면 조금 더 쉬울 것이다.

 

1935번은 그렇게 작성된 후위 표기식을 계산하는 문제이다. 후위 표기식을 앞에서부터 읽어서 숫자가 나오면 스택에 넣고 연산자가 나오면 그 값을 계산해서 스택에 넣어준다. 그렇게 스택에 하나의 값만 남을 때까지 해당 연산을 반복해주면 된다.

BOJ Solutions: https://github.com/Isaac-Lee/BOJ-Algorithm