중위표기식을 후위표기식으로 변환하기 (Java)

표기식(expression)

* 중위표기식

(A+B)-C*D/E 처럼 연산자가 직접 연산하는 피연산자 사이에 위치하는 표기식

* 후위표기식

AB+CD*E/- 처럼 피연산자 뒤에 연산자가 위치하는 표기식

---

배경지식

중위표기식을 후위표기식으로 변환하려면 연산에 대한 '우선순위'를 알아야 한다.

우선순위는 다음과 같다.

1. 소괄호
2. 중괄호
3. 대괄호
4. ^, *, / __제곱, 곱셈, 나눗셈
5. +, - __ 덧셈, 뺄셈

소괄호 안에 있는 식을 계산하고, 다음으로 중괄호 안에 있는 식을 계산하고, 다음으로 대괄호 안에 있는 식을 계산한다.

---

변환 방법

1. 피연산자는 바로 출력한다.
2. 여는 괄호를 만나면 stack에 push 한다.
3. ^, *, / 피연산자를 만나면 stack의 peek가 자신과 같은 우선순위인지 파악하고, 같다면 pop을 한 번 하고, 자신을 push한다.
4. +, - 피연산자를 만나면 stack의 peek가 자신보다 높은 우선순위를 만날 때까지 pop하고, 자신을 push 한다.
5. 닫는 괄호를 만나면 자신과 같은 종류의 여는 괄호를 만날 때까지 pop 한다. 

* 만약 5번에서 다른 종류의 여는 괄호를 먼저 만난다면, 그것은 아마 잘못된 중위표기식일 가능성이 높다.

* 아래 Java 코드는 제곱, 중괄호, 대괄호는 고려하지 않는 코드이다.

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

public class Main {

    public static void main(String[] args){
        
        String exp1 = "A*(B-(C/D))+(E+(F*G))/H";
        String exp2 = "A-(B+C)/D";
        
        System.out.println(convert(exp1)); // ABCD/-*EFG*+H/+
        System.out.println(convert(exp2)); // ABC+D/-
    }

    public static String convert(String exp) {
        String ret = "";
        Stack<Character> operator = new Stack(); //연산자

        for (int i=0; i<exp.length(); i++) {
            char c = exp.charAt(i);
            if (c == '(') {
                operator.push(c);
            } else if ( c == ')') {
                while ((!operator.isEmpty()) && operator.peek() != '(' ) {
                    ret += ""+operator.pop();
                }
                operator.pop(); // 여는 괄호
            } else if (c == '*' || c=='/') {
                // 동일한 우선순위의 연산자를 만나면, 앞에 것을 먼저 연산해야 하므로 pop 해준다.
                if (!operator.isEmpty() && (operator.peek() == '*' || operator.peek() == '/')) {
                    ret += "" + operator.pop();
                }
                operator.push(c);
            } else if (c == '+' || c == '-') {
                // 자신의 우선순위보다 높은 우선순위의 연산자 모두 pop 한다.
                while (!operator.isEmpty() && !(operator.peek() == '(')) {
                    ret += "" + operator.pop();
                }
                operator.push(c);
            } else { //피연산자들
                ret += ""+c;
            }
        }
        while ((!operator.isEmpty())) {
            char c = operator.pop();
            if (c == '(') {continue;}
            ret += ""+c;
        }
        return ret;
    }
}

---

Ps.

직접 구현해서 테스트 해보고 싶다면 백준:후위 표기식 문제에 도전해보는 것을 추천한다.