Javascript/Algorithm : 전위/중위/후위 표기법

개요

회사에서 간단한 실습 과제로 회사 솔루션의 에디터 내 계산기 기능을 구현하는 것이 주어졌다. 그래서 전위, 중위, 후위 표기법에 대해 다시 공부하면서, 후위 표기법을 통한 계산으로 구현한 Javascript 코드를 작성해보았다.

중위 표기법

• 중위 표기법(infix) : 피연산자 사이 연산자가 있는 형태로 일반적으로 사용하는 수식 표기법이다. 괄호와 연산자 우선순위를 고려한 다음 순서대로 연산이 이루어진다.
  컴퓨터는 왼쪽부터 수식을 하나씩 읽어가기 때문에, 우선순위가 있는 중위 표기법으로 구현하기 어려움이 있다. 그래서 전위 표기법, 후위 표기법으로 변환한 후에 계산을 진행한다.

전위 표기법

• 전위 표기법(prefix) : 연산자를 먼저, 피연산자를 나중에 표기하는 방식
• 중위 표기법에서 전위 표기법 변환 (중위 표기법 : 1+2/3*(4+5))
  1. 연산자 우선순위에 맞게 소괄호로 묶는다. (1+((2/3)*(4+5)))
  2. 괄호 안에 있는 연산자들을 앞으로 옮긴다. (+1(/*(23)+(45)))
  3. 괄호들을 모두 없애준다. +1/*23+45

후위 표기법

• 후위 표기법(postfix) : 피연산자를 먼저, 연산자를 나중에 표기하는 방식

• 중위 표기법에서 후위 표기법 변환 (중위 표기법 : 1+2/3*(4+5))

  1. 연산자 우선순위에 맞게 소괄호로 묶는다. (1+((2/3)*(4+5)))
  2. 괄호 안에 있는 연산자들을 뒤로 옮긴다. (1((23)/(45))+*+)
  3. 괄호들을 모두 없애준다. 123/45+*+

• 스택을 이용한 중위 표기법에서 후위 표기법 변환 및 계산

  • 피연산자는 output에, 연산자는 operator stack(연산자 스택)에 push
  • 탐색한 연산자가 operator stack top에 있는 연산자보다 우선순위가 같거나 낮은지 확인
  • 우선순위가 같거나 낮다면 operator stack top에 있는 연산자를 pop하여 output에 push, operator stack에 탐색한 연산자를 push하는 방식
  • 후위 표기법 계산은 왼쪽부터 stack에 쌓으면서 연산자가 탐색되면, stack에 쌓여있는 두 개의 피연산자를 pop하여 해당 연산 진행한 후 다시 stack에 push하는 방식
    • 연산1(2/3) => 연산2(4+5) => 연산3(연산1*연산2) => 연산4(연산3+1)

중위 표기법을 후위 표기법으로 변환 코드

const infix = `["1", "+", "2",  "/", "3", "*", "(", "4", "+", "5", ")"]`; // 중위 표기법

// 중위 표기법을 후위 표기법으로 전환
let output = [];
let operatorStack = [];
let operators = {
  "+": 1,
  "‑": 1,
  "*": 2,
  "/": 2,
  "%": 2,
  "^": 3, // 제곱 연산자
  "=": 0,
};

for (let i = 0; i < infix.length; i++) {
  let token = infix[i];

  if (!isNaN(Number(token || NaN))) { // 피연산자(숫자)인 경우 output에 push
    output.push(token);
  } else if (token in operators) { // 연산자인 경우
    while (
      operatorStack.length > 0 &&
      operators[operatorStack[operatorStack.length - 1]] >=
        operators[token] &&
      operatorStack[operatorStack.length - 1] !== "("
    ) { // operatorStack top에 연산자 우선순위가 token보다 높은 경우 pop하여 output에 push
      output.push(operatorStack.pop());
    }
    operatorStack.push(token); // operatorStack에 push
  } else if (token === "(") { // 여는 괄호인 경우 operatorStack에 push
    operatorStack.push(token);
  } else if (token === ")") { // 닫는 괄호인 경우 여는 괄호가 나오거나 operatorStack가 비워질 때까지 operatorStack에서 pop 후 output에 push
    while (
      operatorStack.length > 0 &&
      operatorStack[operatorStack.length - 1] !== "("
    ) {
      output.push(operatorStack.pop());
    }
    operatorStack.pop();
  }
}

while (operatorStack.length > 0) {  // operatorStack에 남아있는 연산자들을 output에 push
  output.push(operatorStack.pop());
}

후위 표기법 계산 코드

for (let i = 0; i < res.length; i++) {
  let token = res[i];
  if (!isNaN(Number(token))) { // 피연산자(숫자)인 경우 stack에 push
    stack.push(Number(token));
  } else { // 연산자인 경우 stack에 있는 두 개의 수를 pop하여, 해당 연산 수행 후 stack에 다시 push
    let operand2 = stack.pop();
    let operand1 = stack.pop();

    switch (token) {
      case "+":
        stack.push(operand1 + operand2);
        break;
      case "‑":
        stack.push(operand1 - operand2);
        break;
      case "*":
        stack.push(operand1 * operand2);
        break;
      case "/":
        stack.push(operand1 / operand2);
        break;
      case "%":
        stack.push(operand1 % operand2);
        break;
      case "^": // 제곱 연산자
        stack.push(operand1 ** operand2);
        break;
    }
  }
}

const answer = stack.pop(); // 후위 표기법 계산 결과