Распознавание математических выражений, с помощью обратной польской записи |
1. Заголовок или название темы должно быть информативным !
2. Все тексты фрагментов программ должны помещаться в теги [code] ... [/code] или [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ" и используйте ПОИСК !
4. НЕ используйте форум для личного общения!
5. Самое главное - это раздел теоретический, т.е. никаких задач и программ (за исключением небольших фрагментов) - для этого есть отдельный раздел!
Распознавание математических выражений, с помощью обратной польской записи |
marwell |
8.11.2012 14:29
Сообщение
#1
|
Бывалый Группа: Пользователи Сообщений: 198 Пол: Мужской Репутация: 1 |
доброго времени суток
хочу реализовать распознавание математических выражений и формул в введенной строке. Например, пусть строковая переменная s:='sin(x)+x-5*sqrt(x)', а мне надо построить ее график. Вопрос: можно ли реализовать это с помощью обратной польской записи? |
IUnknown |
10.11.2012 16:09
Сообщение
#2
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
На форуме уже выкладывались решения для подобных задач. Можешь поискать по слову "интерпретатор". Я предлагал для таких вещей строить дерево разбора, поскольку при использовании ОПЗ у тебя будет препятствие: сложно будет реализовать и вычисление арифметических операций, и вычисление функций одной/нескольких переменных.
|
TarasBer |
10.11.2012 16:18
Сообщение
#3
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
сложно будет реализовать и вычисление арифметических операций, и вычисление функций одной/нескольких переменных. Дело не в количестве, а в том, что оно не определено. Пихать вместо с функцией ещё и число аргументов? Ну так себе решение... Ещё проблема с ленивыми операторами, типа iff. В польской записи их как реализовать? Как в польской записи делать оптимизации, заменять ветки, состоящие из констант, на результат выражения? -------------------- |
marwell |
10.11.2012 19:44
Сообщение
#4
|
Бывалый Группа: Пользователи Сообщений: 198 Пол: Мужской Репутация: 1 |
значит забыть про ОПЗ и изучать дерево разбора?
планировалось, что функции у меня должны быть только одной переменной |
TarasBer |
11.11.2012 20:27
Сообщение
#5
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
Я бы сделал дерево разбора.
Да, с ним могут быть вопросы, как хранить вершины, чтобы корректно удалить в случае чего. Самый простой и безотказный способ - все новые вершины дерева регистрировать в отдельном списке. При удалении дерева просто пробегаться по этому списку. В процессе преобразования дерева будет много ненужных, мёртвых вершин, но так как они есть в списке, то память не утечёт. Ну и есть вдруг окажется, что лишние вершины занимают слишком много оперативы, то можно сделать отдельный проход по дереву в конце, чтобы сразу убрать ненужные вершины (мне так пришлось делать ради того, чтобы в самом конце расход памяти был нормальный и не лагало, хотя необходимост как бы и нету). -------------------- |
marwell |
12.11.2012 11:41
Сообщение
#6
|
Бывалый Группа: Пользователи Сообщений: 198 Пол: Мужской Репутация: 1 |
ясно, спасибо
|
marwell |
12.11.2012 17:17
Сообщение
#7
|
Бывалый Группа: Пользователи Сообщений: 198 Пол: Мужской Репутация: 1 |
тут годится бинарное дерево? я правильно понял?
|
TarasBer |
13.11.2012 10:09
Сообщение
#8
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
Почему бинарное? А если операция принимает не два аргумента?
-------------------- |
marwell |
13.11.2012 13:56
Сообщение
#9
|
Бывалый Группа: Пользователи Сообщений: 198 Пол: Мужской Репутация: 1 |
Почему бинарное? А если операция принимает не два аргумента? хм, значит, не то. Можно тогда ссылку на литературу подходящую? или хотя бы по каким запросам искать? По запросу "интерпретатор" на форуме про дерево разбора не нашел. Или же мне достаточно информации вообще про деревья и способы работы с ними? |
TarasBer |
13.11.2012 14:09
Сообщение
#10
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
А что вы тогда имели в виду?
-------------------- |
marwell |
13.11.2012 14:16
Сообщение
#11
|
Бывалый Группа: Пользователи Сообщений: 198 Пол: Мужской Репутация: 1 |
прошу прощения, но я не понял вопроса. Что я имел ввиду под чем?
|
IUnknown |
13.11.2012 14:48
Сообщение
#12
|
a.k.a. volvo877 Группа: Пользователи Сообщений: 1 013 Пол: Мужской Репутация: 627 |
Цитата А если операция принимает не два аргумента? Например? Какие операции являются тернарными или выше? Унарные и бинарные легко обрабатываются бинарным деревом.Мне для написания парсера было достаточно бинарного дерева, но вот в узлах своих оно хранило не только токен (собственно, операция, которая будет производиться, или функция, которая будет вычисляться) и 2 дерева-потомка (операнды), а еще и поле, указывающее на список деревьев. Этим решался вопрос с функциями от любого числа переменных (просто в список добавлялись деревья, представляющие собой аргументы функции, любое их количество. С функциями от 1 до 8 аргументов работало запросто). Можно обойтись и без доп. поля, но с приведениями типов или вариантными записями. |
Krjuger |
13.11.2012 20:53
Сообщение
#13
|
Профи Группа: Пользователи Сообщений: 652 Пол: Мужской Реальное имя: Алексей Репутация: 20 |
Извиняюсь, если лезу, но вроде как условная дизъюнкция в мат. логике является тернарной.
Хотя я уверен, что для ТС подобный функционал не нужен, но все таки. |
TarasBer |
14.11.2012 10:18
Сообщение
#14
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
> прошу прощения, но я не понял вопроса. Что я имел ввиду под чем?
Бинарное дерево зачем? Что вы собрались делать с именно бинарным деревом? > Мне для написания парсера было достаточно бинарного дерева > а еще и поле, указывающее на список деревьев И какое же оно бинарное? -------------------- |
marwell |
14.11.2012 15:35
Сообщение
#15
|
Бывалый Группа: Пользователи Сообщений: 198 Пол: Мужской Репутация: 1 |
|
TarasBer |
14.11.2012 16:34
Сообщение
#16
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
но думаю что с помощью бинарного дерева мне надо создать как бы синтаксический анализатор Как? -------------------- |
marwell |
14.11.2012 16:54
Сообщение
#17
|
Бывалый Группа: Пользователи Сообщений: 198 Пол: Мужской Репутация: 1 |
|
TarasBer |
15.11.2012 9:38
Сообщение
#18
|
Злостный любитель Группа: Пользователи Сообщений: 1 755 Пол: Мужской Репутация: 62 |
Нужно прежде чем слова произвонсть, хотя бы примерно прикидывать, насколько и как оно применимо к задаче.
-------------------- |
marwell |
16.11.2012 18:19
Сообщение
#19
|
Бывалый Группа: Пользователи Сообщений: 198 Пол: Мужской Репутация: 1 |
как то слышал от кого то (не помню конкретно), что такое можно сделать с помощью двоичных деревьев. Вспомнил про это, решил загуглить, нашел вот это pdf-файл (надеюсь тут можно приводить ссылки на сторонние сайты). Мельком пройдясь по содержанию, прочел это
Цитата 4. Модуль № 4. Бинарные деревья разбора выражений и деревья общего вида вот и подумал что это про то что мне нужно |
Holland |
19.11.2012 13:01
Сообщение
#20
|
Гость |
I think you hit a bullseye there fleals!
|
Текстовая версия | 28.09.2024 7:14 |