[java] 자바 스택을 활용한 후위 표기법 계산 알고리즘 구현하기

05 Dec 2023

java

후위 표기법(Postfix Notation)은 연산자를 피연산자들의 뒤에 위치시키는 방식으로 수식을 표현하는 방법입니다. 이러한 후위 표기법을 활용하여 계산을 수행하는 알고리즘을 자바 스택(Stack)을 활용하여 구현해보겠습니다.

스택(Stack) 구현하기

우선, 후위 표기법 계산을 위해 스택을 구현해야 합니다. 스택은 LIFO(Last-In-First-Out) 방식으로 데이터를 저장하고 접근할 수 있는 자료구조입니다. 자바에서는 java.util.Stack 클래스를 제공하여 스택을 쉽게 구현할 수 있습니다.

import java.util.Stack;

Stack<Integer> stack = new Stack<>();

위의 코드는 java.util.Stack 클래스를 이용하여 정수형 데이터를 저장할 수 있는 스택을 생성하는 예시입니다.

후위 표기법 계산 알고리즘 구현하기

후위 표기법으로 표현된 식을 계산하기 위해서는 스택을 활용하여 연산을 수행해야 합니다. 이를 위해 다음과 같은 알고리즘을 구현할 수 있습니다.

피연산자를 만나면 스택에 저장합니다.
연산자를 만나면 스택에서 피연산자를 2번 팝(pop)하여 해당 연산자로 계산한 결과를 스택에 저장합니다.
수식을 끝까지 반복하면 스택에는 최종 결과가 저장됩니다.

import java.util.Stack;

public class PostfixCalculator {
    public static int calculate(String expression) {
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < expression.length(); i++) {
            char c = expression.charAt(i);

            if (Character.isDigit(c)) {
                stack.push(Character.getNumericValue(c));
            } else {
                int operand2 = stack.pop();
                int operand1 = stack.pop();

                switch (c) {
                    case '+':
                        stack.push(operand1 + operand2);
                        break;
                    case '-':
                        stack.push(operand1 - operand2);
                        break;
                    case '*':
                        stack.push(operand1 * operand2);
                        break;
                    case '/':
                        stack.push(operand1 / operand2);
                        break;
                }
            }
        }

        return stack.pop();
    }

    public static void main(String[] args) {
        String expression = "52+3*";
        int result = calculate(expression);
        System.out.println("계산 결과: " + result);
    }
}

위의 코드는 후위 표기법 계산을 수행하는 PostfixCalculator 클래스의 예시입니다. calculate 메서드는 후위 표기법으로 표현된 식을 계산하고 결과를 반환합니다. main 메서드에서는 후위 표기법 52+3*을 계산한 결과를 출력하는 예시입니다.

결과

위의 코드를 실행하면 “계산 결과: 21”이 출력됩니다. 후위 표기법으로 표현된 식 52+3*은 5 + 2 * 3과 동일하며, 이를 계산한 결과 21이 나옵니다.

결론

자바 스택을 활용하여 후위 표기법 계산 알고리즘을 구현해보았습니다. 후위 표기법은 표현이 간단하고 계산이 용이하므로 수식 계산에 유용하게 활용될 수 있습니다. 위의 예시를 참고하여 다양한 수식을 계산해보세요.