[java] 자바 스택을 활용한 수식 계산 알고리즘 구현하기

05 Dec 2023

java

이번 포스트에서는 자바의 스택(Stack)을 활용하여 수식을 계산하는 알고리즘을 구현해보겠습니다.

스택(Stack)이란?

스택(Stack)은 데이터를 일시적으로 저장하는 자료구조로, 말 그대로 데이터를 쌓아 올리는 형태로 작동합니다. 스택은 “Last-In-First-Out(LIFO)”의 원칙에 따라 동작합니다. 즉, 가장 마지막에 삽입된 데이터가 가장 먼저 제거되는 구조입니다.

수식 계산 알고리즘 구현하기

import java.util.Stack;

public class ExpressionCalculator {

    // 사칙연산을 수행하는 메소드
    private static int performOperation(char operator, int operand1, int operand2) {
        switch (operator) {
            case '+':
                return operand1 + operand2;
            case '-':
                return operand1 - operand2;
            case '*':
                return operand1 * operand2;
            case '/':
                return operand1 / operand2;
            default:
                throw new IllegalArgumentException("지원되지 않는 연산자입니다.");
        }
    }

    // 주어진 수식을 계산하는 메소드
    public static int calculateExpression(String expression) {
        Stack<Integer> operands = new Stack<>();
        Stack<Character> operators = new Stack<>();

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

            // 공백 문자는 무시합니다.
            if (ch == ' ') {
                continue;
            }

            // 숫자인 경우 숫자를 추출하여 스택에 저장합니다.
            if (Character.isDigit(ch)) {
                int operand = 0;
                while (i < expression.length() && Character.isDigit(expression.charAt(i))) {
                    operand = operand * 10 + (expression.charAt(i) - '0');
                    i++;
                }
                operands.push(operand);
            }

            // 연산자인 경우 스택에 저장합니다.
            else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
                while (!operators.empty() && hasPrecedence(ch, operators.peek())) {
                    operands.push(performOperation(operators.pop(), operands.pop(), operands.pop()));
                }
                operators.push(ch);
            }
        }

        // 스택에 남아있는 연산자를 모두 처리합니다.
        while (!operators.empty()) {
            operands.push(performOperation(operators.pop(), operands.pop(), operands.pop()));
        }

        // 최종 결과를 반환합니다.
        return operands.pop();
    }

    // 연산자 우선순위를 확인하는 메소드
    private static boolean hasPrecedence(char operator1, char operator2) {
        if (operator2 == '(' || operator2 == ')') {
            return false;
        }
        if ((operator1 == '*' || operator1 == '/') && (operator2 == '+' || operator2 == '-')) {
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        String expression = "3 + (4 * 5) - 6 / 2";
        int result = calculateExpression(expression);
        System.out.println("수식 계산 결과: " + result);
    }
}

위의 코드는 주어진 수식을 계산하기 위한 ExpressionCalculator 클래스를 구현한 예시입니다. 수식 계산을 위해 스택을 활용하여 숫자와 연산자를 저장하고 처리합니다. 수식 계산을 위해 performOperation 메소드를 사용하여 사칙연산을 수행합니다. 수식을 계산하는 calculateExpression 메소드는 스택을 사용하여 수식을 계산하고 최종 결과를 반환합니다.

위의 예시에서는 “3 + (4 × 5) - 6 ÷ 2”라는 수식을 계산합니다. 코드를 실행하면 “10”이라는 결과가 출력됩니다.

결론

위의 예시를 통해 자바의 스택을 활용하여 수식을 계산하는 알고리즘을 구현하는 방법을 알아보았습니다. 스택은 수식 계산 외에도 다양한 알고리즘에서 유용하게 활용될 수 있는 자료구조입니다. 자바를 이용한 알고리즘 구현 시 스택을 적절히 활용하면 코드의 효율성을 높일 수 있습니다.