Алгоритм сортировочной станции

Алгоритм сортировочной станции — способ разбора математических выражений, представленных в инфиксной нотации. Может быть использован для получения вывода в виде обратной польской нотации или в виде абстрактного синтаксического дерева. Алгоритм изобретен Эдсгером Дейкстрой и назван им «алгоритм сортировочной станции», поскольку напоминает действие железнодорожной сортировочной станции.

Так же, как и вычисление значений выражений в обратной польской записи, алгоритм работает при помощи стека. Инфиксная запись математических выражений чаще всего используется людьми, ее примеры: 2+4 и 3+6*(3-2). Для преобразования в обратную польскую нотацию используется 2 строки: входная и выходная, и стек для хранения операторов, еще не добавленных в выходную очередь. При преобразовании алгоритм считывает 1 символ и производит действия, зависящие от данного символа.

Алгоритм

• Пока не все токены обработаны:

• Прочитать токен.
• Если токен — число, то добавить его в очередь вывода.
• Если токен — функция, то поместить его в стек.
• Если токен — разделитель аргументов функции (например запятая):

• Пока токен на вершине стека не открывающая скобка, перекладывать операторы из стека в выходную очередь. Если в стеке не было открывающей скобки, то в выражении пропущен разделитель аргументов функции (запятая), либо пропущена открывающая скобка.

• Если токен — оператор op1, то:

• Пока присутствует на вершине стека токен оператор op2, и

Либо оператор op1 лево-ассоциативен и его приоритет меньше чем у оператора op2 либо равен,

или оператор op1 право-ассоциативен и его приоритет меньше чем у op2,

переложить op2 из стека в выходную очередь;

• положить op1 в стек.

• Если токен — открывающая скобка, то положить его в стек.
• Если токен — закрывающая скобка:

• Пока токен на вершине стека не является открывающей скобкой, перекладывать операторы из стека в выходную очередь.
• Выкинуть открывающую скобку из стека, но не добавлять в очередь вывода.
• Если токен на вершине стека — функция, добавить ее в выходную очередь.
• Если стек закончился до того, как был встречен токен открывающая скобка, то в выражении пропущена скобка.

• Если больше не осталось токенов на входе:

• Пока есть токены операторы в стеке:

• Если токен оператор на вершине стека — открывающая скобка, то в выражении присутствует незакрытая скобка.
• Переложить оператор из стека в выходную очередь.

• Конец.

Каждый токен-число, функция или оператор выводится только один раз, а также каждый токен-функция, оператор или круглая скобка будет добавлен и удален из стека по одному разу. Постоянное количество операций на токен, линейная cложность алгоритма O(n).

Пример реализации на C++

#include <string.h>
#include <stdio.h>
 
// Операторы
// Приоритет Оператор Ассоциативность
// 1 ! правая
// 2 * / % левая
// 3 + - левая
// 4 = левая
int op_preced(const char c)
{
    switch(c)
    {
        case '!':
        return 4;
 
        case '*':
        case '/':
        case '%':
        return 3;
 
        case '+':
        case '-':
        return 2;
 
        case '=':
        return 1;
    }
    return 0;
}
 
bool op_left_assoc(const char c)
{
    switch(c)
    {
        // лево-ассоциативные операторы
        case '*':
        case '/':
        case '%':
        case '+':
        case '-':
        case '=':
        return true;
        // право-ассоциативные операторы
        case '!':
        return false;
    }
    return false;
}
 
unsigned int op_arg_count(const char c)
{
    switch(c)
    {
        case '*':
        case '/':
        case '%':
        case '+':
        case '-':
        case '=':
        return 2;
        case '!':
        return 1;
 
        default:
        return c - 'A';
    }
        return 0;
}
 
#define is_operator(c) (c == '+' || c == '-' || c == '/' || c == '*' || c == '!' || c == '%' || c == '=')
#define is_function(c) (c >= 'A' && c <= 'Z')
#define is_ident(c) ((c >= '0' && c <= '9') || (c >= 'a' && c <= 'z'))
 
bool shunting_yard(const char *input, char *output)
{
    const char *strpos = input, *strend = input + strlen(input);
    char c, stack[32], sc, *outpos = output;
    unsigned int sl = 0;
    while(strpos < strend)
    {
        c = *strpos;
        if(c != ' ')
        {
            // Если токен является числом (идентификатором), то добавить его в очередь вывода.
            if(is_ident(c))
            {
                *outpos = c; ++outpos;
            }
            // Если токен - функция, то положить его в стек.
            else if(is_function(c))
            {
                stack[sl] = c;
                ++sl;
            }
            //Если токен - разделитель аргументов функции (запятая):
            else if(c == ',')
            {
                bool pe = false;
                while(sl > 0)
                {
                    sc = stack[sl - 1];
                    if(sc == '(')
                    {
                        pe = true;
                        break;
                    }
                    else
                    {
                        // Пока на вершине не левая круглая скобка,
                        // перекладывать операторы из стека в очередь вывода.
                        *outpos = sc; ++outpos;
                        sl--;
                    }
                }
                // Если не была достигнута левая круглая скобка, либо разделитель не в том месте
                // либо была пропущена скобка
                if(!pe)
                {
                    printf("Error: separator or parentheses mismatched\n");
                    return false;
                }
            }
            // Если токен оператор op1, то:
            else if(is_operator(c))
            {
                while(sl > 0)
                {
                    sc = stack[sl - 1];
                    // Пока на вершине стека присутствует токен оператор op2,
                    // а также оператор op1 лево-ассоциативный и его приоритет меньше или такой же чем у оператора op2,
                    // или оператор op1 право-ассоциативный и его приоритет меньше чем у оператора op2
                    if(is_operator(sc) &&
                        ((op_left_assoc(c) && (op_preced(c) <= op_preced(sc))) ||
                           (!op_left_assoc(c) && (op_preced(c) < op_preced(sc)))))
                    {
                        // Переложить оператор op2 из стека в очередь вывода.
                        *outpos = sc; ++outpos;
                        sl--;
                    }
                    else
                    {
                        break;
                    }
                }
                // положить в стек оператор op1
                stack[sl] = c;
                ++sl;
            }
            // Если токен - левая круглая скобка, то положить его в стек.
            else if(c == '(')
            {
                stack[sl] = c;
                ++sl;
            }
            // Если токен - правая круглая скобка:
            else if(c == ')')
            {
                bool pe = false;
                // До появления на вершине стека токена "левая круглая скобка"
                // перекладывать операторы из стека в очередь вывода.
                while(sl > 0)
                {
                    sc = stack[sl - 1];
                    if(sc == '(')
                    {
                        pe = true;
                        break;
                    }
                    else
                    {
                        *outpos = sc; ++outpos;
                        sl--;
                    }
                }
                // Если стек кончится до нахождения токена левая круглая скобка, то была пропущена скобка.
                if(!pe)
                {
                    printf("Error: parentheses mismatched\n");
                    return false;
                }
                // выкидываем токен "левая круглая скобка" из стека (не добавляем в очередь вывода).
                sl--;
                // Если на вершине стека токен - функция, положить его в стек.
                if(sl > 0)
                {
                    sc = stack[sl - 1];
                    if(is_function(sc))
                    {
                        *outpos = sc; ++outpos;
                        sl--;
                    }
                }
            }
            else
            {
                printf("Unknown token %c\n", c);
                return false; // Unknown token
            }
        }
        ++strpos;
    }
    // Когда не осталось токенов на входе:
    // Если в стеке остались токены:
    while(sl > 0)
    {
        sc = stack[sl - 1];
        if(sc == '(' || sc == ')')
        {
            printf("Error: parentheses mismatched\n");
            return false;
        }
        *outpos = sc; ++outpos;
        --sl;
    }
 
    *outpos = 0; // Добавляем завершающий ноль к строке
    return true;
}
 
bool execution_order(const char *input)
{
    printf("order: (arguments in reverse order)\n");
    const char *strpos = input, *strend = input + strlen(input);
    char c, res[4];
    unsigned int sl = 0, sc, stack[32], rn = 0;
        // Пока на входе остались токены
    while(strpos < strend)
    {
                // Прочитать следующий токен
        c = *strpos;
                // Если токен - значение или идентификатор
        if(is_ident(c))
        {
                // Поместить его в стек
            stack[sl] = c;
            ++sl;
        }
                // В противном случае, токен - оператор (здесь под оператором понимается как оператор, так и название функции)
        else if(is_operator(c) || is_function(c))
        {
                        sprintf(res, "_%02d", rn);
                        printf("%s = ", res);
                        ++rn;
                        // Априори известно, что оператор принимает n аргументов
                        unsigned int nargs = op_arg_count(c);
                        // Если в стеке значений меньше, чем n
                        if(sl < nargs)
                        {
                                // (ошибка) Недостаточное количество аргументов в выражении.
                                return false;
                        }
                        // В противном случае, взять последние n аргументов из стека
                        // Вычислить оператор, взяв эти значения в качестве аргументов
                        if(is_function(c))
                        {
                                printf("%c(", c);
                                while(nargs > 0)
                                {
                                        sc = stack[sl - 1];
                                        sl--;
                                        if(nargs > 1)
                                        {
                                                printf("%s, ", &sc);
                                        }
                                        else
                                        {
                                                printf("%s)\n", &sc);
                                        }
                                        --nargs;
                                }
                        }
                        else
                        {
                                if(nargs == 1)
                                {
                                        sc = stack[sl - 1];
                                        sl--;
                                        printf("%c %s;\n", c, &sc);
                                }
                                else
                                {
                                        sc = stack[sl - 1];
                                        sl--;
                                        printf("%s %c ", &sc, c);
                                        sc = stack[sl - 1];
                                        sl--;
                                        printf("%s;\n",&sc);
                                }
                        }
                        // Если получены результирующие значения, поместить таковые в стек.
            stack[sl] = *(unsigned int*)res;
            ++sl;
        }
        ++strpos;
    }
        // Если в стеке осталось лишь одно значение,
        // оно будет являться результатом вычислений.
        if(sl == 1)
        {
                sc = stack[sl - 1];
                sl--;
                printf("%s is a result\n", &sc);
                return true;
        }
        // Если в стеке большее количество значений,
        // (ошибка) Пользователь ввёл слишком много значений.
        return false;
}
 
int main()
{
    // Имена функций: A() B(a) C(a, b), D(a, b, c) ...
    // идентификаторы: 0 1 2 3 ... and a b c d e ...
    // операторы: = - + / * % !
    const char *input = "a = D(f - b * c + d, !e, g)";
    char output[128];
    printf("input: %s\n", input);
    if(shunting_yard(input, output))
    {
        printf("output: %s\n", output);
        execution_order(output);
    }
    return 0;
}

Ссылки

• Java апплет демонстрирующий работу алгоритма
• Parsing Expressions by Recursive Descent Theodore Norvell © 1999—2001. Access date September 14, 2006.
• Алгоритм преобразования инфиксной записи в обратную польскую нотацию
• Оригинальное описание алгоритма
• Расширение алгоритма для использования произвольного количества аргументов функции
• Описание простейшей реализации, реализации унарных операторов и правоассоциативности
• Описание и реализация на C++
• Библиотека, реализующая алгоритм, на Java