알고리즘

[알고리즘] 차량기지(Shunting Yard) 알고리즘 괄호가 포함된 수식 처리 기법 소스코드

멱군 2024. 1. 29. 19:18

프로그래밍 언어에서 복잡한 수학적 표현을 다룰 때, 괄호가 포함된 수식을 어떻게 효율적으로 계산할까요? 이러한 문제를 해결하는 데에는 여러 알고리즘이 있지만, 가장 널리 사용되는 방법 중 하나가 바로 'Shunting Yard' 알고리즘입니다. 이 글에서는 Shunting Yard 알고리즘의 기본 원리와 구현 방법에 대해 자세히 알아보겠습니다.

 

 

Shunting Yard 알고리즘의 기본 원리

Shunting Yard 알고리즘은 1960년대에 Edsger Dijkstra에 의해 개발된 알고리즘으로, 중위 표기법(infix notation)으로 작성된 수식을 후위 표기법(postfix notation) 또는 역폴란드 표기법으로 변환하는 데 사용됩니다.

알고리즘의 처리 모양이 차량기지에서 차량을 움직이는 모양과 닮았다고 해서 차량기지 알고리즘이라고도 합니다.

이 알고리즘의 핵심은 연산자의 우선 순위와 괄호를 적절히 처리하여 수식을 후위 표기법으로 변환하는 것입니다.

 

중위 표기법과 후위 표기법

중위 표기법

  • 연산자가 피연산자 사이에 위치하는 방식 (예: A + B)

후위 표기법

  • 연산자가 피연산자 뒤에 위치하는 방식 (예: AB+)

 

알고리즘의 주요 단계

1. 입력 읽기

  • 수식을 문자 단위로 읽습니다.

2. 연산자 처리

  • 스택에 연산자를 쌓습니다.
  • 연산자의 우선 순위를 고려하여 스택에서 연산자를 꺼내 출력합니다.

3. 괄호 처리

  • 여는 괄호 '('는 스택에 쌓습니다.
  • 닫는 괄호 ')'를 만나면 여는 괄호가 나올 때까지 스택에서 연산자를 꺼내 출력합니다.

4. 출력 생성

  • 후위 표기법으로 변환된 수식을 생성합니다.

 

구현 방법

필요한 자료구조

  • 스택: 연산자를 임시로 저장하는 데 사용됩니다.
  • 출력 리스트: 변환된 후위 표기법 수식을 저장합니다.
function shuntingYard(expression) {
    const precedence = {'+': 1, '-': 1, '*': 2, '/': 2};
    let output = [];
    let operatorStack = [];

    for (let token of expression) {
        if (!isNaN(token)) {
            output.push(token);
        } else if (token in precedence) {
            while (operatorStack.length > 0 &&
                   precedence[operatorStack[operatorStack.length - 1]] >= precedence[token]) {
                output.push(operatorStack.pop());
            }
            operatorStack.push(token);
        } else if (token === '(') {
            operatorStack.push(token);
        } else if (token === ')') {
            while (operatorStack.length > 0 && operatorStack[operatorStack.length - 1] !== '(') {
                output.push(operatorStack.pop());
            }
            operatorStack.pop(); // 여는 괄호 제거
        }
    }

    while (operatorStack.length > 0) {
        output.push(operatorStack.pop());
    }

    return output.join('');
}

// 예제 수식
let expression = "3+(4*5)-6/2";
console.log(shuntingYard(expression));

이 코드는 간단한 수식을 입력으로 받아 후위 표기법으로 변환합니다. 자바스크립트의 특성에 맞게 isNaN 함수를 사용하여 숫자를 판별하고, 스택과 출력 배열을 적절히 관리합니다.

 

HTML & JavaScript 코드

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Shunting Yard Algorithm with Calculation</title>
</head>
<body>

<h2>Shunting Yard Algorithm with Calculation</h2>
<label for="expression">Enter an Expression:</label>
<input type="text" id="expression" placeholder="3+(4*5)-6/2">
<button onclick="processExpression()">Calculate</button>
<p id="postfixOutput"></p>
<p id="calculationResult"></p>

<script>
    function shuntingYard(expression) {
        const precedence = {'+': 1, '-': 1, '*': 2, '/': 2};
        let output = [];
        let operatorStack = [];

        for (let token of expression) {
            if (!isNaN(token) && token.trim() !== '') {
                output.push(token);
            } else if (token in precedence) {
                while (operatorStack.length > 0 &&
                       precedence[operatorStack[operatorStack.length - 1]] >= precedence[token]) {
                    output.push(operatorStack.pop());
                }
                operatorStack.push(token);
            } else if (token === '(') {
                operatorStack.push(token);
            } else if (token === ')') {
                while (operatorStack.length > 0 && operatorStack[operatorStack.length - 1] !== '(') {
                    output.push(operatorStack.pop());
                }
                operatorStack.pop();
            }
        }

        while (operatorStack.length > 0) {
            output.push(operatorStack.pop());
        }

        return output;
    }

    function evaluatePostfix(postfix) {
        let stack = [];
        for (let token of postfix) {
            if (!isNaN(token)) {
                stack.push(parseFloat(token));
            } else {
                let b = stack.pop();
                let a = stack.pop();
                switch (token) {
                    case '+': stack.push(a + b); break;
                    case '-': stack.push(a - b); break;
                    case '*': stack.push(a * b); break;
                    case '/': stack.push(a / b); break;
                }
            }
        }
        return stack.pop();
    }

    function processExpression() {
        let expression = document.getElementById("expression").value;
        let postfix = shuntingYard(expression);
        let result = evaluatePostfix(postfix);
        document.getElementById("postfixOutput").innerText = "Postfix Notation: " + postfix.join(' ');
        document.getElementById("calculationResult").innerText = "Calculation Result: " + result;
    }
</script>

</body>
</html>

이 코드는 사용자가 입력한 중위 표기법 수식을 후위 표기법으로 변환하고, 이를 계산하여 결과를 표시합니다.

  • shuntingYard
    • 함수는 중위 표기법 수식을 후위 표기법으로 변환합니다.
  • evaluatePostfix
    • 함수는 후위 표기법 수식을 계산합니다.
  • processExpression
    • 함수는 사용자가 입력한 수식을 처리하고, 후위 표기법 변환 결과와 계산 결과를 화면에 표시합니다.

 

전체소스코드다운로드

위에서 사용한 소스코드는 아래의 파일을 다운로드 받을 수 있습니다.

Shunting Yard 알고리즘.zip
0.00MB

 

 

결론

평소에 연산할 때 괄호는 어떻게 알고리즘으로 처리를 했는지 궁금했었는데 이렇게 또 하나 배워갑니다.

Shunting Yard 알고리즘은 괄호가 포함된 복잡한 수식을 효율적으로 처리하는 데 매우 유용합니다.

이 알고리즘을 이해하고 구현하는 것은 프로그래밍 언어의 파서나 계산기 애플리케이션을 만드는 데 필수적인 기술입니다.

저작자표시 비영리 동일조건