Home 스택계산기

사칙연산 계산기 : 스택 계산기 – 자바스크립트 구현

스택 계산기 (Stack Caculator)

우리가 일반적으로 사용하는 계산식은 두 개의 피연산자(operand) 사이에 연산자 (operator)를 넣는 구조인 중위 표기식 (연산자를 가운데에 넣는 방법) 을 사용한다.

 

중위표기법 (In-fix) 예시

간단해 보인다 그러나,
이렇게 우선순위를 생각해야하는 계산식이 된다면 어떨까? 저런 상황에서 컴퓨터 코드로 우선순위를 고려해서 연산하기에는 정말 쉽지 않다. 그래서 우리는 스택 자료구조를 활용하여 중위 표기식을 후위 표기식으로 바꾼 뒤, 후위표기식을 가지고 계산하는 방법을 생각해야 한다.

 

후위표기법 (Post-fix) 예시

이것은 식 3 + 2 * 9  를 후위표기법으로 변경한 예시이다. 후위표기법의 연산자는 오른쪽에 있다고 하였다. 3 + 2 * 9  에서 2 * 9  다음 3  을 더해 주는거긴 한데,  여기서 연산 방법은 포스트 아래.

 

중위표기법을 후위표기법으로 변환 (infix notation to postfix notation)

중위표기법을 후위표기법으로 변환 시에는, 연산자 우선순위를 고려해야한다. 연산자 우선순위는,
‘*’ 와 ‘/’ 가 1 순위고, ‘+’ 와 ‘-‘ 가 2 순위다. 우리가 중위표기식에서는 괄호를 쳐진곳을 우선 계산 하지만, 후위표기식에서는 좀 다르다. 이걸 이해하려면 좀 복잡해서, 인터넷에서 누군가가 정리해둔 자료를 참고해서 변환을 짰다.

  1. 우선순위는 ( )  < + -  < * /  순이다.
  2. 입력받은 중위 표기식 한 글자씩 읽어들인다.
  3. 읽어들인 글자가 피연산자이면 후위표기식에 적는다.
  4. 읽어들인 글자가 연산자인경우
    1. 왼쪽 괄호 (  인 경우, 스택에 넣는다. (  를 스택에 넣는다)
    2. 오른쪽 괄호 )  인 경우, 왼쪽 괄호 (  를 꺼낼 떄 까지 스택에서 하나 씩 꺼내서 후위표기식에 적고, 왼쪽 괄호 (  를 뽑으면 버리고 끝낸다.
    3. 나머지 사칙 연산자의 경우, 그 연산자가 스택의 최상위 노드
      스택의 가장 윗 부분을 뜻하는거다
      보다 우선순위가 높을 때 까지, 최상위 노드를 꺼내 후위표기식에 적는다. 현재 연산자가 스택의 최상위 노드보다 우선순위가 높아졌다면 스택에 넣고 끝낸다.
      예) 스택에 * + * /  가 있을 경우, 읽어들인 연산자가 *  이면, *  가 우선순위가 +  보다 때문에, 스택 두번째에 있는  +  까지 차례대로 빼서 후위표기식에 적은 뒤, 스택에 읽어들인 * 를 넣는다.
  5. 2 ~ 4 를 반복해서, 중위표기식을 모두 읽었다면, 스택에 있는 연산자를 pop 으로 꺼내, 후위표기식에 적는다.
  6. 다 적으면 결과가 나온다.
JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
toPostfix = (infixStr) => {
  const valInfix = infixStr;
  const arrayInfix = valInfix.split('');
    
  const arrayOperators = [];
  const arrayPostfix   = [];
    
  // http://maytrees.tistory.com/71
  // 음수를 나타내는 -의 경우에는 저 알고리즘에서 처리 불가능 합니다.
  // - 연산자의 대상이 되는 두 숫자가 없기 때문인데요.
  // 앞에서 부터 읽어들이면서 지금까지 읽어들인 괄호를 제외한 연산자가 숫자보다 많은 경우에
  // -는 음수 처리를 하는 코드를 넣으면 해결이 될 것 같기도 하네요.
 
 
  // 0. 우선순위는 '(' < '+' = '-' < '*' = '/' 순이다.
  const objCharPriority = {
    '*' : 3,
    '/' : 3,
    '+' : 2,
    '-' : 2,
    '(' : 1,
    ')' : 1
  }
  
  // 1. 입력받은 중위 표기식에서 한 글자씩 읽어들인다.
  let tempNumberInput = '';
  
  for (let i = 0; i < arrayInfix.length; i++) {
 
    // 2. 읽어들인 글자가 피연산자이면 후위 표기식에 적는다
    if (arrayInfix[i] >= '0' && arrayInfix[i] <= '9' || arrayInfix[i] == '.') {
      tempNumberInput += arrayInfix[i];
      //arrayPostfix.push(char);
    } else {
      
      // 숫자는 1문자가 아니다!
      if (tempNumberInput != '') {
        arrayPostfix.push(parseFloat(tempNumberInput));
        tempNumberInput = '';
      }
      
      if (arrayInfix[i] === ' ') continue;
      
      // 3. 읽어들인 글자가 연산자이면
    
      if (arrayInfix[i] === '(') {
        // 3-1. 왼쪽 괄호일 경우 스택에 넣는다.
        arrayOperators.push(arrayInfix[i]);  
      } else if (arrayInfix[i] === ')') {
        // 3-2. 오른쪽 괄호일 경우 왼쪽 괄호를 꺼낼 때까지 스택에서 하나씩 꺼내 후위 표기식에 적고 왼쪽 괄호를 뽑으면 버리고 끝낸다.
        let 抜き = '';
        while (arrayOperators.length) {
          抜き = arrayOperators.pop();
          if (抜き === '(') break;
          arrayPostfix.push(抜き);
        }
      } else {
        // 3-3. 나머지 사칙 연산자의 경우 그 연산자가 스택의 최상위 노드보다 우선순위가 높을 때까지 스택의 최상위 노드를 꺼내 후위 표기식에 적는다.
 
        while (arrayOperators.length && objCharPriority[arrayOperators[arrayOperators.length - 1]] >= objCharPriority[arrayInfix[i]]) {
          const 抜き = arrayOperators.pop();
          arrayPostfix.push(抜き);
        }
        
        // 현재 연산자가 스택의 최상위 노드보다 우선순위가 높아졌다면 스택에 넣고 끝낸다.
        arrayOperators.push(arrayInfix[i]);
        
      }
      
    }  
        
  }
  
  // 숫자는 1문자가 아니다!
  if (tempNumberInput != '') {
    arrayPostfix.push(parseFloat(tempNumberInput));
    tempNumberInput = '';
  }
  
  // 4. 1~3 을 반복해서 중위 표기식을 모두 읽어들였다면 스택에 있는 연산자를 최상위 노드부터 꺼내 후위 표기식에 적는다.
  while (arrayOperators.length)
    arrayPostfix.push(arrayOperators.pop());
        
  return postfix = arrayPostfix.join(' ');
 
}
이 소스에서 내가 1문자씩 읽어들이는 바람에, 여러자리 숫자의 경우에 따로따로 읽어버리는 문제가 있어서 숫자의 경우 연산자를 읽을 때 까지 미리 저장해두게 작성했다.

 

후위표기법을 연산 (Postfix Expression Evaluation)

  1. 후위표기법 왼쪽 부터 읽어들여서 숫자인 경우 스택에 push로 넣는다. 스택 : [3, 2, 9]
  2. 연산자를 만난경우, (이 경우엔 *) 스택에 넣었던 피연산자 (숫자)를 2개 pop 으로 꺼낸다. [9, 2]   스택 : [3]&nbsp;
  3. 2에서의 연산자 (*)로, 피연산자 (2, 9) 를 서로 곱한다. ※ 나누기와 빼기의 경우 피연산자 위치에 따라 결과가 다르므로 주의하자.
  4. 3 에서 연산한 결과 값을 다시 스택에 넣는다. 스택 : [3, 18]
  5. 오른쪽으로 읽어들여서, 다시 연산자 (+)를 만났으니, 피연산자 두개를 스택에서 빼낸다. [18, 3] 스택 : []
  6. 5 에서 사용할 연산자  (+)와 (3, 18) 을 연산 후 결과를 스택에 다시 넣는다. 스택 : [22]
  7. 후위표기법을 모두 읽어 처리한 경우, 스택에는 숫자 하나의 값이 존재한다. 이것이 결과 값이다. 빼서 쓰면 되겠다.
JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
evalPostfix = (postfix) => {
  
  // 후위표기법 연산
  // http://soen.kr/lecture/ccpp/cpp2/19-3-2.htm # MakePostfix
  try {
 
    const operatorFunctions = {
      '*' : (o1, o2) => { return o1 * o2 },
      '/' : (o1, o2) => { return o1 / o2 },
      '+' : (o1, o2) => { return o1 + o2 },
      '-' : (o1, o2) => { return o1 - o2 }
    }
    
    const stringPostfix = postfix;
    
    const arrayPostfix = postfix.split(' ');
    
    const arrayCalcStack = [];
    
    for (let i = 0; i < arrayPostfix.length; i++) {
      
      if (!isNaN(arrayPostfix[i])) {
        // 숫자로 인식되는 부분만큼 읽어서 스택에 푸시한다.
        arrayCalcStack.push(parseFloat(arrayPostfix[i]));
      } else {
        
        // 연산자인경우 피연산자 두개를 꺼내서 연산 후 결과를 스택에 넣는다.
        const operator = arrayPostfix[i];
        
        const operand2 = arrayCalcStack.pop();
        const operand1 = arrayCalcStack.pop();
                
        const operateResult = operatorFunctions[operator](operand1, operand2);
        
        arrayCalcStack.push(operateResult);
                
      }
      
    }
    
    // 마지막으로 스택에 남아있는 값이 최종연산된 값이다
    return arrayCalcStack.pop();
    
  } catch (e) {
    // 표기식 오류
  }
}
원래, 후위표기식이 유효한 식인지 검증을 해야 되는데, 거기까지 정리하기엔 번거로워서 그냥 예외처리로 했다. operand2  와 operand1  의 순서가 바꼇는데, 이건 나누셈과 뺄셈에서 피연산자가 누가되느냐에 따라 결과가 달라지기 때문이다.