Как использовать деревья выражений в PHP?

В настоящее время я создаю PHP-программу, которая решает уравнения. Я разделил входное уравнение на массив так, чтобы каждая строка в массиве содержала один термин. (So. [0] = "+ 5x", [1] = "=", [2] = "-5", [3] = "+10". Это просто базовое уравнение. (например, 2x + (5-3x) = 3 (x + 1) [0] = "+ 2 * x", [1] = массив ([0] = "+5" ….

Однако я обнаружил деревья выражений, которые идеально подходят для использования в этом решении. Я искал весь интернет, чтобы узнать его, но я не могу найти сайты, которые объясняют это на PHP (я знаю PHP OOP.). Есть много страниц, объясняющих их, например, на C, но поскольку я знаю только PHP, это не поможет, потому что я не понимаю пример кода.

Может ли кто-нибудь здесь объяснить все о деревьях выражений в PHP и некоторый практический пример кода?

Вот описанный алгоритм . вы можете реализовать это в PHP. Я не думаю, что кто-то уже реализовал это в PHP (и распространял его как открытый исходный код)

Примером может служить:

2*x+3*5-(6+9) = 0 

Где:

  • * = приоритет 2
  • + = приоритет 1
  • ( = увеличит приоритет знаков на 10
  • + (второй +) = приоритет 11
  • ) = уменьшит приоритет знаков на 10
  • = = в этом случае он показывает, что существует другое выражение (0)

Самый высокий приоритет – самый важный – тот, который вам нужно сделать в первую очередь

Используя эти правила, вы можете создать дерево выражений …

Итак .. способ, которым вы должны создать выражение, а затем интерпретировать:

 2 x * 3 5 * + 6 9 + - 

Разъяснение:

  • 2 * x | (1)
  • 3 * 5 | (2)
  • (1) + (2) | (3)
  • 6 + 9 | (4)
  • (3) - (4) = final

Я точно не помню, как писать дерево. Я сделал это на курсе в области компьютерных наук, но это было примерно так:

  - / \ E (E) | + + / \ / \ 6 9 EE | | * * / \ / \ TETE | | | | 2 T 3 T | | x 5 

Теперь для этого вам нужно создать собственный интерпретатор. Вы можете использовать шаблон интерпретатора: PHP Interpreter

Я бы посоветовал вам немного прочитать образец шаблона Composite для ваших деревьев выражений. Статья Википедии об этом имеет некоторые диаграммы UML и пример Java-кода, который не так сложно перевести на PHP.

Вы, вероятно, захотите также взглянуть на алгоритм Shunting-yard , для разбора вашей строки в дереве выражений.

A (очень упрощенный) PHP-пример дерева выражений может выглядеть так:

 interface INode { public function getValue(); } class ValueNode implements INode { private $val; function __construct($val) { $this->val = $val; } public function getValue() { return $this->val; } } class AdditionNode implements INode { private $op1, $op2; function __construct($op1, $op2) { if(!($op1 instanceof INode) or !($op2 instanceof INode)) { throw new Exception("The operands must implement the INode interface."); } $this->op1 = $op1; $this->op2 = $op2; } public function getValue() { return $this->op1->getValue() + $this->op2->getValue(); } } $a = new ValueNode(1); $b = new ValueNode(5); $c = new ValueNode(10); $add1 = new AdditionNode($a, $b); $add2 = new AdditionNode($add1, $c); echo $add2->getValue(); // 16 

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

Класс ValueNode является простой оболочкой, позволяющей числам быть частью вашего дерева выражений (фактически, в PHP вы не ограничены только номерами в ValueNode ). Объекты ValueNode могут служить только узлами листа в вашем дереве выражений.

Вы начинаете использовать составной шаблон с классом AdditionNode , который принимает объекты INode качестве дочерних INode и может помочь вам построить дерево выражений.

Вы можете расширить этот пример дальше, чтобы добавить другие операции, переменные, константы и т. Д., Которые будут реализовывать интерфейс INode.

Я построил дерево выражений в PHP, которое анализирует математические выражения и пытается решить проблему. Вы можете найти источник здесь http://codehackit.blogspot.com/2011/08/expression-parser-in-php.html

Я в значительной степени объясняю все подробности в этом сообщении в блоге, но если вы найдете какие-то двусмысленности, просто спросите здесь;)

Приветствия, надеюсь, что это поможет или хотя бы вдохновляет

Несколько лет назад я написал парсер для этой утилиты – он занимает выражение SQL WHERE в квадратных скобках почти любой глубины и преобразует его в код PHP Propel. Здесь весь tarball, и здесь разыгрывается выражение. Код может быть более аккуратным и иметь в виду, что я не знаком с какими-либо формальными методами анализа выражений, но он работает, после моды :) .