중위표기법을 후위표기법으로 바꿔서 계산하는 알고리즘

현실에선 사칙연산과 괄호가 포함된 수식을 중위 표기법으로 기술한다.

예를들어 3 + 4 와 같은 꼴이다.

하지만 3 + ( 4 - 7 ) * 8 + 3 * 4 와 같이 우선순위가 꼬여버린 수식은 컴퓨터가 알아먹기 힘들다.

하지만 수식계산은 연산 순서만 잘 정리되면 술술 풀린다.

목표는 숫자(피연산자)는 가만히 냅두고, 연산자들의 서열만 정리시켜주려는 것이다.

위 수식의 연산순서를 그래프로 나타내면 다음과 같다.

위 그래프를 중위순회하면 원래의 수식이 나온다. 위 그래프를 후위순회하면 후위표기법대로 기술된다.

3 4 7 - 8 * + 3 4 * +

우리가 보기엔 해괴한 수식이지만, 컴퓨터가 보기엔 앞에서 부터 계산만 하면 되는 편한 식이다.(괄호가 없다)

어떻게 계산 하냐면, 앞에서부터 보면서 연산자가 나오면 앞의 두 피연산자를 뽑아 연산하는 것이다. 다음과 같다.

1. - 때문에 4와 7을 뺀 -3을 기록한다.

2. * 때문에 (1)의 -3과 8을 곱한 -24를 기록한다.

3. + 때문에 (2)의 -24와 3을 더한 -21을 기록한다.

4. * 때문에 3과 4를 곱한 12를 기록한다.

5. + 때문에 (3)과 (4)의 -21과 12를 더한 -9를 기록한다.

6. 최종기록 -9가 결과다.

따라서 계산하는데 O(n) 걸린다.

따라서 중위식을 후위식으로 변환하는데 O(n)만 걸리면 아름다운 알고리즘이 될 것이다.

이제부터 중위식을 후위식으로 변환하는 과정을 설명하고자 한다.

하려는 짓은 결국엔 연산순서를 잘 일렬로 세워주는 것이다. 숫자는 앞에서 부터 잘 기억만 하면 된다.

아이디어는 다음의 생각들을 잘 섞으면 된다.

1. +와 -는 당연히 *와 /보다 나중에 계산해야 한다.

2. (는 수식안에 새로운 수식이 생기게 한다.

3. )는 그 새로운 수식을 닫는 역할을 한다.

4. 따라서 곱하기 > 더하기 > 괄호질로 연산 우선순위가 높다. ( 다음을 생각해보자. (1+2)*3 ) 

이제 이 아이디어로 중위식을 앞에서부터 보면서 후위식으로 바꿔보자

1. 현재 문자가 ( 라면 스택에 ( 를 넣어준다. 새로운 수식이 언제 시작되었는지 기억하기 위함이다.

2. 현재 문자가 ) 라면 수식이 끝난 것이다. 스택에 ( 가 보일 때 까지 파내면서 후위식에 기록한다. ( 는 버린다.

괄호질은 서열이 제일 낮기때문이다.

3. 현재 문자가 연산자라면, 서열을 정해야 한다. 스택에 나보다 쎈 연산자가 있다면 파내고 후위식에 기록한다.

나와 우선순위가 같은 연산자라면, 수식의 왼쪽이 우선순위가 더 높으므로 사실 나보다 쎈 연산자다. 파내고 기록해야한다.

4. 숫자라면 그냥 후위식에 기록한다.

숫자가 여러자리라면 고통스럽겠지만 역량에 맡긴다. 코드를 보면서 이해해보자.

#include "calc.h"
#include <stack>
using namespace std;
 
int order[256];
char post[202];
 
int stoi(char* from, char* to) {
    int ans = 0;
    int t = 1;
    while (1) {
        ans += (*to - '0') * t;
        t *= 10;
 
        if (from == to)
            break;
        else
            to--;
    }
    return ans;
}
 
int calc(char str[])
{
    order['('] = order[')'] = 0;
    order['+'] = order['-'] = 1;
    order['*'] = order['/'] = 2;
 
    char* infix = str;
    char* postfix = post;
 
    stack<char> st;
    while (*infix) {
        if (*infix == '(') {
            st.push('(');
            infix++;
        }
        else if (*infix == ')') {
            while (st.top() != '(') {
                *postfix++ = st.top();
                *postfix++ = ' ';
                st.pop();
            }
            st.pop();
            infix++;
        }
        else if (*infix == '+' || *infix == '-' || *infix == '*' || *infix == '/') {
            while (!st.empty() && order[*infix] <= order[st.top()]) {
                *postfix++ = st.top();
                *postfix++ = ' ';
                st.pop();
            }
            st.push(*infix++);
        }
        else if ('0' <= *infix && *infix <= '9') {
            do {
                *postfix++ = *infix++;
            } while ('0' <= *infix && *infix <= '9');
            *postfix++ = ' ';
        }
    }
 
    while (!st.empty()) {
        *postfix++ = st.top();
        *postfix++ = ' ';
        st.pop();
    }
    --postfix;
    *postfix = '\0';
    //중위표기법 -> 후위표기법
 
    stack<int> ans;
    postfix = post;
    char* from = post;
    char* to = post;
    bool started = false;
 
    while (*postfix) {
        if (*postfix == '+') {
            int a = ans.top(); ans.pop();
            int b = ans.top(); ans.pop();
            ans.push(a + b);
            started = false;
        }
        else if (*postfix == '-') {
            int a = ans.top(); ans.pop();
            int b = ans.top(); ans.pop();
            ans.push(b - a);
            started = false;
        }
        else if (*postfix == '*') {
            int a = ans.top(); ans.pop();
            int b = ans.top(); ans.pop();
            ans.push(a * b);
            started = false;
        }
        else if (*postfix == ' ') {
            if (started) {
                ans.push(stoi(from, to));
                started = false;
            }
        }
        else {
            if (!started) {
                from = to = postfix;
                started = true;
            }
            else
                to = postfix;
        }
        postfix++;
    }
    //후위표기법 계산
 
    return ans.top();
}

calc 함수는 문자열을 받아 계산결과를 리턴해준다.