[Data Structure] 스택을 사용한 후위 표기법 변환 및 계산

후위 표기법

우리가 평소에 쓰는 수식 표기법은 중위 표기법(infix notation)이다. 하지만 연산자에는 우선순위가 있기 때문에 컴퓨터에서는 이를 후위 표기법(postfix notation)으로 변환해 매우 쉽게 수식을 계산할 수 있다.

 

후위 표기법은 연산자가 피연산자들 뒤에 온다.

• 중위 표기법: A/B-C + D*E - A*C
• 후위 표기법: AB/C-DE*AC*-

후위 표기법은 다음과 같은 이유로 계산을 쉽게 만든다.

• 괄호의 필요성이 없어짐
• 연산자 우선순위의 의미가 없어짐
  • infix에서 postfix로 변환하면서 연산자 계산 순서까지 순서대로 들어오기 때문에 계산 과정에서는 단순히 왼쪽부터 쭉 읽어나가면 된다.

중위 표현법 -> 후위 표현법 변환

• 해당 변환 과정에서 연산자를 저장하는 스택이 중요하게 사용된다.
  • 연산자 우선순위가 높은 순서부터 사용될 수 있게 함
  • 우선순위가 높은 연산자가 뒤에 나오더라도 순서를 바꿀 수 있게 함
• 이 과정에는 infix로 표현된 수식과 postfix로 변환한 결과를 내보낼 공간이 필요하다.
  • 해당 글에서는 큐를 사용한다. 변환한 결과를 내보낼 큐를 output이라 하자.
• Prec 함수는 연산자의 우선 순위를 리턴한다. 숫자가 높을수록 우선순위가 높다. 
  • 각 연산자의 우선순위는 곱셈/나눗셈 > 덧셈/뺄셈 > 괄호로 둔다.

변환 과정

1. 피연산자는 바로 output에 집어넣는다.
2. 연산자인 경우 연산자 스택에 집어넣는다. 이때, 다른 연산자가 이미 스택에 있는 경우 두 연산자의 우선순위를 비교한다.
   
   • 현재 연산자가 스택 맨 위에 있는 연산자보다 우선순위가 높을 경우 연산자 스택에 바로 집어넣는다.
   • 현재 연산자가 스택 맨 위에 있는 연산자보다 우선순위가 낮을 경우 자신보다 우선순위가 높은 연산자들을 모두 output으로 보낸 후, 자신을 연산자 스택에 집어넣는다.
3. 만약 괄호인 경우
   • 여는 괄호가 나오면 연산자 스택에 집어 넣는다.
   • 닫는 괄호가 나오면 연산자 스택에서 여는 괄호가 나오기 전까지 하나씩 꺼내 output에 집어 넣은 후 여는 괄호를 꺼내 없앤다. 
4. 더 이상 남은 식이 없다면 연산자 스택에 남아있는 연산자들을 모두 output에 집어넣는다.

// 숫자가 높을수록 우선순위가 높음
int Prec(char c)
{
    if (c == '+' || c == '-')
        return 1;
    else if (c == '*' || c == '/')
        return 2;
    else
        return -1; // 괄호는 우선순위가 아주 낮은 것으로 생각
}

void InfixToPostfix(queue<char>& q, queue<char>& output)
{
    stack<char> s; // 연산자 담아둘 스택

    while (!q.empty())
    {
        char c = q.front();
        q.pop();

        if (c == '+' || c == '-' || c == '*' || c == '/') // 연산자인 경우
        {
            while (!s.empty() && Prec(s.top()) > Prec(c)) // 스택에 있는 연산자의 우선순위가 낮거나 같은 동안
            {
                cout << s.top();
                output.push(s.top()); // 스택에 있는 연산자를 output으로 보냄
                s.pop();
            }
            s.push(c); // 우선순위 높은 연산자들 모두 output으로 보냈으면 자신이 들어감
        }
        else if (c == '(') // 여는 괄호인 경우
            s.push(c);
        else if (c == ')') // 닫는 괄호인 경우
        {
            while (s.top() != '(') // 여는 괄호가 나올 때까지 스택에 있는 모든 연산자를 output으로 보냄
            {
                cout << s.top();
                output.push(s.top());
                s.pop();
            }
            s.pop(); // 여는 괄호 제거
        }
        else // 피연산자인 경우
        {
            cout << c;
            output.push(c);
        }
    }

    // 스택에 남아있는 연산자 모두 output으로 옮김
    while (!s.empty())
    {
        cout << s.top();
        output.push(s.top());
        s.pop();
    }
}

Infix: 1+2*3
Postfix: 123*+

후위 표현법 계산

• 후위 표기법의 계산에는 결과 스택이 사용된다.

계산 과정

1. infix 큐에서 값을 하나씩 꺼낸다.
2. 피연산자인 경우 결과 스택에 바로 집어 넣는다.
3. 연산자인 경우, 결과 스택의 위에서 두 수를 꺼낸 후 연산자에 맞게 계산해 다시 집어넣는다.
4. 들어올게 더 이상 없다면 스택에 남은 하나의 값이 계산 결과

int EvalPostfix(queue<char>& q)
{
    stack<char> result; // 결과값 저장할 스택

    while (!q.empty())
    {
        char ch = q.front();
        q.pop();

        if (ch == '+' || ch == '-' || ch == '*' || ch == '/') // 연산자인 경우
        {
            // 스택에서 피연산자 두 개 꺼냄
            int right = result.top() - 48;
            result.pop();
            int left = result.top() - 48;
            result.pop();

            // 계산 결과를 다시 스택에 저장
            switch (ch)
            {
                case '+':
                    result.push(char(left + right) + 48);
                    break;
                case '-':
                    result.push(char(left - right) + 48);
                    break;
                case '*':
                    result.push(char(left * right) + 48);
                    break;
                case '/':
                    result.push(char(left / right) + 48);
                    break;
            }
        }
        else // 피연산자인 경우 바로 결과에 저장
        {
            result.push(ch);
        }
    }

    return result.top() - 48; // 마지막에 스택에 남아있는 수가 결과
}

Infix: 1+(1*2*3)*4
Postfix: 1123**4*+
Calc: 25

전체 코드

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

// 숫자가 높을 수록 우선순위가 높음
int Prec(char c)
{
    if (c == '+' || c == '-')
        return 1;
    else if (c == '*' || c == '/')
        return 2;
    else
        return -1; // 괄호는 우선순위가 아주 낮은 것으로 생각
}

void InfixToPostfix(queue<char>& q, queue<char>& output)
{
    stack<char> s; // 연산자 담아둘 스택

    while (!q.empty())
    {
        char c = q.front();
        q.pop();

        if (c == '+' || c == '-' || c == '*' || c == '/') // 연산자인 경우
        {
            while (!s.empty() && Prec(s.top()) > Prec(c)) // 스택에 있는 연산자의 우선순위가 낮거나 같은 동안
            {
                cout << s.top();
                output.push(s.top()); // 스택에 있는 연산자를 output으로 보냄
                s.pop();
            }
            s.push(c); // 우선순위 높은 연산자들 모두 output으로 보냈으면 자신이 들어감
        }
        else if (c == '(') // 여는 괄호인 경우
            s.push(c);
        else if (c == ')') // 닫는 괄호인 경우
        {
            while (s.top() != '(') // 여는 괄호가 나올 때까지 스택에 있는 모든 연산자를 output으로 보냄
            {
                cout << s.top();
                output.push(s.top());
                s.pop();
            }
            s.pop(); // 여는 괄호 제거
        }
        else // 피연산자인 경우
        {
            cout << c;
            output.push(c);
        }
    }

    // 스택에 남아있는 연산자 모두 output으로 옮김
    while (!s.empty())
    {
        cout << s.top();
        output.push(s.top());
        s.pop();
    }
}

int EvalPostfix(queue<char>& q)
{
    stack<char> result; // 결과값 저장할 스택

    while (!q.empty())
    {
        char ch = q.front();
        q.pop();

        if (ch == '+' || ch == '-' || ch == '*' || ch == '/') // 연산자인 경우
        {
            // 스택에서 피연산자 두 개 꺼냄
            int right = result.top() - 48;
            result.pop();
            int left = result.top() - 48;
            result.pop();

            // 계산 결과를 다시 스택에 저장
            switch (ch)
            {
                case '+':
                    result.push(char(left + right) + 48);
                    break;
                case '-':
                    result.push(char(left - right) + 48);
                    break;
                case '*':
                    result.push(char(left * right) + 48);
                    break;
                case '/':
                    result.push(char(left / right) + 48);
                    break;
            }
        }
        else // 피연산자인 경우 바로 결과에 저장
        {
            result.push(ch);
        }
    }

    return result.top() - 48; // 마지막에 스택에 남아있는 수가 결과
}

int main()
{
    // 빈칸 없이 한 자리 숫자만 가능
    //const char infix[] = "1+2*3";
    const char infix[] = "1+(1*2*3)*4";
    const int size = sizeof(infix) / sizeof(char) - 1;

    // 큐에 모두 넣기
    queue<char> q;
    for (int i = 0; i < size; i++)
        q.push(infix[i]);

    queue<char> postfix;

    cout << "Infix: " << infix << "\n";
    cout << "Postfix: ";
    InfixToPostfix(q, postfix);
    cout << "\n";
    cout << "Calc: " << EvalPostfix(postfix);
}