N Log

스택으로 수식 변환과 계산

수식 계산과 표기법

계산기는 연산자 우선순위와 괄호를 고려해 수식을 올바른 순서로 계산해야 한다.
수식을 읽어나가는 도중에는 계산 순서가 확정될 때까지 보류하는 연산자와 괄호, 그리고 계산 중간값을 잠시 보관할 공간이 필요하다.
스택은 가장 나중에 넣은 원소를 먼저 꺼내므로, 이러한 정보를 관리하며 수식을 계산하기에 알맞다.

수식은 연산자와 피연산자를 배치하는 방식에 따라 중위, 전위, 후위 표기법으로 나타낼 수 있다.
세 표기법은 같은 수식을 서로 다른 형태로 표현하며, 계산 순서를 드러내는 방식도 다르다.
이 글에서는 스택을 활용해 중위 표기식을 후위 표기식으로 변환한 뒤 계산하는 방법을 알아본다.

중위 표기법 (Infix Notation)

2 + 3 * 4

일상적으로 가장 익숙한 표기법으로, 연산자가 두 피연산자 사이에 놓인다.
2 + 3 * 4라는 식 자체에는 계산 순서가 명시되어 있지 않다.
우리는 *가 +보다 먼저 계산된다는 연산자 우선순위 규칙을 이 수식에 적용해 2 + (3 * 4)로 해석한다.
기본 우선순위와 다른 순서로 계산하려면 소괄호로 순서를 명시한다.

전위 표기법 (Prefix Notation)

+ 2 * 3 4

연산자가 피연산자보다 앞에 놓이는 표기법이다.
연산자의 위치만으로 계산 순서가 정해지므로, 연산자 우선순위를 따지거나 소괄호를 사용할 필요가 없다.

위 수식은 다음 순서로 해석한다.

  1. 첫 번째 토큰인 +는 뒤따르는 두 항을 더한다는 뜻이다.
  2. 첫 번째 항은 2다.
  3. 두 번째 항인 * 3 4는 3 * 4를 뜻한다.
  4. 따라서 전체 수식은 2 + (3 * 4)가 되며, 계산 결과는 14다.

문제에서 예시로 제시한 식을 변환한 결과는 다음과 같다.

중위 표기식 전위 표기식 결과
2 + 3 * 4 + 2 * 3 4 14
(2 + 3) * 4 * + 2 3 4 20
8 / 2 * 3 * / 8 2 3 12
2 + 3 * 4 - 5 - + 2 * 3 4 5 9
10 + 2 * 3 + 10 * 2 3 16

후위 표기법 (Postfix Notation)

2 3 4 * +

연산자가 피연산자 뒤에 놓이는 표기법이다.
연산자의 위치만으로 계산 순서가 정해지므로, 연산자 우선순위나 소괄호가 필요 없다.

위 수식은 다음 순서로 해석한다.

  1. 왼쪽부터 읽으면 2, 3, 4가 차례로 피연산자로 나온다.
  2. *를 만나면 바로 앞의 두 피연산자인 3과 4를 계산해 12로 바꾼다.
  3. 남은 수식은 2 12 +가 된다.
  4. 마지막 +는 2와 12를 더하라는 뜻이므로, 계산 결과는 14다.

중위 표기식을 후위 표기식으로 변환하면 다음과 같다.

중위 표기식 후위 표기식 결과
2 + 3 * 4 2 3 4 * + 14
(2 + 3) * 4 2 3 + 4 * 20
8 / 2 * 3 8 2 / 3 * 12
2 + 3 * 4 - 5 2 3 4 * + 5 - 9
10 + 2 * 3 10 2 3 * + 16

소스 코드

#include <cassert>
#include <iostream>
#include <stack>
#include <string>

using namespace std;

int evaluate_postfix_expression(const string& postfix_expression)
{
    stack<int> values;

    for (size_t i = 0; i < postfix_expression.length();)
    {
        char ch = postfix_expression[i];

        if (ch == ' ')
        {
            ++i;
            continue;
        }

        if (ch >= '0' && ch <= '9')
        {
            int value = 0;

            while (i < postfix_expression.length() &&
                   postfix_expression[i] >= '0' && postfix_expression[i] <= '9')
            {
                value = value * 10 + (postfix_expression[i] - '0');
                ++i;
            }

            values.push(value);
            continue;
        }

        int right = values.top();
        values.pop();

        int left = values.top();
        values.pop();

        switch (ch)
        {
        case '+':
            values.push(left + right);
            break;
        case '-':
            values.push(left - right);
            break;
        case '*':
            values.push(left * right);
            break;
        case '/':
            values.push(left / right);
            break;
        default:
            cerr << "Unsupported operator: " << ch << '\n';
            assert(false);
            break;
        }

        ++i;
    }

    return values.top();
}

int get_precedence(char op)
{
    switch (op)
    {
    case '*':
    case '/':
        return 3;

    case '+':
    case '-':
        return 2;

    case '(':
        return 1;
    }

    return -1;
}

string infix_to_postfix(const string& infix_expression)
{
    string result;
    stack<char> operators;

    for (size_t i = 0; i < infix_expression.length();)
    {
        char ch = infix_expression[i];

        if (ch == ' ')
        {
            ++i;
            continue;
        }

        if (ch == '(')
        {
            operators.push(ch);
            ++i;
            continue;
        }

        if (ch == ')')
        {
            while (operators.top() != '(')
            {
                result += operators.top();
                result += ' ';
                operators.pop();
            }

            operators.pop();
            ++i;
            continue;
        }

        if (ch >= '0' && ch <= '9')
        {
            while (i < infix_expression.length() &&
                   infix_expression[i] >= '0' && infix_expression[i] <= '9')
            {
                result += infix_expression[i];
                ++i;
            }

            result += ' ';
            continue;
        }

        while (!operators.empty() &&
               get_precedence(operators.top()) >= get_precedence(ch))
        {
            result += operators.top();
            result += ' ';
            operators.pop();
        }

        operators.push(ch);
        ++i;
    }

    while (!operators.empty())
    {
        result += operators.top();
        result += ' ';
        operators.pop();
    }

    return result;
}

int main()
{
    string infix_expression = "2 + 3 * 4";
    string postfix_expression = infix_to_postfix(infix_expression);

    cout << "Infix: " << infix_expression << '\n';
    cout << "Postfix: " << postfix_expression << '\n';
    cout << "Result: " << evaluate_postfix_expression(postfix_expression) << '\n';

    return 0;
}

구현 설명

중위 표기식을 후위 표기식으로 변환

infix_to_postfix() 함수는 중위 표기식의 문자를 왼쪽부터 하나씩 읽어 후위 표기식으로 변환한다.
숫자를 읽으면 결과 문자열에 바로 추가하고, 연산자를 읽으면 우선순위를 정하기 위해 스택을 사용한다.
스택의 맨 위에 이미 들어 있는 연산자가 새 연산자보다 우선순위가 높거나 같으면, 스택에 있던 연산자를 결과 문자열에 추가한 뒤 새 연산자를 스택에 넣는다.
왼쪽 괄호는 스택에 넣고, 오른쪽 괄호를 읽으면 왼쪽 괄호를 만날 때까지 연산자를 꺼내 결과 문자열에 추가한다.

중위 표기식 2 * (3 + 4) - 5를 후위 표기식으로 변환해 보자.

읽은 문자 연산자 스택 결과 문자열 처리
2 없음 2 피연산자는 결과 문자열에 바로 추가한다.
* * 2 스택이 비어 있으므로 *를 넣는다.
( *, ( 2 괄호 안에서 처리할 연산자의 시작을 표시하기 위해 (를 넣는다.
3 *, ( 2 3 피연산자는 결과 문자열에 바로 추가한다.
+ *, (, + 2 3 +는 (보다 우선순위가 높으므로 스택에 넣는다.
4 *, (, + 2 3 4 피연산자는 결과 문자열에 바로 추가한다.
) * 2 3 4 + (를 만날 때까지 연산자를 꺼내 결과 문자열에 추가한다.
- - 2 3 4 + * 스택의 *가 -보다 우선순위가 높으므로 *를 꺼내 결과에 추가한 뒤 -를 스택에 넣는다.
5 - 2 3 4 + * 5 피연산자는 결과 문자열에 바로 추가한다.
입력 종료 없음 2 3 4 + * 5 - 스택에 남은 -를 꺼내 추가한다.

후위 표기식 계산하기

evaluate_postfix_expression() 함수는 후위 표기식의 문자를 왼쪽부터 읽고 스택을 활용해 계산한다.
문자 숫자를 읽으면 정수로 만들어 스택에 넣고, 연산자를 읽으면 스택의 맨 위에서 값 두 개를 꺼내 연산한 결과를 다시 넣는다.

후위 표기식 2 3 4 + * 5 -를 계산하는 과정은 다음과 같다.

읽은 토큰 값 스택 처리
2 2 2를 스택에 넣는다.
3 2, 3 3을 스택에 넣는다.
4 2, 3, 4 4를 스택에 넣는다.
+ 2, 7 4와 3을 꺼내 3 + 4를 계산한 결과 7을 넣는다.
* 14 7과 2를 꺼내 2 * 7을 계산한 결과 14를 넣는다.
5 14, 5 5를 스택에 넣는다.
- 9 5와 14를 꺼내 14 - 5를 계산한 결과 9를 넣는다.

모든 문자를 처리한 뒤 스택에 남은 하나의 값이 수식의 계산 결과다.