2. Stack #2 Caculator Algorithm1

1. 고려사항

우리는 여러 연산자가 포함된 식을 계산할 때 어떤 과정을 거칠까?

이미 학습된 지식을 바탕으로 우선순위를 파악하고, 이 우선순위에 따라서 순차적으로 계산한다. 하지만, 우선순위를 알고 있지 못한 컴퓨터 입장에서는 식을 해석하기 어렵다.

이를 해결하기 위해 어떤 방법을 취할 수 있는지 우선 확인해보자

2. 흐름

0) 사전 지식

우리가 평소에 사용하는 수식의 표기법은 ‘중위 표기법’이다.(infix) 중위표기법을 제외한 나머지 표기법에는 전위 표기법과 후위 표기법이 있는데, 이 두 표기법은 연산자의 우선순위를 학습하지 않아도 혼합연산을 계산할 수 있다는 장점을 갖고 있다.

1) Flow

그렇다면 계산기 프로그램을 어떻게 구현해야 할 지 구상해보자.

1. 우선 컴퓨터가 우선순위를 파악할 수 있도록 사용자가 중위표기법으로 입력한 식을 후위 표기법으로 바꿔주는 과정이 필요하다.
2. 다음으로는 후위 표기법으로 입력된 식을 계산하는 코드를 돌려서 결과값을 얻어야 한다.

결국 정리하면

1) 중위 → 후위

2) 후위 계산

이렇게 두 가지 단계로 나누어 구현하는 방향으로 생각할 수 있다. 각 단계에 맞추어 코드를 완성해보자.

3. 수식의 표기법

그렇다면 중위표기법을 후위 표기법으로 바꾸는 방법은 어떻게 생각해야 하는가?

1) 후위 표기법 -1(괄호x)

우선 간단하게 괄호가 없는 상황부터 해결해보자.

5 + 2 / 7

이런 식을 계산한다고 가정하자. 가장 먼저 준비할 것은 결과를 적을 수 있도록 처음 칸 수와 동일한 결과 창을 만드는 것이고, 하나의 ‘그릇’을 준비할 것이다. 이 그릇에는 우리가 앞에서 배웠던 스택의 원리가 적용될 것이다.

(1) 숫자

왼쪽부터 훑고 갈 때 숫자를 만났으면 그대로 적어주면 된다

(2) 문자

문자를 만난 경우 일단 그릇에 넣을 준비를 한다

그릇에 아무것도 없다면 그대로 쌓는다

(3) 문자 쌓기(우선순위 판정)

그릇에 이미 문자가 있는 경우

if → 그릇에 있는 연산자가 더 우선순위가 낮으면 → 우선순위 높은 연산자가 위로 갈 수 있도록 쌓는다

else → 내가 우선순위가 더 낮은 경우 → 그릇에 있는 건 결과칸으로 옮기고, 나를 그릇에 쌓는다

(4) Q1

우선순위가 동등한 연산자가 오는 경우는 어떻게 할까?

혼합 연산을 할 때도 연산자의 우선순위를 정하는 요소는 두 가지가 있다. 연산자의 종류와 위치.

따라서 앞에 있는 연산자가 우선순위를 갖고 있다고 생각할 수 있다. 결국 위의 이미지 같은 상황이 있다면 +는 결과 자리에 치우고, - 혼자 그릇 위에 올라가면 될 것이다.

(5) Q2

다음과 같이 연산자가 이미 쌓여있는 상태에서는 / 혼자 나가야 하는가 아니면 그 아래 있는 +까지 나가야 하는가?

앞에 있는 연산자가 우선순위가 높기 때문에 둘 다 나가야 한다.

2) 후위 표기법 -2 (괄호ㅇ)

참고로 후위 표기법의 결과에는 괄호가 포함되어 있지 않다. 괄호 또한 어떠한 ‘기능’이 있는 것이 아니라 단순히 우선순위를 표현하려고 한 것이기 때문에 후위표기법에서는 필요가 없다.

그래서 사실은 결과칸은 시작칸과 동일한 수의 칸을 만들지 않아도 된다. ()를 다시 안쓸 것이기 때문에 2칸 줄여서 작성해도 무방하다.

(1) ( 의 처리

(는 우선순위가 어떻게 될까? 후위 표기법으로 나타낼 때는 ‘가장 낮은 우선순위’를 갖는다고 가정하자. 따라서 이 위에 다른연산자들은 계속 쌓일 것이고, 만약 그릇에 있는 연산자들이 다 나가야 하는 상황이 발생할 때도 (는 나가지 않고 그대로 있어야 한다.

그러니까 바닥에 붙었다고 생각하고, 상관 없이 계속 계산하면 된다는 것이다.

(2) 나머지

(오른쪽에 있는 연산들은 그냥 그대로 실행했다. 숫자를 만나면 그대로 숫자를 쓰고, 문자들을 만나면 우선순위를 비교하여 쌓거나 내보내거나 하였다.

(3) ) 연산자

) 연산자는 그 어떤 연산자보다 우선순위가 낮다고 판단한다. ( ( 연산자 보다도)

그렇기 때문에 ) 가 등장하면 모두 다 나가야 하는 것이다

그리고 아까 후위 표기법 시작할 때 언급했던 것과 같이 (, ) 연산자는 표시하지 않을 것이다. 따라서 ( 와 ) 사이 있는 연산자들만 결과에 써주면 된다.

(4) 나머지

나머지는 지금까지 했던 규칙 그대로 작성하면 된다.

(5) Result

이렇게 적고나면 마무리가 된다. 그럼 이런 알고리즘을 구현하기 위해 코드를 작성해보자.

4. 알고리즘 적용 코드

지금부터는 앞에서 설명했던 원리를 적용하여 중위표기법 → 후위 표기법으로 바꾸는 코드를 작성해볼 것이다.

하나의 함수로 모든 것을 해결할 수 없으니 함수를 하나씩 확인해보자.

1) GetOpPrec, 우선순위

int GetOpPrec(char op) {
    switch (op) {
        case '*':
        case '/':
            return 5; 
        case '+':
        case '-':
            return 3; 
        case '(':
            return 1;
    }
    return -1;
}

우선순위를 확인하는 함수를 만들어보자

1. char op : parameter로 연산자를 보낼 것이다.
2. *, / : 가장 높은 우선순위
3. +, - : 그 다음 우선순위
4. ( : 가장 낮은 우선순위

Q. ) 는 왜 없냐

A. ) 넣으면 -1 나와서 가장 낮은 우선순위가 되기 때문이라고 난 생각했다. 하지만 이후에 적을 코드를 보면 애초에 )는 다른 케이스로 분류하기 때문에 저 함수에 넣을 일이 없다.

2) WhoPrecOp, 비교

int WhoPrecOp(char op1, char op2) {
    int op1Prec = GetOpPrec(op1);
    int op2Prec = GetOpPrec(op2);

    if (op1Prec > op2Prec)
        return 1;  // op1의 우선순위가 더 높다면
    else if (op1Prec < op2Prec)
        return -1; // op2의 우선순위가 더 높다면
    else
        return 0;  // op1과 op2의 우선순위가 같다면
}

1. return 1 : op1의 우선순위가 더 높은 경우
2. return -1 : op2의 우선순위가 더 높은 경우
3. return 0 : 우선 순위가 동일한 경우

3) ConvToRPNExp

void ConvToRPNExp(char exp[]) {
    Stack stack;
    int expLen = strlen(exp);
    char *convExp = (char *)malloc(expLen + 1); // result

    int i, idx = 0;
    char tok, popOp;

    memset(convExp, 0, sizeof(char) * expLen + 1); // reset
    StackInit(&stack);

    for (i = 0; i < expLen; i++) {
    .
    .
    .
    }

    while (!IsEmpty(&stack))
        convExp[idx++] = SPop(&stack);

    strcpy(exp, convExp); // 변환된 수식을 원본 배열로 복사
    free(convExp);        // 메모리 해제
}

1. stack : 그릇
2. convExp : 결과를 담을 stack
3. for 문은 우선 생략
4. while (!IsEmpty(&stack)) : 모든 과정이 마무리 된 이후, stack 에 연산자가 남아있다면 이를 convExp에 넣어주기

for 문을 구체적으로 확인해보자

  for (i = 0; i < expLen; i++) {
      tok = exp[i];

      if (isdigit(tok)) {
          convExp[idx++] = tok; 
      } else {
          switch (tok) {
              case '(':
                  SPush(&stack, tok);
                  break;
              case ')':
                  while (1) {
                      popOp = SPop(&stack);
                      if (popOp == '(')
                          break;
                      convExp[idx++] = popOp;
                  }
                  break;
              case '+': 
              case '-': 
              case '*': 
              case '/':
                  while (!IsEmpty(&stack) && WhoPrecOp(SPeek(&stack), tok) >= 0)
                      convExp[idx++] = SPop(&stack);
                  SPush(&stack, tok);
                  break;
          }
      }
  }

1. tok : 연산식을 하나씩 임시로 담는 변수

2. if (isdigit(tok)) : tok이 숫자인지 확인하여 맞다면 → 바로 결과에 저장 && index늘리기

3. else : 지금부터는 연산자인 경우에 대해서 다룰 것임

   1. case '(' : ( 가 나온 경우 일단 스택에 쌓기

   2. case ')' : ( 나올 때 까지 stack안에 있는 거 다 꺼내어 결과값에 저장

   3. case +-*/ : while…

      • !IsEmpty(&stack) : 스택에 무언가 있고

      • WhoPrecOp(SPeek(&stack), tok) >= 0 : 동시에 지금 확인하고 있는 놈(=tok)이 우선순위가 같거나 낮은 경우

        while문의 조건 = 접시에 있는 것들이 다 튀어나와야 하는 경우

   4. SPush(&stack, tok) : 접시에 있는 거 다 내보냈으니 이제 tok을 접시(=stack)에 올린다.

이 과정이 마무리 되면, 기존에 있던 배열 안에는 후위표기법으로 표기가 된 식이 위치해있을 것이다.