사칙연산 후위표기식의 계산 알고리즘 자바스크립트로 만들어보기

추상자료형

추상자료형에 대해 검색해 보면

'기능의 구현 부분을 나타내지 않고 순수한 기능이 무엇인지 나열한 것' 혹은

'기능의 구현 부분을 나타내지 않고 자료구조의 특성과 연산을 설명한 것'이라고 한다.

이를 더 자세히 생각해 보자면 추상자료형은 특정 자료구조에 대한 프로그래머의 의도를 명확히 설명하고 오해를 없애기 위해

구현 부분을 만드는 게 아니라 단지 어떤 객체가 어떤 행동을 하는지만 설명함으로써 프로그래머의 의도를 정확하게 반영한 자료구조를 정의하기 위한 방법이라고 생각한다.

 

스택의 추상자료형

스택 객체: 0개 이상의 원소를 갖는 유한 순서 리스트
연산
1. CreateStack(maxSize) ::= 스택의 크기가 maxSize인 빈 스택을 생성하고 반환한다.
2. StackIsFull(stack, maxSize) ::= stack의 element의 개수 == maxSize 면 true, 아니면 false
3. Push(stack, item) ::= 만약 StackIsFull이 참이면 에러, 아니면 스택의 가장위에 item 삽입하고 스택 반환.
4. StackIsEmpty(stack) ::= 만약 스택의 갯수가 0이면 true, 아니면 false
5. Pop(stack) ::= 만약 StackIsEmpty가 참이면 에러, 아니면 스택의 가장 위에 있는 원소를 삭제하고 반환.

 

스택은 다양하게 응용된다. 변수에 메모리 항당과 수집을 위한 시스템 스택, 서브루틴의 수행이 끝난 뒤에 돌아갈 함수 주소를 저장하기 위한 서브루틴 호출 관리, 후위수식계산, 컴파일러, 순환 호출이 끝나고 되돌아갈 실행주소를 저장하기 위한 순환 호출 관리.

그러면 후위수식계산을 하기 위한 스택의 응용을 자바스크립트로 한번 만들어보자.

후위수식계산이란 간단히 말해 입력되는 숫자의 순서와 연산자 우선순위에 따른 계산의 처리 순서 충돌을 해결하는 방법이다.

예를 들어 const result = 1 + 2 * 3이라고 하면 사칙연산에 따라 2 * 3이 먼저 계산되어 답은 7이 되어야 한다.

하지만 프로그램은 왼쪽에서부터 읽기 때문에 그대로 계산 스택에 들어가면 1 + 2를 먼저 하게 된다. 

이러한 충돌을 해결하기 위해 후위수식계산방법을 사용한다. 간단히, 1 + 2 * 3은 "123*+" 로 변환되는 것이다

이와 동일하게 1+5*2+1/2는 문자열 "152*12/++" 이 된다.

그럼 컴퓨터는 문자열 "152*12/++"를 가져다가 1+(5*2)+(1/2)의 결과를 내면 된다.

 

일단 말로 설명하면 앞에서부터 순회하면서 스택에 쌓을 건데, 만약 피연산자를 만나면 스택에 push 하고

연산자를 만나면 pop을 두 번 해서 (이항연산자니까) 피연산자를 꺼내고 연산을 수행한 후에 결괏값을 push 한다.

순회가 끝나면 스택에 마지막 남은 결괏값을 꺼내준다.

 

이것을 자바스크립트로 구현해 보자

const operator = ["+", "-", "*", "/"];

function checkIsNotNaN(value) {
  if (Number.isNaN(value)) {
    throw new Error("input wrong value");
  }
}

function evalPostfix(exp) {
  const stack = new Stack(100);

  try {
    for (let symbol of exp) {
      if (operator.includes(symbol)) {
        let oper2 = stack.pop();
        let oper1 = stack.pop();
        if (symbol === "+") stack.push(oper1 + oper2);
        if (symbol === "-") stack.push(oper1 - oper2);
        if (symbol === "*") stack.push(oper1 * oper2);
        if (symbol === "/") stack.push(oper1 / oper2);
      } else {
        const numberSymbol = Number(symbol);
        checkIsNotNaN(numberSymbol);
        stack.push(numberSymbol);
      }
    }
    return stack.pop();
  } catch (error) {
    console.log(error.message);
    return null;
  }
}

 

간단히 에러처리하는 부분을 제외하고 보면

const operator = ["+", "-", "*", "/"];

function evalPostfix(exp) {
  const stack = new Stack(100);

  for (let symbol of exp) {
    if (operator.includes(symbol)) {
      let oper2 = stack.pop();
      let oper1 = stack.pop();
      if (symbol === "+") stack.push(oper1 + oper2);
      if (symbol === "-") stack.push(oper1 - oper2);
      if (symbol === "*") stack.push(oper1 * oper2);
      if (symbol === "/") stack.push(oper1 / oper2);
    } else {
      const numberSymbol = Number(symbol);
      stack.push(numberSymbol);
    }
  }
  return stack.pop();
}

// 2+3*4 => 234*+ === 14
console.log(evalPostfix("234*+"));
// 1+5*2 => 152*+ === 11
console.log(evalPostfix("152*+"));
// 1+5*2+1/2 => 152*12/++ === 11.5
console.log(evalPostfix("152*12/++"));

 

이렇게 구현할 수 있다.

exp는 문자열이니 이터러블이므로 for of문을 사용할 수 있다.

하나씩 순회하면서 operator배열에 포함된 문자를 만나면 stack.pop()으로 피연산자 두 개를 뽑아서 연산을 하고 stack.push()를 한다.

만약 operator배열에 포함되지 않는 숫자라면 숫자타입으로 변경해서 stack.push()한다. 

숫자타입으로 변경해야 pop을 해서 사칙연산을 수행할 수 있다.

만약 숫자타입으로 변경할 수 없는 값을 입력한다면 에러처리가 되어야 하므로

validation함수를 추가하고 try, catch문으로 처리할 수 있다.