.: [предыдущая | оглавление | следующая] :.

16.5 Алгоритм раскрытия скобок

Раскрытие скобок необходимо для приведения арифметического выражения к каноническому виду. Раскрытие скобок производится только для аддитивных составляющих (в том случае, когда для некоторого узла <T> имеется единственный <D> c сыновьями "(", <E>, ")") (алгоритм Expation). Для приведения к такому случаю для мультипликативных составляющих производится операция внесения в скобки. Здесь рассматриваются три случая:
       1)внесение в скобки для умножения (случай <D>*<D>) (алгоритм MImport);
       2)внесение в скобки для деления (случай <D>/<D>) (алгоритм D1Impоrt);
       3)внесение в скобки для деления (случай /<D>/<D>) (алгоритм D2Import). 
       Перед рассмотрением данных алгоритмов необходимо сделать замечание, что работа их рассматривается при упорядоченном синтаксическом дереве. выражения в скобках становятся самыми левыми сыновьями для узлов <T>.
       Алгоритм MImport производит внесение в скобки следующим образом:
       1)проверяется в синтаксическом дереве наличие <D>, у которых имеются скобки и следующий символ операции является умножением;
        2)если ДА, то поддерево следующего узла <D> со знаком "умножить" становится самым правым сыном всех узлов <T> рассматриваемого узла <E>, заключенного в скобках.
       3)соседний узел <D> и знак "умножить" удаляются.
       Данный алгоритм рекурсивно применяется для всех узлов рассматриваемого синтаксического дерева.
       Алгоритм D1Import аналогичен алгоритму Mimport, только вместо умноже- ния ставится знак деления. Алгоритм D2Import аналогичен MImport за исключением следующего:
       1)производит дополнительную проверку знака операции перед выражением в скобках;
       2)при внесении соответствующего <D> знак деления заменяется на знак умножения. Например:

a/(x + y)/b = > a/(x * b + y * b).

       Алгоритм Expantion производит раскрытие скобок следующим образом:
       1)осуществляется проверка, когда у некоторого <T> имеется единственный сын <D>, который имеет сыновей "(", <E>, ")";
        2)если ДА, то все поддеревья сыновей <Т> скобочного узла <E> становятся справа от рассматриваемого сына <T>, при этом переставляются соответствующие знаки (+ или -);
        3)производится удаление узлов <T>, <D>, "(", <E> и ")" из синтаксиче- ского дерева. Ниже показан пример преобразования синтаксического дерева при раскрытии скобок для выражения (a+b)*c.
        4)шаги 1-3 рекурсивно производятся для всех узлов <T> синтаксического дерева.
        Пример работы алгоритма по внесению и раскрытию показан на рис.15.3.

 
.: [предыдущая | оглавление | следующая] :.