Помощь - Поиск - Пользователи - Календарь
Полная версия: Распознавание математических выражений
Форум «Всё о Паскале» > Pascal, Object Pascal > Теоретические вопросы
marwell
доброго времени суток
хочу реализовать распознавание математических выражений и формул в введенной строке. Например, пусть строковая переменная s:='sin(x)+x-5*sqrt(x)', а мне надо построить ее график. Вопрос: можно ли реализовать это с помощью обратной польской записи?
IUnknown
На форуме уже выкладывались решения для подобных задач. Можешь поискать по слову "интерпретатор". Я предлагал для таких вещей строить дерево разбора, поскольку при использовании ОПЗ у тебя будет препятствие: сложно будет реализовать и вычисление арифметических операций, и вычисление функций одной/нескольких переменных.
TarasBer
Цитата(IUnknown @ 10.11.2012 16:09) *
сложно будет реализовать и вычисление арифметических операций, и вычисление функций одной/нескольких переменных.

Дело не в количестве, а в том, что оно не определено. Пихать вместо с функцией ещё и число аргументов? Ну так себе решение...
Ещё проблема с ленивыми операторами, типа iff. В польской записи их как реализовать?
Как в польской записи делать оптимизации, заменять ветки, состоящие из констант, на результат выражения?
marwell
значит забыть про ОПЗ и изучать дерево разбора?
планировалось, что функции у меня должны быть только одной переменной
TarasBer
Я бы сделал дерево разбора.
Да, с ним могут быть вопросы, как хранить вершины, чтобы корректно удалить в случае чего.

Самый простой и безотказный способ - все новые вершины дерева регистрировать в отдельном списке. При удалении дерева просто пробегаться по этому списку. В процессе преобразования дерева будет много ненужных, мёртвых вершин, но так как они есть в списке, то память не утечёт. Ну и есть вдруг окажется, что лишние вершины занимают слишком много оперативы, то можно сделать отдельный проход по дереву в конце, чтобы сразу убрать ненужные вершины (мне так пришлось делать ради того, чтобы в самом конце расход памяти был нормальный и не лагало, хотя необходимост как бы и нету).
marwell
ясно, спасибо
marwell
тут годится бинарное дерево? я правильно понял?
TarasBer
Почему бинарное? А если операция принимает не два аргумента?
marwell
Цитата(TarasBer @ 13.11.2012 10:09) *

Почему бинарное? А если операция принимает не два аргумента?

хм, значит, не то. Можно тогда ссылку на литературу подходящую? или хотя бы по каким запросам искать? По запросу "интерпретатор" на форуме про дерево разбора не нашел.
Или же мне достаточно информации вообще про деревья и способы работы с ними?
TarasBer
А что вы тогда имели в виду?
marwell
прошу прощения, но я не понял вопроса. Что я имел ввиду под чем?
IUnknown
Цитата
А если операция принимает не два аргумента?
Например? Какие операции являются тернарными или выше? Унарные и бинарные легко обрабатываются бинарным деревом.

Мне для написания парсера было достаточно бинарного дерева, но вот в узлах своих оно хранило не только токен (собственно, операция, которая будет производиться, или функция, которая будет вычисляться) и 2 дерева-потомка (операнды), а еще и поле, указывающее на список деревьев. Этим решался вопрос с функциями от любого числа переменных (просто в список добавлялись деревья, представляющие собой аргументы функции, любое их количество. С функциями от 1 до 8 аргументов работало запросто). Можно обойтись и без доп. поля, но с приведениями типов или вариантными записями.
Krjuger
Извиняюсь, если лезу, но вроде как условная дизъюнкция в мат. логике является тернарной.
Хотя я уверен, что для ТС подобный функционал не нужен, но все таки.
TarasBer
> прошу прощения, но я не понял вопроса. Что я имел ввиду под чем?

Бинарное дерево зачем? Что вы собрались делать с именно бинарным деревом?

> Мне для написания парсера было достаточно бинарного дерева
> а еще и поле, указывающее на список деревьев

И какое же оно бинарное?
marwell
Цитата(TarasBer @ 14.11.2012 10:18) *

Бинарное дерево зачем? Что вы собрались делать с именно бинарным деревом?

еще не сильно разобрался в данной теме, но думаю что с помощью бинарного дерева мне надо создать как бы синтаксический анализатор
TarasBer
Цитата(marwell @ 14.11.2012 15:35) *

но думаю что с помощью бинарного дерева мне надо создать как бы синтаксический анализатор

Как?
marwell
Цитата(TarasBer @ 14.11.2012 16:34) *

Как?

ну нет, так нет. Значит нужно не бинарное дерево?
TarasBer
Нужно прежде чем слова произвонсть, хотя бы примерно прикидывать, насколько и как оно применимо к задаче.
marwell
как то слышал от кого то (не помню конкретно), что такое можно сделать с помощью двоичных деревьев. Вспомнил про это, решил загуглить, нашел вот это pdf-файл (надеюсь тут можно приводить ссылки на сторонние сайты). Мельком пройдясь по содержанию, прочел это
Цитата
4. Модуль № 4. Бинарные деревья разбора выражений и деревья общего вида
вот и подумал что это про то что мне нужно
Holland
I think you hit a bullseye there fleals!
Pait
I was struck by the honesty of your psotnig
Abdo
You keep it up now, undersantd? Really good to know.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.