Распознавание математических выражений, с помощью обратной польской записи Опции

[marwell]

доброго времени суток
хочу реализовать распознавание математических выражений и формул в введенной строке. Например, пусть строковая переменная s:='sin(x)+x-5*sqrt(x)', а мне надо построить ее график. Вопрос: можно ли реализовать это с помощью обратной польской записи?

[IUnknown]

На форуме уже выкладывались решения для подобных задач. Можешь поискать по слову "интерпретатор". Я предлагал для таких вещей строить дерево разбора, поскольку при использовании ОПЗ у тебя будет препятствие: сложно будет реализовать и вычисление арифметических операций, и вычисление функций одной/нескольких переменных.

[TarasBer]

сложно будет реализовать и вычисление арифметических операций, и вычисление функций одной/нескольких переменных.

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

[marwell]

значит забыть про ОПЗ и изучать дерево разбора?
планировалось, что функции у меня должны быть только одной переменной

[TarasBer]

Я бы сделал дерево разбора.
Да, с ним могут быть вопросы, как хранить вершины, чтобы корректно удалить в случае чего.

Самый простой и безотказный способ - все новые вершины дерева регистрировать в отдельном списке. При удалении дерева просто пробегаться по этому списку. В процессе преобразования дерева будет много ненужных, мёртвых вершин, но так как они есть в списке, то память не утечёт. Ну и есть вдруг окажется, что лишние вершины занимают слишком много оперативы, то можно сделать отдельный проход по дереву в конце, чтобы сразу убрать ненужные вершины (мне так пришлось делать ради того, чтобы в самом конце расход памяти был нормальный и не лагало, хотя необходимост как бы и нету).

[marwell]

ясно, спасибо

[marwell]

тут годится бинарное дерево? я правильно понял?

[TarasBer]

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

[marwell]

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

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

[TarasBer]

А что вы тогда имели в виду?

[marwell]

прошу прощения, но я не понял вопроса. Что я имел ввиду под чем?

[IUnknown]

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

Например? Какие операции являются тернарными или выше? Унарные и бинарные легко обрабатываются бинарным деревом.

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

[Krjuger]

Извиняюсь, если лезу, но вроде как условная дизъюнкция в мат. логике является тернарной.
Хотя я уверен, что для ТС подобный функционал не нужен, но все таки.

[TarasBer]

> прошу прощения, но я не понял вопроса. Что я имел ввиду под чем?

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

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

И какое же оно бинарное?

[marwell]

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

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

[TarasBer]

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

Как?

[marwell]

Как?

ну нет, так нет. Значит нужно не бинарное дерево?

[TarasBer]

Нужно прежде чем слова произвонсть, хотя бы примерно прикидывать, насколько и как оно применимо к задаче.

[marwell]

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

4. Модуль № 4. Бинарные деревья разбора выражений и деревья общего вида

вот и подумал что это про то что мне нужно

[Holland]

I think you hit a bullseye there fleals!