3.9 Инфиксный вывод

Пожалуй, основным моментом обработки арифметических выражений является печать их с минимальным количеством скобок. Это как правило довольно сложновато и зависит от того, кто несёт ответственность за эмиссию скобок. В дополнение к имени оператора, используемого для постфиксного вывода, мы добавляем в struct Type два числа:

struct Type {

    const char * name;    /* имя узла */

    char rank, rpar;

    void * (* new) (va_list ap);

    void (* exec) (const void * tree, int rank, int par);

    void (* delete) (void * tree);

};

.rank (rank - ранг) это приоритет оператора, начиная с 1 для сложения. .rpar (parentheses - скобки) устанавливается для таких операторов, как вычитание, которые требуют от своего правого операнда быть заключённым в скобки, если он использует оператор равного приоритета. В качестве примера рассмотрим

$ infix

1 + (2 - 3)

    1 + 2 - 3

1 - (2 - 3)

    1 - (2 - 3)

Это демонстрирует, что мы имеем следующую инициализацию:

static struct Type _Add = {"+", 1, 0, mkBin, doBin, freeBin};

static struct Type _Sub = {"-", 1, 1, mkBin, doBin, freeBin};

Сложной частью для бинарного узла является решение, должен ли он окружить себя скобками. Бинарному узлу, например, сложению, даётся приоритет содержащего его узла и флаг, указывающий, нужны ли скобки в случае равного приоритета. Будут ли использоваться скобки решает doBin():

static void doBin (const void * tree, int rank, int par) {

    const struct Type * type = * (struct Type **) tree;

    par = type -> rank < rank

            || (par && type -> rank == rank);

    if (par) putchar(’(’);

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

    exec(((struct Bin *) tree) -> left, type -> rank, 0);

    printf(" %s ", type -> name);

    exec(((struct Bin *) tree) -> right,

            type -> rank, type -> rpar);

    if (par) putchar(’)’);

}

Остальные процедуры печати написать значительно проще.