В настоящее время я создаю 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, и здесь разыгрывается выражение. Код может быть более аккуратным и иметь в виду, что я не знаком с какими-либо формальными методами анализа выражений, но он работает, после моды :) .