Версия для печати темы

Автор: marwell 8.11.2012 18:29

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

Автор: IUnknown 10.11.2012 20:09

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

Автор: TarasBer 10.11.2012 20:18

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

Автор: marwell 10.11.2012 23:44

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

Автор: TarasBer 12.11.2012 0:27

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

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

Автор: marwell 12.11.2012 15:41

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

Автор: marwell 12.11.2012 21:17

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

Автор: TarasBer 13.11.2012 14:09

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

Автор: marwell 13.11.2012 17:56

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

Автор: TarasBer 13.11.2012 18:09

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

Автор: marwell 13.11.2012 18:16

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

Автор: IUnknown 13.11.2012 18:48

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

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

Автор: Krjuger 14.11.2012 0:53

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

Автор: TarasBer 14.11.2012 14:18

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

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

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

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

Автор: marwell 14.11.2012 19:35

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

Автор: TarasBer 14.11.2012 20:34

Как?

Автор: marwell 14.11.2012 20:54

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

Автор: TarasBer 15.11.2012 13:38

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

Автор: marwell 16.11.2012 22:19

как то слышал от кого то (не помню конкретно), что такое можно сделать с помощью двоичных деревьев. Вспомнил про это, решил загуглить, нашел вот это http://www.ict.edu.ru/ft/004893/rsu646.pdf (надеюсь тут можно приводить ссылки на сторонние сайты). Мельком пройдясь по содержанию, прочел это

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

Автор: Holland 19.11.2012 17:01

I think you hit a bullseye there fleals!

Автор: Pait 19.11.2012 19:34

I was struck by the honesty of your psotnig

Автор: Abdo 20.11.2012 3:45

You keep it up now, undersantd? Really good to know.