[Java] 백준 BOJ / 1918번: 후위표기식

후위표기식

문제

---

문제 설명

중위 표기식으로 되어있는 수식을 후위 표기식으로 바꾸는 문제이다.'

---

구현

스택에 연산자를 넣으면서 풀면 될 것 같아서 그렇게 생각을 하고 방향을 잡고 생각을 하고 있었는데 괄호처리 방법을 잘 모르겠고 연산자의 우선순위를 고려하다 보니 코드가 너무 난잡해져서 어떻게 해야될지 잘 모르겠어서 다른 글들을 참고했다.

연산자의 우선순위는 그냥 함수로 따로 빼서 곱셈과 나눗셈은 높은 우선순위를 부여하고 덧셈과 뺄셈은 낮은 우선순위를 부여하게 함수를 짰다.

public static int priority(char operator) {
	if (operator == '+' || operator == '-') {
		return 1;
    } else if (operator == '*' || operator == '/') {
		return 2;
    }
    return -1;
}

그리고 이제 입력으로 들어오는 문자열에 대해서 확인을 해야한다.

피연산자들은 어차피 먼저 나오고 연산자들이 나중에 붙을거기 때문에 StringBuilder에 바로 넣어줘도 되기 때문에 switch 구문에서 default로 설정해주었다.

그리고 일반 수식 연산자들인 +, -, *, / 에 대해서는 스택에 넣긴 해야한다.

이제 여기서 우선순위를 확인해야 하는데 만약에 스택에 피연산자가 있고 스택에 있는 연산자의 우선순위가 높으면 그 연산자는 먼저 연산을 해주어야 하기 때문에 스택을 돌면서 우선순위가 높은 연산자들을 다 빼주고 나서 현재의 연산자를 스택에 추가해주면 된다.

switch(ch) {
	//기본연산자에 대해서는 다 같은 연산
	case '+':
	case '-':
	case '*':
	case '/':
	//스택이 안 비고 스택에 있는 연산자의 우선순위가 현재 연산자의 우선순위보다 높으면
	while (!stack.isEmpty() && priority(ch) <= priority(stack.peek())) {
		sb.append(stack.pop());
	}
	stack.add(ch);
	break;
}

그리고 괄호를 확인해보자.

일단 열린 괄호가 나오면 스택에 추가해준다. 그리고 안에서의 계산은 독립된 계산이라고 치기 때문에 다른 연산들은 그냥 해주면 된다.

닫힌 괄호가 나온다면 스택에서 ( 가 나올때까지 스택의 연산자들을 다 StringBuilder에 붙여주고 괄호는 후위표기식에 들어가지 않으니 ( 는 마지막에 pop 해주면 된다.

case '(':
	stack.add(ch);
	break;

case ')':
	while (!stack.isEmpty() && stack.peek() != '(') {
	sb.append(stack.pop());
	}
    
	//여는 괄호 없애주기
	stack.pop();
	break;

---

코드

import java.util.*;
import java.io.*;

public class Main_1918 {
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    String str = br.readLine();
    char[] arr = str.toCharArray();
    Stack<Character> stack = new Stack<>();
    StringBuilder sb = new StringBuilder();
    for (char ch : arr) {
      switch(ch) {
        //기본연산자에 대해서는 다 같은 연산
        case '+':
        case '-':
        case '*':
        case '/':
          //스택이 안 비고 스택에 있는 연산자의 우선순위가 현재 연산자의 우선순위보다 높으면
          while (!stack.isEmpty() && priority(ch) <= priority(stack.peek())) {
            sb.append(stack.pop());
          }
          stack.add(ch);
          break;

        case '(':
          stack.add(ch);
          break;

        case ')':
          while (!stack.isEmpty() && stack.peek() != '(') {
            sb.append(stack.pop());
          }
          //여는 괄호 없애주기
          stack.pop();
          break;

        default:
          sb.append(ch);
      }
    }
    //남은거 다 이어주기
    while (!stack.isEmpty()) {
      sb.append(stack.pop());
    }
    System.out.println(sb);
  }

  public static int priority(char operator) {
    if (operator == '+' || operator == '-') {
      return 1;
    } else if (operator == '*' || operator == '/') {
      return 2;
    }
    return -1;
  }
}