Shunting Yard 알고리즘이란?

Shunting Yard 알고리즘은 네덜란드의 컴퓨터 과학자 에디스커 다익스트라(Edsger Dijkstra)가 고안한 알고리즘으로, 중위 표기법(Infix) 수식을 후위 표기법(Postfix, RPN)으로 변환하는 데 사용됩니다. 컴퓨터는 후위 표기법을 사용하면 연산 우선순위나 괄호 처리 없이도 쉽게 계산할 수 있기 때문에 계산기, 컴파일러 등에 활용됩니다.

Infix  : 3 + 4 * 2 / (1 - 5)
Postfix: 3 4 2 * 1 5 - / +

알고리즘 요약

• 숫자는 바로 출력
• 연산자는 우선순위 비교 후 스택 처리
• 왼쪽 괄호 (는 스택에 push
• 오른쪽 괄호 )는 (가 나올 때까지 pop

Pseudo code

for each token in input:
    if token is number:
        output.push(token)
    else if token is operator:
        while there is an operator on the stack with greater precedence:
            output.push(stack.pop())
        stack.push(token)
    else if token is "(":
        stack.push(token)
    else if token is ")":
        while stack top is not "(":
            output.push(stack.pop())
        stack.pop() // remove "("

while stack not empty:
    output.push(stack.pop())

중위 표기법, 후위 표기법

• 중위표기법: 사람에게 익숙한 수식 표기 ex. (3 + 4)
• 후위표기법: 컴퓨터가 계산하기 쉬운 수식 형태 ex. (3 4 +)
• 우선순위: *, /, >, +, -
• 결합법칙: +, *는 왼쪽에서 오른쪽, ^는 오른쪽에서 왼쪽

TypeScript 구현 예시

type Token = string;

const precedence: Record<string, number> = {
  "+": 1,
  "-": 1,
  "*": 2,
  "/": 2,
};

const isLeftAssociative = (op: string): boolean => {
  return ["+", "-", "*", "/"].includes(op); // 모두 좌결합
};

const isOperator = (token: Token): boolean => {
  return ["+", "-", "*", "/"].includes(token);
};

export function shuntingYard(tokens: Token[]): Token[] {
  const output: Token[] = [];
  const operatorStack: Token[] = [];

  for (const token of tokens) {
    if (!isNaN(Number(token))) {
      // 숫자면 출력으로
      output.push(token);
    } else if (isOperator(token)) {
      while (
        operatorStack.length &&
        isOperator(operatorStack[operatorStack.length - 1]) &&
        (
          precedence[operatorStack[operatorStack.length - 1]] > precedence[token] ||
          (precedence[operatorStack[operatorStack.length - 1]] === precedence[token] && isLeftAssociative(token))
        )
      ) {
        output.push(operatorStack.pop()!);
      }
      operatorStack.push(token);
    } else if (token === "(") {
      operatorStack.push(token);
    } else if (token === ")") {
      while (operatorStack.length && operatorStack[operatorStack.length - 1] !== "(") {
        output.push(operatorStack.pop()!);
      }
      if (operatorStack.length === 0) {
        throw new Error("Mismatched parentheses");
      }
      operatorStack.pop(); // '(' 제거
    }
  }

  while (operatorStack.length) {
    const op = operatorStack.pop()!;
    if (op === "(" || op === ")") {
      throw new Error("Mismatched parentheses");
    }
    output.push(op);
  }

  return output;
}

// usage
const input = ["3", "+", "4", "*", "2", "/", "(", "1", "-", "5", ")"];
const result = shuntingYard(input);
console.log(result.join(" ")); // 출력: 3 4 2 * 1 5 - / +