доброго времени суток
хочу реализовать распознавание математических выражений и формул в введенной строке. Например, пусть строковая переменная s:='sin(x)+x-5*sqrt(x)', а мне надо построить ее график. Вопрос: можно ли реализовать это с помощью обратной польской записи?
IUnknown
10.11.2012 20:09
На форуме уже выкладывались решения для подобных задач. Можешь поискать по слову "интерпретатор". Я предлагал для таких вещей строить дерево разбора, поскольку при использовании ОПЗ у тебя будет препятствие: сложно будет реализовать и вычисление арифметических операций, и вычисление функций одной/нескольких переменных.
TarasBer
10.11.2012 20:18
Цитата(IUnknown @ 10.11.2012 16:09)
сложно будет реализовать и вычисление арифметических операций, и вычисление функций одной/нескольких переменных.
Дело не в количестве, а в том, что оно не определено. Пихать вместо с функцией ещё и число аргументов? Ну так себе решение...
Ещё проблема с ленивыми операторами, типа iff. В польской записи их как реализовать?
Как в польской записи делать оптимизации, заменять ветки, состоящие из констант, на результат выражения?
значит забыть про ОПЗ и изучать дерево разбора?
планировалось, что функции у меня должны быть только одной переменной
Я бы сделал дерево разбора.
Да, с ним могут быть вопросы, как хранить вершины, чтобы корректно удалить в случае чего.
Самый простой и безотказный способ - все новые вершины дерева регистрировать в отдельном списке. При удалении дерева просто пробегаться по этому списку. В процессе преобразования дерева будет много ненужных, мёртвых вершин, но так как они есть в списке, то память не утечёт. Ну и есть вдруг окажется, что лишние вершины занимают слишком много оперативы, то можно сделать отдельный проход по дереву в конце, чтобы сразу убрать ненужные вершины (мне так пришлось делать ради того, чтобы в самом конце расход памяти был нормальный и не лагало, хотя необходимост как бы и нету).
тут годится бинарное дерево? я правильно понял?
TarasBer
13.11.2012 14:09
Почему бинарное? А если операция принимает не два аргумента?
Цитата(TarasBer @ 13.11.2012 10:09)
Почему бинарное? А если операция принимает не два аргумента?
хм, значит, не то. Можно тогда ссылку на литературу подходящую? или хотя бы по каким запросам искать? По запросу "интерпретатор" на форуме про дерево разбора не нашел.
Или же мне достаточно информации вообще про деревья и способы работы с ними?
TarasBer
13.11.2012 18:09
А что вы тогда имели в виду?
прошу прощения, но я не понял вопроса. Что я имел ввиду под чем?
IUnknown
13.11.2012 18:48
Цитата
А если операция принимает не два аргумента?
Например? Какие
операции являются тернарными или выше? Унарные и бинарные легко обрабатываются бинарным деревом.
Мне для написания парсера было достаточно бинарного дерева, но вот в узлах своих оно хранило не только токен (собственно, операция, которая будет производиться, или функция, которая будет вычисляться) и 2 дерева-потомка (операнды), а еще и поле, указывающее на список деревьев. Этим решался вопрос с функциями от любого числа переменных (просто в список добавлялись деревья, представляющие собой аргументы функции, любое их количество. С функциями от 1 до 8 аргументов работало запросто). Можно обойтись и без доп. поля, но с приведениями типов или вариантными записями.
Извиняюсь, если лезу, но вроде как условная дизъюнкция в мат. логике является тернарной.
Хотя я уверен, что для ТС подобный функционал не нужен, но все таки.
TarasBer
14.11.2012 14:18
> прошу прощения, но я не понял вопроса. Что я имел ввиду под чем?
Бинарное дерево зачем? Что вы собрались делать с именно бинарным деревом?
> Мне для написания парсера было достаточно бинарного дерева
> а еще и поле, указывающее на список деревьев
И какое же оно бинарное?
Цитата(TarasBer @ 14.11.2012 10:18)
Бинарное дерево зачем? Что вы собрались делать с именно бинарным деревом?
еще не сильно разобрался в данной теме, но думаю что с помощью бинарного дерева мне надо создать как бы синтаксический анализатор
TarasBer
14.11.2012 20:34
Цитата(marwell @ 14.11.2012 15:35)
но думаю что с помощью бинарного дерева мне надо создать как бы синтаксический анализатор
Как?
Цитата(TarasBer @ 14.11.2012 16:34)
Как?
ну нет, так нет. Значит нужно не бинарное дерево?
TarasBer
15.11.2012 13:38
Нужно прежде чем слова произвонсть, хотя бы примерно прикидывать, насколько и как оно применимо к задаче.
как то слышал от кого то (не помню конкретно), что такое можно сделать с помощью двоичных деревьев. Вспомнил про это, решил загуглить, нашел вот это
pdf-файл (надеюсь тут можно приводить ссылки на сторонние сайты). Мельком пройдясь по содержанию, прочел это
Цитата
4. Модуль № 4. Бинарные деревья разбора выражений и деревья общего вида
вот и подумал что это про то что мне нужно
I think you hit a bullseye there fleals!
I was struck by the honesty of your psotnig
You keep it up now, undersantd? Really good to know.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста,
нажмите сюда.