[java] 스택을 이용한 수식의 중위 표기법 변환하기

05 Dec 2023

java

수식의 중위 표기법을 후위 표기법으로 바꾸기 위해서 스택을 사용할 수 있습니다. 중위 표기법은 연산자가 피연산자 사이에 위치하는 표기법이며, 후위 표기법은 연산자가 피연산자 뒤에 위치하는 표기법입니다.

문제

예를 들어, 다음과 같은 중위 표기법 수식을 고려해보겠습니다.

3 + 4 * 2 / ( 1 - 5 ) ^ 2

이 수식을 후위 표기법으로 변환하면 다음과 같습니다.

3 4 2 * 1 5 - 2 ^ / +

해결 방법

중위 표기법을 후위 표기법으로 바꾸기 위해서 스택을 사용합니다. 알고리즘은 다음과 같습니다.

피연산자는 그대로 결과에 추가합니다.
’(‘를 만나면 스택에 push합니다.
’)’를 만나면 스택의 top에 있는 연산자를 결과에 추가하고 pop합니다. ‘(‘를 만날 때까지 이 과정을 반복합니다.
연산자를 만나면 스택의 top에 있는 연산자와 우선순위를 비교합니다. 스택의 top에 있는 연산자가 현재 연산자보다 우선순위가 높으면 결과에 추가하고 pop합니다. 현재 연산자보다 우선순위가 낮거나 같은 연산자를 만날 때까지 이 과정을 반복합니다.
모든 수식을 확인한 후에 스택에 남아있는 모든 연산자를 결과에 추가합니다.

아래는 위 알고리즘을 Java로 구현한 코드 예시입니다.

import java.util.Stack;

public class InfixToPostfix {
    public static String convertToPostfix(String expression) {
        String postfix = "";
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < expression.length(); i++) {
            char ch = expression.charAt(i);
            if (Character.isLetterOrDigit(ch)) {
                postfix += ch;
            } else if (ch == '(') {
                stack.push(ch);
            } else if (ch == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    postfix += stack.pop();
                }
                stack.pop();
            } else {
                while (!stack.isEmpty() && precedence(ch) <= precedence(stack.peek())) {
                    postfix += stack.pop();
                }
                stack.push(ch);
            }
        }

        while (!stack.isEmpty()) {
            postfix += stack.pop();
        }

        return postfix;
    }

    public static int precedence(char op) {
        switch (op) {
            case '+':
            case '-':
                return 1;
            case '*':
            case '/':
                return 2;
            case '^':
                return 3;
        }
        return -1;
    }

    public static void main(String[] args) {
        String infix = "3 + 4 * 2 / ( 1 - 5 ) ^ 2";
        String postfix = convertToPostfix(infix);
        System.out.println("Infix expression: " + infix);
        System.out.println("Postfix expression: " + postfix);
    }
}

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

Infix expression: 3 + 4 * 2 / ( 1 - 5 ) ^ 2
Postfix expression: 342*15-2^/+

결론

스택을 사용하여 중위 표기법을 후위 표기법으로 변환하는 방법을 살펴보았습니다. 중위 표기법과 후위 표기법을 변환하는 알고리즘은 다양한 응용 분야에서 유용하게 사용될 수 있습니다.