Computer >> 컴퓨터 >  >> 프로그래밍 >> JavaScript

JavaScript로 연산자 우선순위를 반영한 수학 표현식 계산기 구현하기

문제 정의

수학 표현식을 문자열 형태로 입력받아, 그 계산 결과를 숫자(number)로 반환하는 자바스크립트 함수를 작성해야 합니다. 단순히 왼쪽부터 차례대로 계산하는 것이 아니라, 실제 수학의 규칙처럼 연산자 우선순위까지 올바르게 반영해야 한다는 점이 핵심입니다.

함수가 지원해야 하는 연산자는 다음과 같습니다.

  • + (덧셈)
  • - (뺄셈)
  • * (곱셈)
  • / (나눗셈) — 부동소수점(floating-point) 나눗셈으로 처리하며, 0으로 나누는 경우에는 0을 반환하도록 안전장치를 둡니다.

연산자는 기본적으로 왼쪽에서 오른쪽 방향으로 평가되며, 곱셈(*)과 나눗셈(/)은 덧셈(+)과 뺄셈(-)보다 반드시 먼저 계산되어야 합니다. 추가로, 식 맨 앞이나 여는 괄호 바로 뒤에 등장하는 음수처럼 단항 마이너스(unary minus)도 처리할 수 있어야 완성도 높은 계산기라고 할 수 있습니다.

풀이 접근: 셔팅야드 알고리즘

이런 문제는 에츠허르 다익스트라(Dijkstra)가 고안한 셔팅야드(shunting-yard) 알고리즘을 활용하면 체계적으로 해결할 수 있습니다. 이 알고리즘은 사람이 읽는 중위 표기법(infix) 수식을 컴퓨터가 계산하기 쉬운 후위 표기법(postfix, 역폴란드 표기법)으로 변환한 뒤, 스택(stack)을 이용해 값을 평가하는 방식입니다.

전체 흐름은 다음과 같습니다.

  1. 입력 문자열에서 공백을 제거하고, 문자를 하나씩 스캔하면서 숫자·연산자·괄호를 구분합니다.
  2. 각 연산자마다 우선순위(pred)와 결합 방향(assoc)을 미리 정의해 둡니다.
  3. '-'가 단항 음수인지 이항 뺄셈인지 문맥을 보고 판별하여 별도의 'negate' 연산자로 분류합니다.
  4. 스택에 쌓인 연산자와 우선순위를 비교해, 출력 큐(output queue)에 후위 표기식을 완성합니다.
  5. 완성된 후위 표기식을 스택으로 평가하여 최종 결과를 반환합니다.

연산자 우선순위 정의

연산자우선순위(pred)결합 방향(assoc)
+, -2left
*, /3left
negate (단항 음수)4right

우선순위 값이 클수록 먼저 계산됩니다. 왼쪽 결합(left) 연산자는 같은 우선순위끼리 만나면 스택의 연산자를 먼저 꺼내 처리하고, 오른쪽 결합(right) 연산자인 negate는 우선순위가 엄격히 더 높은 경우에만 대기시킵니다.

구현 예제 코드

다음은 위 알고리즘을 그대로 구현한 전체 코드입니다.

const exp = '6 - 4';

const findResult = (exp = '') => {
   const digits = '0123456789.';
   const operators = ['+', '-', '*', '/', 'negate'];
   const legend = {
      '+': { pred: 2, func: (a, b) => a + b, assoc: 'left' },
      '-': { pred: 2, func: (a, b) => a - b, assoc: 'left' },
      '*': { pred: 3, func: (a, b) => a * b, assoc: 'left' },
      '/': {
         pred: 3,
         func: (a, b) => (b !== 0 ? a / b : 0),
         assoc: 'left'
      },
      'negate': { pred: 4, func: (a) => -1 * a, assoc: 'right' }
   };

   exp = exp.replace(/\s/g, '');
   let operations = [];
   let outputQueue = [];
   let ind = 0;
   let str = '';

   while (ind < exp.length) {
      let ch = exp[ind];

      if (operators.includes(ch)) {
         if (str !== '') {
            outputQueue.push(new Number(str));
            str = '';
         }
         // 단항 음수(negate) 판별
         if (ch === '-') {
            if (ind == 0) {
               ch = 'negate';
            } else {
               const nextCh = exp[ind + 1];
               const prevCh = exp[ind - 1];
               if ((digits.includes(nextCh) || nextCh === '(' || nextCh === '-') &&
                   (operators.includes(prevCh) || prevCh === '(')) {
                  ch = 'negate';
               }
            }
         }
         // 우선순위 비교 후 스택의 연산자를 출력 큐로 이동
         if (operations.length > 0) {
            let topOper = operations[operations.length - 1];
            while (operations.length > 0 && legend[topOper] &&
              ((legend[ch].assoc === 'left' && legend[ch].pred <= legend[topOper].pred) ||
               (legend[ch].assoc === 'right' && legend[ch].pred < legend[topOper].pred))) {
               outputQueue.push(operations.pop());
               topOper = operations[operations.length - 1];
            }
         }
         operations.push(ch);

      } else if (digits.includes(ch)) {
         str += ch;

      } else if (ch === '(') {
         operations.push(ch);

      } else if (ch === ')') {
         if (str !== '') {
            outputQueue.push(new Number(str));
            str = '';
         }
         while (operations.length > 0 && operations[operations.length - 1] !== '(') {
            outputQueue.push(operations.pop());
         }
         if (operations.length > 0) { operations.pop(); }
      }
      ind++;
   }

   if (str !== '') { outputQueue.push(new Number(str)); }
   outputQueue = outputQueue.concat(operations.reverse());

   // 후위 표기식 평가
   let res = [];
   while (outputQueue.length > 0) {
      let ch = outputQueue.shift();
      if (operators.includes(ch)) {
         if (ch === 'negate') {
            res.push(legend[ch].func(res.pop()));
         } else {
            let [num2, num1] = [res.pop(), res.pop()];
            res.push(legend[ch].func(num1, num2));
         }
      } else {
         res.push(ch);
      }
   }
   return res.pop().valueOf();
};

console.log(findResult(exp));

실행 결과

2

'6 - 4'라는 식이 입력되었을 때 함수는 정확히 2를 반환합니다. 같은 방식으로 '2 + 3 * 4'를 넣으면 곱셈이 먼저 적용되어 14가 나오고, '-3 + 5'처럼 단항 음수가 포함된 식도 2로 올바르게 계산됩니다.

코드 동작 원리 정리

  • 토큰 분리: 공백을 제거한 뒤, 숫자 문자는 임시 문자열(str)에 모았다가 연산자나 괄호를 만나는 시점에 하나의 숫자로 변환해 출력 큐에 넣습니다.
  • 단항 음수 판별: '-'가 식의 맨 앞에 있거나, 앞이 연산자·여는 괄호이면서 뒤가 숫자·괄호·음수라면 이항 뺄셈이 아닌 negate로 치환합니다.
  • 우선순위 관리: 새 연산자를 스택에 push하기 전에, 스택 위(top)의 연산자보다 우선순위가 낮거나(왼쪽 결합의 경우 같으면) 결합 규칙상 먼저 처리해야 하는 연산자를 모두 출력 큐로 옮깁니다.
  • 괄호 처리: ')'를 만나면 대응하는 '('를 찾을 때까지 스택의 연산자를 모두 출력 큐로 이동시켜 괄호 내부가 먼저 계산되도록 합니다.
  • 최종 평가: 남은 스택 연산자를 뒤집어 붙여 후위 표기식을 완성한 후, 피연산자 두 개를 꺼내 연산자에 대응하는 함수(func)로 계산하는 과정을 반복해 결과를 얻습니다.

이처럼 셔팅야드 알고리즘을 사용하면 복잡한 재귀 파서 없이도 연산자 우선순위, 결합 방향, 괄호, 단항 음수를 모두 지원하는 수식 계산기를 견고하게 만들 수 있습니다.