Общие сведения


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

Парсер — это программа, анализирующая входное арифметическое выражение. Программы подобного класса, иногда называют так же «распознавателями».

Парсинг — процесс разбора входного арифметического выражения на более простые составляющие.

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

Описание алгоритма распознавания приводится без привязки к какому-либо языку программирования. В заключении статьи приведен пример реализации данного алгоритма на PHP. Возможна реализация алгоритма практически на любом языке программирования (даже без поддержки ООП).

Постановка задачи


Предположим, что парсер принимает на входе арифметическое выражение, представляющее собой обычную строку вида: (x+10.2)^2+5*y-z. Входное выражение является правильным с точки зрения грамматики арифметических выражений:
  • Количество открывающих скобок равно количеству закрывающих.
  • Целая часть числа отделена от дробной с помощью точки.
  • В строке присутствуют только допустимые символы: цифры 0...9, операторы +-*/^, скобки, точка и параметры x, y, z.

Парсер должен построить дерево лексем, пригодное для вычисления численного значения входного выражения. Значения параметров будем передавать методу, реализующему расчет численного значения.

Для каждого конкретного выражения дерево объектов строится один раз. Затем, используя полученное дерево объектов, вычисляем итоговое значение выходного выражения с учетом значений параметров. Повторять вычисления можно неограниченное число раз.

Алгоритм должен позволить обработку входных выражений неограниченной длины (в разумных пределах) без ограничений по уровню вложенности скобок.

Лексический анализ входного выражения


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

Для примера, вернёмся к рассмотрению строки арифметического выражения, приведённую выше: (x+10.2)^2+5*y-z. В процессе лексического анализа указанная строка будет преобразована в массив строк следующей структуры: [0]=>”(”, [1]=>”x”, [2]=>”+”, [3]=>”10.2”, [4]=>”)”, [5]=>”^”, [6]=>”2”, [7]=>”+”, [8]=>”5”, [9]=>”*”, [10]=>”y”, [11]=>”-”, [12]=>”z”.

Таким образом, цельная лексема представляет из себя либо оператор (арифметическую операцию), либо операнд (число, состоящее из одной или нескольких цифр), либо параметр (x, y, z) или скобку (как элемент, изменяющий приоритет выполнения арифметических операций в строке).

Лексема как объект


Каждая цельная лексема в составе древовидной структуры описывается объектом. Любой объект «дерева» обладает набором свойств (полей) и определенным поведением. Перечислим предполагаемый набор полей данных для каждого объекта, моделирующего лексему:
  1. Поле name — определяет уникальное имя объекта.
  2. Поле lec — массив лексем, для хранения информации о той части входного выражения вершиной которого является данный узел «дерева» объектов.
  3. Поле const — если данный объект представляет собой параметр, тогда переменная хранит его наименование.
  4. Поле var — если данный объект представляет собой число или параметр, то переменная хранит его значение.

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

Все объекты древовидной структуры могут принадлежать одному классу, достаточно просто переопределить один метод при создании объекта. Или, как вариант, можно описать абстрактный класс с одной абстрактной функцией calc(). Далее для каждого типа лексемы опишем свой класс, наследующий абстрактный класс и определяющий конкретное поведение метода calc(). В примере программной реализации выбран последний способ, для которого требуется существенно меньший объём кода.

Некоторые поля могут оставаться незаполненными — это зависит от того, какую лексему моделирует данный конкретный объект.

Лексема как узел древовидной структуры


Конфигурация объектов, моделирующих лексемы в общих чертах ясна. Но тут возникает вопрос о том, как сформировать из этих объектов древовидную структуру?

Данная проблема довольно типична для проектов программного обеспечения. Суть решения можно получить из шаблона проектирования с названием: «Компоновщик». Слепое копирование всех тонкостей данного шаблона проектирования (паттерна) не входит в наши планы, поэтому пытаемся выделить самое главное и необходимое для конкретного случая.

Для компоновки объектов в древовидную структуру добавим в каждый объект еще три поля:
  1. Поле childrenLeft — левый «наследник» данного объекта.
  2. Поле childrenRight — правый «наследник» данного объекта.
  3. Поле parent — «родитель» данного объекта.

Здесь и далее термины «родитель» и «наследник» используются без привязки к одному из ключевых принципов ООП, а в контексте указания на относительное местоположение других объектов относительно заданного в сформированной древовидной структуре.
Чтобы пояснить сказанное, приведём изображение древовидной структуры для выражения «(x+10.2)^2+5*y-z», указав значения всех полей объектов.



Из приведённой схемы становится предельно ясно, почему каждый узел может иметь только двоих «наследников», или не иметь их совсем.

Полученная структура объектов вполне приемлема для расчета значений арифметических выражений посредством вызова метода calc() самого верхнего на схеме объекта.

Поиск точки «перегиба» арифметического выражения


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

Для ввода возможности оценивать значения приоритетов арифметических операций в программе достаточно определить массив со структурой: [+]=>3, [-]=>3, [*]=>2, [/]=>2, [^]=>1.

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

Далее в массиве лексем выделяются элементы, стоящие слева от точки «перегиба» и записываются в поле lec объекта, являющегося левым «наследником». Элементы, расположенные справа от точки «перегиба» заносятся в аналогичное поле правого «наследника». Следует так же упомянуть, что при поиске точки «перегиба» следует учитывать уровень вложенности скобок в массиве цельных лексем.

Построение древовидной структуры


В данном разделе подробно разберём последовательность формирования «дерева» объектов в рамках предложенного алгоритма.
Рассмотрим процедуру построения первых трёх объектов «дерева», включая корневой объект и его двоих «наследников». Получив на входе массив цельных лексем всего арифметического выражения, находим в нём точку «перегиба». Напомню, что это всегда оператор (арифметическое действие). Значение найденной точки «перегиба» позволяет однозначно определить класс объекта, находящегося на вершине структуры. Далее делим массив лексем на две части, как было описано выше. В каждой из обеих частей так же находим точки «перегиба», которые указывают на класс объектов левого и правого «наследников». Теперь можно сформировать все три объекта и указать связи между ними. В завершение объекты помещают в массив arNode для последующих действий над ними.

Для нашего входного выражения: (x+10.2)^2+5*y-z описанная процедура выглядит следующим образом. Под определение точки «перегиба» подпадают два оператора: «+» (между цифрами «2» и «5») и «-». Выбираем последний оператор в перечне: «-». Значение этого оператора позволяет выбрать необходимый класс корневого объекта и его имя. В частности, формируется объект класса Minus с именем Minus1. После деления исходного массива лексем на две части получаем два массива из элементов: (x+10.2)^2+5*y и z. Для первой лексемы точка перегиба "+", а вторая состоит только из одного элемента z. Это значит, что в качестве «наследников» корневого объекта следует сформировать объекты классов Plus и Constant с именами Plus1 и Constant1 соответственно. Осталось заполнить поля вновь созданных объектов: childrenLeft, childrenRight и parent для формирования древовидной структуры и внести объекты в массив arNode.

Дальнейшее формирование «дерева» очень похоже на процедуру создания первой тройки, но имеет свои тонкости. В массиве arNode простым перебором по элементам массива ищем объект с полем lec, содержащем более одного элемента в массиве и одновременно с пустыми полями childrenLeft и childrenRight. Считываем значение поля lec у выбранного объекта, делим его на две части в точке «перегиба». Далее находим точки «перегиба» у получившихся обеих частей и формируем два объекта-наследника для выбранного объекта, в соответствии с логикой изложенной выше. Не забываем формировать связи между объектами и добавлять сами объекты в массив arNode.

Указанную последовательность действий повторяем до тех пор, пока ни один из объектов древовидной структуры не будет соответствовать указанным условиям. Теперь можно считать, что «дерево» для нашего входного выражения построено и готово для вычисления значений.

Вычисление значений


Процесс вычисления значений входного арифметического выражения становится предельно ясен при просмотре листинга программной реализации алгоритма. Остановимся на некоторых существенных моментах.

Расчет происходит после вызова метода calc() объекта класса Main. В программе предусмотрена возможность использования не более трех параметров при вызове данного метода: x, y, z. Несложно это количество изменить с учетом потребностей конкретного применения описанного алгоритма.

Предварительно метод ищет в массиве объекты, описывающие лексемы параметров, затем в поля var найденных объектов заносятся числовые значения, указанные при вызове метода calc(). Теперь можно приступать к поиску в массиве arNode объекта с пустым полем parent (это будет корневой объект древовидной структуры) и вызвать его метод calc(). Метод возвращает значение арифметического выражения.

Пример программной реализации


Листинг программной реализации решено выложить целиком. Это позволяет скопировать программу целиком при необходимости проведения с ней экспериментов или доработки.

<!DOCTYPE html>
<html>

    <head>
        <meta charset="UTF-8">
        <title>Алгоритм</title>
    </head>

    <body>
        <?php

        class Main {
            
            // массив объектов дерева
            var $arNode = Array();
            
            // расчет значения с учетом параметров
            public function calc($x, $y, $z){
                
                if($x){
                    foreach ($this->arNode as $obj){
                        if($obj->const == "x"){
                            $obj->var = $x;
                            break;
                        }
                    }
                }
                
                if($y){
                    foreach ($this->arNode as $obj){
                        if($obj->const == "y"){
                            $obj->var = $y;
                            break;
                        }
                    }
                }
                
                if($z){
                    foreach ($this->arNode as $obj){
                        if($obj->const == "z"){
                            $obj->var = $z;
                            break;
                        }
                    }
                }
                
                foreach ($this->arNode as $obj){
                    if(!$obj->parent){
                        return $obj->calc();
                    }
                }
            }

            // реализация строительства дерева классов
            public function builder ($str) {                
                        
                // массив объектов дерева
                $arNode = Array();

                // предварительные операции с входной строкой
                function parse ($str){

                    // подготовка входного выражения к парсингу
                    $str = mb_strtolower($str, 'UTF-8');
                    $str = str_replace(" ", "", $str);
                    $n = mb_strlen($str, 'UTF-8');
                    $arStr = preg_split('/(?!^)(?=.)/u', $str);
                    
                    echo '<pre>';
                    echo print_r($arStr);
                    echo '</pre>';

                    // преобразуем массив символов в массив лексем
                    $j=0;
                    $accum = $arStr[0];
                    for($i=1; $i<$n+1; ++$i){
                        
                        if ($i==$n+1){
                            $arLec[$j] = $accum;
                            break;
                        }
                        
                        if($accum=="-" && $i==1){
                            if(preg_match("/\d/", $arStr[$i])){
                                $accum = $accum.$arStr[$i];
                            }
                            if($arStr[$i]=="("){
                                $arLec[$j] = "0";
                                $arLec[++$j] = "-";
                                ++$j;
                                $accum = $arStr[$i];
                            }
                            continue;
                        }
                        
                        if($accum=="-" && $arLec[$j-1]=="("){
                            $accum = $accum.$arStr[$i];
                            continue;
                        }
                        
                        if (preg_match("/^[\d.]/", $accum) && preg_match("/^[\d.]/", $arStr[$i])){
                            $accum = $accum.$arStr[$i];
                        }else{
                            $arLec[$j] = $accum;
                            ++$j;
                            $accum = $arStr[$i];
                        }
                    }
                    /*
                    $j = 0;                    
                    if($arStr[0]=="-"){
                        $accum = $arStr[0];
                    }else{
                        $accum = $arStr[0];
                    }
                    
                    for ($i=1; $i<$n+1; ++$i){                    
                        if ($i==$n+1){
                            $arLec[$j] = $accum;
                            continue;
                        }
                        if (preg_match("/^[\d.]/", $accum)&&preg_match("/^[\d.]/", $arStr[$i])){
                            $accum = $accum.$arStr[$i];
                        }else{
                            $arLec[$j] = $accum;
                            ++$j;
                            $accum = $arStr[$i];
                        } 
                    }
                     * 
                     */
                    
                    echo '<pre>';
                    echo print_r($arLec);
                    echo '</pre>';
                    
                    return $arLec;
                }
                
                // построение одного объекта
                function objBuilder($point){
                        
                    static $arNumNode = Array(
                        "addition" => 1,
                        "subtraction" => 1,
                        "exponentiation" =>1,
                        "multiplication" => 1,
                        "division" => 1,
                        "number" => 1,
                        "constant" => 1);
                        
                    switch ($point){

                        case "+": $name = "Plus".$arNumNode["addition"];
                            $node = new Plus($name);
                            ++$arNumNode["addition"];
                            break;

                        case "-": $name = "Minus".$arNumNode["subtraction"];
                            $node = new Minus($name);
                            ++$arNumNode["subtraction"];
                            break;

                        case "*": $name = "Multiply".$arNumNode["multiplication"];
                            $node = new Multiply($name);
                            ++$arNumNode["multiplication"];
                            break;

                        case "/": $name = "Fission".$arNumNode["division"];
                            $node = new Fission($name);
                            ++$arNumNode["division"];
                            break;

                        case "^": $name = "Exponent".$arNumNode["exponentiation"];
                            $node = new Exponent($name);
                            ++$arNumNode["exponentiation"];
                            break;
                        
                        case "x": $name = "Constant".$arNumNode["constant"];
                            $node = new Constant($name);
                            $node->const = "x";
                            $node->var = 0;
                            ++$arNumNode["constant"];
                            break;
                        
                        case "y": $name = "Constant".$arNumNode["constant"];
                            $node = new Constant($name);
                            $node->const = "y";
                            $node->var = 0;
                            ++$arNumNode["constant"];
                            break;
                        
                        case "z": $name = "Constant".$arNumNode["constant"];
                            $node = new Constant($name);
                            $node->const = "z";
                            $node->var = 0;
                            ++$arNumNode["constant"];
                            break;

                        default: $name = "Variable".$arNumNode["number"];
                            $node = new Variable($name);
                            $node->var = $point;
                            ++$arNumNode["number"];
                    }
                    return $node;                    
                }
                
                // строительство тройки объектов дерева
                function trioBuilder($topLec, $leftLec, $rightLec, $topP, $leftP, $rightP, $topObj){
    
                    // вершина тройки
                    if(!$topObj){
                        $topTrio = objBuilder($topP);
                        $topTrio->lec = $topLec;
                    }  else {
                        $topTrio = $topObj;
                    }

                    // левая ветвь тройки
                    $leftTrio = objBuilder($leftP);
                    $leftTrio->lec = $leftLec;

                    // правая ветвь тройки
                    $rightTrio = objBuilder($rightP);
                    $rightTrio->lec = $rightLec;

                    // формирование тройки из объектов
                    $topTrio->childrenLeft = $leftTrio;
                    $topTrio->childrenRight = $rightTrio;
                    $leftTrio->parent = $topTrio;
                    $rightTrio->parent = $topTrio;
                    if(!$topObj){
                        $trio = Array($topTrio, $leftTrio, $rightTrio);
                        return $trio;
                    }  else {
                        $duo = Array($leftTrio, $rightTrio);
                        return $duo;
                    }
                }
                
                // проверка на полное построение дерева
                function stopBuild($arNode){
                    foreach ($arNode as $obj){
                        if($obj->lec[1] && !$obj->childrenLeft && !$obj->childrenRight){
                            return FALSE;
                        }
                    }
                    return TRUE;
                }

                // поиск вершины для следующей тройки
                function searchObj($arNode){
                    foreach ($arNode as $obj){
                        if($obj->lec[1] && !$obj->childrenLeft && !$obj->childrenRight){
                            return $obj;
                        }
                    }
                }                

                // определение точки перегиба выражения
                function inflPoint($lec){
                    $infl=0;
                    $max=0;
                    static $br = 0;
                    static $arPrioritet = Array(
                        "+" => 3,
                        "-" => 3,
                        "*" => 2,
                        "/" => 2,
                        "^" => 1);

                    foreach ($lec as $key=>$value){
                        if(preg_match("/^[\d.]/", $value)){
                            continue;
                        }
                        if($value=="("){
                            ++$br;
                            continue;
                        }
                        if($value==")"){
                            --$br;
                            continue;
                        }
                        if($arPrioritet[$value]-3*$br >= $max){
                            $max=$arPrioritet[$value]-3*$br;
                            $infl=$key;
                        }
                    }
                    return $infl;
                }

                $arLec = parse($str);

                // первая тройка дерева
                $topN = inflPoint($arLec);
                $topP = $arLec[$topN];
                $leftLec = array_slice($arLec, 0, $topN);
                if($leftLec[0]=="(" && $leftLec[count($leftLec)-1]==")"){
                    array_shift($leftLec);
                    array_pop($leftLec);
                }
                $rightLec = array_slice($arLec, $topN+1);
                if($rightLec[0]=="(" && $rightLec[count($rightLec)-1]==")"){
                    array_shift($rightLec);
                    array_pop($rightLec);
                }
                $leftN = inflPoint($leftLec);
                $leftP = $leftLec[$leftN];
                $rightN = inflPoint($rightLec);
                $rightP = $rightLec[$rightN];                
                $trio = trioBuilder($arLec, $leftLec, $rightLec, $topP, $leftP, $rightP, NULL);
                $arNode = $trio;

                // все последующие тройки дерева
                while (!stopBuild($arNode)){
                        $topTrio = searchObj($arNode);
                        $arLec = $topTrio->lec;
                        $topN = inflPoint($arLec);    
                        $leftLec = array_slice($arLec, 0, $topN);
                        if($leftLec[0]=="(" && $leftLec[count($leftLec)-1]==")"){
                            array_shift($leftLec);
                            array_pop($leftLec);
                        }
                        $rightLec = array_slice($arLec, $topN+1);
                        if($rightLec[0]=="(" && $rightLec[count($rightLec)-1]==")"){
                            array_shift($rightLec);
                            array_pop($rightLec);
                        }
                        $leftN = inflPoint($leftLec);
                        $leftP = $leftLec[$leftN];
                        $rightN = inflPoint($rightLec);
                        $rightP = $rightLec[$rightN];                
                        $duo = trioBuilder(NULL, $leftLec, $rightLec, NULL, $leftP, $rightP, $topTrio);
                        $arNode = array_merge($arNode, $duo);
                }
                $this->arNode = $arNode;
            }
        }

        abstract class Term {

            public $name;
            public $childrenLeft;
            public $childrenRight;
            public $parent;
            public $lec;
            public $const;
            public $var;

            public function __construct($name) {
                $this->name = $name;
            }
            
            abstract function calc();
        }
        
        class Plus extends Term {
            public function calc() {
                return $this->childrenLeft->calc()+$this->childrenRight->calc();
            }
        }
        
        class Minus extends Term {
            public function calc() {
                return $this->childrenLeft->calc()-$this->childrenRight->calc();
            }
        }
        
        class Multiply extends Term {
            public function calc() {
                return $this->childrenLeft->calc()*$this->childrenRight->calc();
            }
        }
        
        class Fission extends Term {
            public function calc() {
                return $this->childrenLeft->calc()/$this->childrenRight->calc();
            }
        }
        
        class Exponent extends Term {
            public function calc() {
                return pow ($this->childrenLeft->calc(), $this->childrenRight->calc());
            }
        }
        
        class Constant extends Term {
            public function calc() {
                return $this->var;
            }
        }
        
        class Variable extends Term {
            public function calc() {
                return $this->var;
            }
        }        

        // задаем исходное математическое выражение
        $str = "(x+10.2)^2+5*y-z";
        $x = 2;
        $y = 1;
        $z = 3;

        $parse = new Main();

        // строительство дерева классов
        $parse->builder($str);
        
        //echo '<pre>';
        //echo print_r($parse->arNode);
        //echo '</pre>';


        echo $str." = ".$parse->calc($x, $y, $z);

        echo " при: x=".$x."; y=".$y."; z=".$z;

        ?>
    </body>

</html>

Если убрать комментарии из трех идущих подряд операторов echo в конце программы, то можно проанализировать правильность формирования древовидной структуры и посмотреть значения полей всех объектов.

Заключение


Старался описать алгоритм по возможности подробно, но если остались вопросы — пишите, постараюсь всем ответить. Буду так же признателен за сообщения о найденных ошибках и неточностях в тексте.

Комментарии (26)


  1. Fuco
    29.07.2015 12:12
    +9

    Каковы преимущества Вашего алгоритма перед хрестоматийной обратной польской записью?
    На первый и второй взгляд, Ваш алгоритм труднее в восприятии, реализации, и, скорее всего, медленнее.


    1. Pilum Автор
      29.07.2015 18:35

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


      1. aparamonov
        30.07.2015 05:28

        Предполагалось? Должен быть?
        А бенчмарки-то где?


  1. alexhemp
    29.07.2015 12:47
    -1

    Есть элементарное решение данной задачи на основе формальной грамматики. Раза в 3 короче и в 10 раз понятнее выходит.


    1. Danov
      29.07.2015 13:27
      +3

      Есть конечно. Хорошим стилем было бы стразу привести название и, желательно, дать ссылку на вики.


      1. alexhemp
        29.07.2015 13:29
        -1

        Боюсь на таком уровне понимания материала автором википедия не поможет

        P.S. ссылку на википедию хабр не ест, легко гуглиться по «грамматика, разбирающая выражение».

        Подобные задачи вообще решаются в курсе теории алгоритмов как пример использования формальных грамматик.


        1. Danov
          29.07.2015 13:47
          +3

          По мне так алгоритм «обратной польской записи» понятнее. Вы статью напишите с примерами, всем полезнее будет.


          1. alexhemp
            29.07.2015 14:03

            Фактически транслятор переводит выражение с языка арифметических выражений в обратную польскую нотацию и тут-же ее вычисляет, потому что это элементарно.

            Проблема же в том что вместо изучения теории и ее применения автор потратил время на изобретения очередного велосипеда. И дополнительных знаний не приобрел.

            Статей по данному вопросу — вагон и тележка, практически в каждой книге по теории алгоритмов и трансляции разбирают пример как раз на базе вычисления арифметических выражений.


            1. Danov
              29.07.2015 14:30
              +4

              … автор потратил время на изобретения очередного велосипеда.
              с этим согласен
              И дополнительных знаний не приобрел.
              А вот с этим, как преподаватель, категорически не согласен! Автор приобрел опыт самостоятельного нешаблонного решения задачи. Опыт, который в будущем позволит решить другую нешаблонную задачу.

              И всё же надеюсь, что в реальной работе автор будет использовать стандартные методы, а не изобретать велосипеды :)


              1. Colwin
                30.07.2015 10:58

                Автор приобрел опыт самостоятельного нешаблонного решения задачи


                В таком случае не стоило браться за реализацию.

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

                Да и под «нестандартным решением» обычно скрывается комбинация более мелких стандартных решений. :-)


            1. Pilum Автор
              29.07.2015 19:02

              Фактически транслятор переводит выражение с языка арифметических выражений в обратную польскую нотацию и тут-же ее вычисляет, потому что это элементарно

              Это в данном случае неприемлемо. Получается, что каждый раз при расчёте значения выражения мы будем снова преобразовывать арифметическое выражение в обратную польскую нотацию? При большом количестве вычислений данная процедура займет в несколько раз больше времени.


              1. 3StYleR
                29.07.2015 21:36
                +3

                Зачем? Один раз построили ОПЗ, а потом меняем значения переменных.


  1. KvanTTT
    29.07.2015 14:00
    +1

    YAP — Yet Another Parser.

    Автор, почему вы не использовали ANTLR или еще какой-нибудь генератор парсеров? Тоже раньше занимался математическими выражениями, посмотрите эту статью: Математические выражения в .NET (разбор, дифференцирование, упрощение, дроби, компиляция).


  1. jcmvbkbc
    29.07.2015 16:17
    +2

    Из приведённой схемы становится предельно ясно, почему каждый узел может иметь только двоих «наследников», или не иметь их совсем.

    Автор, что вы будете делать с унарным минусом?


    1. Pilum Автор
      29.07.2015 19:30

      Ничего не буду… его по определению нет во входном арифметическом выражении.


      1. jcmvbkbc
        29.07.2015 19:44
        +2

        Т.е. отрицательные числа вам не нужны? Понимаю (:
        А если бы он всё-таки был во входном выражении?


        1. Pilum Автор
          30.07.2015 10:57
          +1

          Вопрос на 10 баллов из 10 возможных. Сразу просто не понял к чему Вы клоните…
          По сути получается, что если программе «скормить» простенькое выражение вроде -5+7, то она и «дерево» некорректно построит и результат неверный выдаст. Надо учесть возможность наличия знака «минус» как в начале выражения, так и сразу после открывающей скобки в процессе построения массива цельных лексем.


          1. KvanTTT
            30.07.2015 11:52

            Можно вставлять фиктивный 0 перед унарным минусом или плюсом, чтобы операторы всегда были бинарными.


            1. jcmvbkbc
              30.07.2015 14:56
              +1

              Задача частично в том, чтобы распознать, что именно этот минус — унарный


              1. Pilum Автор
                30.07.2015 23:01

                Исправил часть программы, которая преобразует входное выражение в массив цельных лексем. Теперь, если в выражении есть унарный минус в самом начале или после открывающей скобки, то в массив лексем попадает отрицательное число. Это позволяет не плодить количество объектов в древовидной структуре сверх необходимого… И только в случае, когда унарный минус стоит перед открывающими скобками пришлось добавлять в массив лексем фиктивный ноль.


                1. 3StYleR
                  31.07.2015 00:14

                  А как насчет выражения 5+-7? Нормально посчитается?


                  1. Pilum Автор
                    31.07.2015 12:25

                    Возможность подачи подобных выражений на вход программы не предусмотрена. Но не смотря на это получим «дерево» в виде:

                         -
                        /    +   7
                      / 5   null
                    

                    Подобное дерево выдает верный результат: -2
                    С точки зрения грамматики арифметических выражений, данное выражение следует записать в виде: 5+(-7). Тогда формируется древовидная структура вида:
                         +
                        /    5  -7
                    

                    Результат аналогичный: -2.


  1. ololoepepe
    29.07.2015 16:34
    +2

    Кто-то в очередной раз изобрел конечный автомат?


    1. Colwin
      30.07.2015 11:01

      Скорее, конченый автомат.


  1. burjui
    30.07.2015 01:10
    +1

    Написано суховато и как-то скомкано, не хватает картинок для лучшей иллюстрации структур данных и алгоритма, какая-то самопальная терминология («точки перегиба»). Ну да ладно, статью читал по диагонали, сильно критиковать не стану. А вот код я читал внимательнее, и он попахивает:

    • Копипаста:
      public function calc($x, $y, $z){
        ...
        if($x){
          // некий код
        }
        ...
        if($y){
          // тот же код, только для 'y'
        }
        ...
        // и для 'z'... :(
      }
      

    • Избыточность.

      Куча классов для каждого оператора. Если не нужно получившееся дерево распечатывать с минимальным количеством скобок или его оптимизировать для компиляции (свёртка констант, замена умножения сложением и прочие трюки), или делать ещё что-то подобное, то хватит и одного класса Operation со switch по оператору внутри.

      Жутко избыточый класс Term.
    • Стрёмные названия функций:
      • Неглагольные типа objBuilder, builder
      • Экономия на символах — inflPoint, тот же objBuilder
      • Неясные или искажающие смысл:
        // проверка на полное построение дерева
        function stopBuild($arNode){

        // поиск вершины для следующей тройки
        function searchObj($arNode){
    • Runglish. Смесь ломаного английского с транслитерированным русским.

    В общем, советую автору поработать над стилем кода и подтянуть английский, если уж он решил заняться просвещением. Для первого могу посоветовать «Чистый код» Роберта Мартина; и пусть код в ней на Java, зато советы хорошие и универсальные, да и глаза не будут болеть от вездесущего $. Второе решается регулярным чтением (блоги, доки и пр.) и просмотром фильмов/сериалов с субтитрами.

    Я изучал разбор выражений по книге Herbert Shildt «Expert C++» 1996 (глава 3). Там всё разложено по полочкам, стиль изложения приятный — как раз для новичков, более полная реализация (есть унарный минус и не только). К тому же, в главе 10 описывается создание интерпретатора этакого мини-BASIC, которое в то моё нубское время взорвало мне мозг и наполнило ощущением невиданной мощи (можно «написать» свой язык программирования!). Автор в обеих главах использует метод рекурсивного спуска. Возможно, кому-то это покажется неэффективным, кто-то скажет про генераторы парсеров, и т.п., но в образовательных целях пойдёт, тем более что для начала хватит и вычисления выражений на лету, без явного построения дерева (цель автора — показать принцип, не перегружая деталями).


  1. saksmt
    30.07.2015 08:40
    +1

    Надеюсь PHP — не ваш основной инструмент… В противном случае вас можно отнести к группе людей из-за которых PHP ненавидят. (CodeStyle, Naming, OOP).

    Вам следует почитать про шаблон интерпретатор, AST, BNF и оптимальные способы «приписывания» цифры к числу (запомните: строки в оптимизации — ЗЛО)