Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 28
Каковы преимущества Вашего алгоритма перед хрестоматийной обратной польской записью?
На первый и второй взгляд, Ваш алгоритм труднее в восприятии, реализации, и, скорее всего, медленнее.
На первый и второй взгляд, Ваш алгоритм труднее в восприятии, реализации, и, скорее всего, медленнее.
При составлении алгоритма предполагалось, что древовидная структура позволяет производить расчёт одного значения за минимальный промежуток времени. Если предположить, что «дерево» будет создано один раз, затем последует расчёт сотен или тысяч значений (для построения графиков и оценки степени соответствия полученного графика заданным критериям в зависимости от значений нескольких параметров), то данный алгоритм должен обеспечить максимальное быстродействие.
Процесс построения «дерева», безусловно, более сложен и требует существенно больших ресурсов по сравнению с процессом преобразования арифметического выражения в обратную польскую запись.
Другими словами, если считать надо мало, тогда указанный Вами алгоритм с использованием обратной польской записи вне конкуренции. А если расчётов много, тогда описанный алгоритм должен быть быстрее.
Процесс построения «дерева», безусловно, более сложен и требует существенно больших ресурсов по сравнению с процессом преобразования арифметического выражения в обратную польскую запись.
Другими словами, если считать надо мало, тогда указанный Вами алгоритм с использованием обратной польской записи вне конкуренции. А если расчётов много, тогда описанный алгоритм должен быть быстрее.
В подобных случаях говорят, что нужно заткнуть сегодня те дыры, которые, к сожалению присутствуют в профессии, если не удается предложить что-либо лучше. Поскольку самые умные уже давно работают в Apple.
А вообще автору, как программисту, нужно обратить внимание на то, что профессия в основном связана с чтением. Поэтому код должен быть компактным и выразительным.
Считаю, что статья на ту же тему на несколько порядков лучше.
Есть элементарное решение данной задачи на основе формальной грамматики. Раза в 3 короче и в 10 раз понятнее выходит.
Есть конечно. Хорошим стилем было бы стразу привести название и, желательно, дать ссылку на вики.
Боюсь на таком уровне понимания материала автором википедия не поможет
P.S. ссылку на википедию хабр не ест, легко гуглиться по «грамматика, разбирающая выражение».
Подобные задачи вообще решаются в курсе теории алгоритмов как пример использования формальных грамматик.
P.S. ссылку на википедию хабр не ест, легко гуглиться по «грамматика, разбирающая выражение».
Подобные задачи вообще решаются в курсе теории алгоритмов как пример использования формальных грамматик.
По мне так алгоритм «обратной польской записи» понятнее. Вы статью напишите с примерами, всем полезнее будет.
Фактически транслятор переводит выражение с языка арифметических выражений в обратную польскую нотацию и тут-же ее вычисляет, потому что это элементарно.
Проблема же в том что вместо изучения теории и ее применения автор потратил время на изобретения очередного велосипеда. И дополнительных знаний не приобрел.
Статей по данному вопросу — вагон и тележка, практически в каждой книге по теории алгоритмов и трансляции разбирают пример как раз на базе вычисления арифметических выражений.
Проблема же в том что вместо изучения теории и ее применения автор потратил время на изобретения очередного велосипеда. И дополнительных знаний не приобрел.
Статей по данному вопросу — вагон и тележка, практически в каждой книге по теории алгоритмов и трансляции разбирают пример как раз на базе вычисления арифметических выражений.
… автор потратил время на изобретения очередного велосипеда.с этим согласен
И дополнительных знаний не приобрел.А вот с этим, как преподаватель, категорически не согласен! Автор приобрел опыт самостоятельного нешаблонного решения задачи. Опыт, который в будущем позволит решить другую нешаблонную задачу.
И всё же надеюсь, что в реальной работе автор будет использовать стандартные методы, а не изобретать велосипеды :)
Автор приобрел опыт самостоятельного нешаблонного решения задачи
В таком случае не стоило браться за реализацию.
Навык определения, когда нужно решать нестандартным способом, а когда — по шаблону, нужен гораздо чаще, чем поиск нестандартного алгоритма.
И еще: база знаний об известных алгоритмах составляет инструментарий для создания более совершенных и сложных нестандартных алгоритмов. И банальное знание того, какие бывают алгоритмы и что они делают, оказывается на практике важнее, чем умение придумать нестандартное решение.
Да и под «нестандартным решением» обычно скрывается комбинация более мелких стандартных решений. :-)
Фактически транслятор переводит выражение с языка арифметических выражений в обратную польскую нотацию и тут-же ее вычисляет, потому что это элементарно
Это в данном случае неприемлемо. Получается, что каждый раз при расчёте значения выражения мы будем снова преобразовывать арифметическое выражение в обратную польскую нотацию? При большом количестве вычислений данная процедура займет в несколько раз больше времени.
YAP — Yet Another Parser.
Автор, почему вы не использовали ANTLR или еще какой-нибудь генератор парсеров? Тоже раньше занимался математическими выражениями, посмотрите эту статью: Математические выражения в .NET (разбор, дифференцирование, упрощение, дроби, компиляция).
Автор, почему вы не использовали ANTLR или еще какой-нибудь генератор парсеров? Тоже раньше занимался математическими выражениями, посмотрите эту статью: Математические выражения в .NET (разбор, дифференцирование, упрощение, дроби, компиляция).
Из приведённой схемы становится предельно ясно, почему каждый узел может иметь только двоих «наследников», или не иметь их совсем.
Автор, что вы будете делать с унарным минусом?
Ничего не буду… его по определению нет во входном арифметическом выражении.
Т.е. отрицательные числа вам не нужны? Понимаю (:
А если бы он всё-таки был во входном выражении?
А если бы он всё-таки был во входном выражении?
Вопрос на 10 баллов из 10 возможных. Сразу просто не понял к чему Вы клоните…
По сути получается, что если программе «скормить» простенькое выражение вроде -5+7, то она и «дерево» некорректно построит и результат неверный выдаст. Надо учесть возможность наличия знака «минус» как в начале выражения, так и сразу после открывающей скобки в процессе построения массива цельных лексем.
По сути получается, что если программе «скормить» простенькое выражение вроде -5+7, то она и «дерево» некорректно построит и результат неверный выдаст. Надо учесть возможность наличия знака «минус» как в начале выражения, так и сразу после открывающей скобки в процессе построения массива цельных лексем.
Можно вставлять фиктивный 0 перед унарным минусом или плюсом, чтобы операторы всегда были бинарными.
Задача частично в том, чтобы распознать, что именно этот минус — унарный
Исправил часть программы, которая преобразует входное выражение в массив цельных лексем. Теперь, если в выражении есть унарный минус в самом начале или после открывающей скобки, то в массив лексем попадает отрицательное число. Это позволяет не плодить количество объектов в древовидной структуре сверх необходимого… И только в случае, когда унарный минус стоит перед открывающими скобками пришлось добавлять в массив лексем фиктивный ноль.
А как насчет выражения 5+-7? Нормально посчитается?
Возможность подачи подобных выражений на вход программы не предусмотрена. Но не смотря на это получим «дерево» в виде:
Подобное дерево выдает верный результат: -2
С точки зрения грамматики арифметических выражений, данное выражение следует записать в виде: 5+(-7). Тогда формируется древовидная структура вида:
Результат аналогичный: -2.
-
/ \
+ 7
/ \
5 null
Подобное дерево выдает верный результат: -2
С точки зрения грамматики арифметических выражений, данное выражение следует записать в виде: 5+(-7). Тогда формируется древовидная структура вида:
+
/ \
5 -7
Результат аналогичный: -2.
Кто-то в очередной раз изобрел конечный автомат?
Написано суховато и как-то скомкано, не хватает картинок для лучшей иллюстрации структур данных и алгоритма, какая-то самопальная терминология («точки перегиба»). Ну да ладно, статью читал по диагонали, сильно критиковать не стану. А вот код я читал внимательнее, и он попахивает:
В общем, советую автору поработать над стилем кода и подтянуть английский, если уж он решил заняться просвещением. Для первого могу посоветовать «Чистый код» Роберта Мартина; и пусть код в ней на Java, зато советы хорошие и универсальные, да и глаза не будут болеть от вездесущего $. Второе решается регулярным чтением (блоги, доки и пр.) и просмотром фильмов/сериалов с субтитрами.
Я изучал разбор выражений по книге Herbert Shildt «Expert C++» 1996 (глава 3). Там всё разложено по полочкам, стиль изложения приятный — как раз для новичков, более полная реализация (есть унарный минус и не только). К тому же, в главе 10 описывается создание интерпретатора этакого мини-BASIC, которое в то моё нубское время взорвало мне мозг и наполнило ощущением невиданной мощи (можно «написать» свой язык программирования!). Автор в обеих главах использует метод рекурсивного спуска. Возможно, кому-то это покажется неэффективным, кто-то скажет про генераторы парсеров, и т.п., но в образовательных целях пойдёт, тем более что для начала хватит и вычисления выражений на лету, без явного построения дерева (цель автора — показать принцип, не перегружая деталями).
- Копипаста:
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, которое в то моё нубское время взорвало мне мозг и наполнило ощущением невиданной мощи (можно «написать» свой язык программирования!). Автор в обеих главах использует метод рекурсивного спуска. Возможно, кому-то это покажется неэффективным, кто-то скажет про генераторы парсеров, и т.п., но в образовательных целях пойдёт, тем более что для начала хватит и вычисления выражений на лету, без явного построения дерева (цель автора — показать принцип, не перегружая деталями).
Надеюсь PHP — не ваш основной инструмент… В противном случае вас можно отнести к группе людей из-за которых PHP ненавидят. (CodeStyle, Naming, OOP).
Вам следует почитать про шаблон интерпретатор, AST, BNF и оптимальные способы «приписывания» цифры к числу (запомните: строки в оптимизации — ЗЛО)
Вам следует почитать про шаблон интерпретатор, AST, BNF и оптимальные способы «приписывания» цифры к числу (запомните: строки в оптимизации — ЗЛО)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Алгоритм парсинга арифметических выражений