스택을 이용한 계산기 만들기

수식의 다양한 표기법 🚀

살다 보면 계산이 필요한 상황을 자주 만나게 됩니다. 그럴 때마다 우리는 작은 수를 다루는 문제라면 단순 암산으로 해결하지만, 보다 큰 수를 다루는 경우에는 정확도를 위해 계산기의 도움을 받습니다. 그런데 우리가 이해하고 있는 계산식을 컴퓨터는 이해할 수 없다는 사실을 알고 계신가요?

1 + 3이라는 계산식을 우리는 직관적으로 이해할 수 있지만, 컴퓨터는 이를 연산자(+)와 피연산자(1, 3)로 분리한 후 일련의 로직으로 이해시켜야 합니다. 그리고 우리가 일상에서 사용하는 계산식을 중위 표현식(Infix Expression)이라 부르는데, 컴퓨터는 이를 바로 이해할 수 없기 때문에 전위 표기법(prefix) 또는 후위 표기법(postfix) 중 하나로 변환해 사용합니다.

위 그림에서 확인 가능한 것처럼 중위 표기법은 연산자를 피연산자 사이에 배치하는 방식이고, 전위 표기법과 후위 표기법은 각각 연산자를 피연산자의 앞뒤에 배치하는 방식입니다. 이들을 나중에 만났을 때 혼란스럽지 않도록 지금부터 함께 표기법과 관련된 알고리즘을 알아보고, 직접 예제를 만들어 보면서 익혀봅시다!

표기법 변환 알고리즘

중위 표기법으로 작성된 (A+B)*C를 후위 표기법 AB+C*로 변환하는 과정을 그림과 함께 알아보겠습니다.

변환 과정은 다음과 같습니다.

• ① 표기법 변환에 사용할 스택을 준비합니다.
• ② 중위 표현식을 왼쪽부터 오른쪽으로 읽으며 토큰 단위로 분해하고 변환을 진행합니다.
• ③ 읽고 있는 토큰이 피연산자라면 그냥 출력합니다.
• ④ 읽고 있는 토큰이 연산자라면 다음 케이스들을 고려합니다.
• case 1 스택이 비어있는 경우, 토큰을 스택에 삽입합니다.
• case 2 스택이 비어있지 않은 경우, 스택의 최상위 노드와 현재 읽고 있는 토큰의 우선순위를 비교하여, 우선순위가 더 높은 연산자를 스택 상단에 위치할 수 있도록 합니다.
• case 3 현재 읽고 있는 토큰이 )인 경우, (를 만날 때까지 스택 안의 노드들을 제거하면서 출력합니다.
• ⑤ 토큰을 모두 읽었다면, 스택이 빌 때까지 남은 노드들을 제거하면서 출력합니다.

본문에서 전위 표기법은 소개하지 않으니 양해 부탁드립니다 😅

후위 표현식 계산 알고리즘

위에서 만든 후위 표현식을 계산하는 알고리즘은 간단합니다.

이번에도 과정을 간단하게 설명해 보겠습니다.

• ① 표현식 계산에 사용할 스택을 준비합니다.
• ② 표현식을 왼쪽부터 오른쪽으로 읽으며 토큰 단위로 분해하고 계산을 진행합니다.
• ③ 읽고 있는 토큰이 피연산자라면, 그대로 스택에 삽입합니다.
• ④ 읽고 있는 토큰이 연산자라면, 스택에서 피연산자 2개를 빼낸 다음 계산해서 다시 스택에 삽입합니다.
• ⑤ 위 과정을 반복하면 마지막에는 스택에 하나의 노드만 남게 되는데, 그것이 최종 결과가 됩니다.

설명의 편의를 위해 A=1, B=2, C=3이라 가정했습니다.

스택 계산기 만들기 🔥

연산자 우선순위 비교 함수 구현

중위 표현식을 후위 표현식으로 변환하는 과정에서 연산자의 우선순위를 비교하여 표현식 상의 위치를 결정해야 합니다. 이 과정이 없다면 더하기와 곱하기 연산자의 우선순위가 동일하여 계산에 문제가 발생합니다.

/**
 * 연산자의 우선순위를 구하는 함수
 * @param {string} operator
 * @param {boolean} inStack
 * @returns {number} priority
 */
const getPriority = (operator, inStack) => {
  if (operator === '+' || operator === '-') {
    return 1;
  } else if (operator === '*' || operator === '/') {
    return 2;
  } else if (operator === '(') {
    if (inStack) return 0;
    else return 5;
  } else if (operator === ')') {
    return 4;
  }
};

getPriority는 operator와 inStack을 매개변수로 받는 유틸 함수입니다. 연산자와 관련된 매개변수는 별도로 설명할 필요가 없지만, 스택에 담겨 있는지의 여부도 함께 받는 이유가 궁금할 수 있습니다. 이는 ( 연산자 때문인데요. 실제로 계산을 할 때 (을 만나게 되면 그 어떤 연산자보다 우선순위가 높습니다. 하지만 이미 괄호를 연 경우에는 )를 만날 때까지 우선순위가 가장 낮아집니다.

이런 이유에서 매개변수 inStack을 이용해 괄호간의 우선순위를 확실히 계산했습니다.

후위 표현식 변환 함수 구현

중위 표현식을 후위 표기법으로 변환하는 방법은 위에서 설명한 알고리즘을 따라 구현했습니다.

/**
 * 중위 표현식을 후위 표현식으로 변환하는 함수
 * @param {string} infix
 * @returns {string} postfix
 */
const infixToPostfix = (infix) => {
  const operators = ['(', ')', '+', '-', '*', '/'];
  const stack = [];
  const postfix = [];

  infix = infix.split(' ');
  infix.forEach((token) => {
    if (operators.includes(token)) {
      if (token === ')') {
        // 토큰이 ')' 연산자인 경우, '('를 만날 때까지 Postfix에 삽입
        let popped = stack.pop();
        while (popped !== '(') {
          postfix.push(popped);
          popped = stack.pop();
        }
      } else {
        if (stack.length === 0) {
          stack.push(token);
        } else {
          // 최상위 노드와 토큰의 연산자 우선순위 비교
          // 이 과정이 없으면 '1 - 3 * 2'의 후위 표현식이 '1 3 - 2 *'가 됨
          let popped = stack.pop();
          if (getPriority(popped, true) > getPriority(token, false)) {
            postfix.push(popped);
          } else {
            stack.push(popped);
          }
          stack.push(token);
        }
      }
    } else {
      // 토큰이 피연산자인 경우 Postfix에 삽입
      postfix.push(token);
    }
  });

  // 스택의 남은 노드(연산자)를 모두 후위에 붙임
  while (stack.length !== 0) {
    postfix.push(stack.pop());
  }

  return postfix.join(' ');
};

조건문의 분기마다 주석을 달았기 때문에 크게 어려운 부분은 없을 거라 생각합니다. 다만 주의해야 하는 부분이 있다면, 현재 읽고 있는 토큰이 연산자인 경우입니다. 스택에 이미 다른 연산자가 있고, 새로운 연산자를 읽고 있는 경우라면 두 연산자의 우선순위를 비교한 다음, 우선순위가 더 큰 연산자가 스택의 상단에 위치할 수 있도록 배치해야 합니다.

후위 표현식 계산 함수 구현

계산 함수 calculate 역시 위에서 설명한 알고리즘을 바탕으로 구현했습니다.

/**
 * 후위 표현식을 계산하는 함수
 * @param {string} postfix
 * @returns {number} result
 */
const calculate = (postfix) => {
  const operators = ['+', '-', '*', '/'];
  const stack = [];

  postfix.split(' ').forEach((token) => {
    if (operators.includes(token)) {
      let operand1 = parseFloat(stack.pop());
      let operand2 = parseFloat(stack.pop());
      let temp;

      if (token === '+') temp = operand2 + operand1;
      else if (token === '-') temp = operand2 - operand1;
      else if (token === '*') temp = operand2 * operand1;
      else if (token === '/') temp = operand2 / operand1;

      stack.push(temp);
    } else {
      stack.push(token);
    }
  });

  return stack[0];
};

반복문을 올바르게 수행하게 되면 스택에는 하나의 노드만 남아있게 되며, 해당 노드가 최종 결과이므로 이를 반환하면 됩니다. 스택을 이용한 계산기를 만드는 예제는 표기법을 변환하는 과정이 조금 머리 아프지, 실질적으로 계산하는 부분은 비교적 간단하게 구현할 수 있습니다.

References 📝

• 스택 예제, 중위 표기를 후위 표기로 변환하기
• What is Infix Prefix & Postfix Expressions in Data Structures