- 001
- 002
- 003
- 004
- 005
- 006
- 007
- 008
- 009
- 010
- 011
- 012
- 013
- 014
- 015
- 016
- 017
- 018
- 019
- 020
- 021
- 022
- 023
- 024
- 025
- 026
- 027
- 028
- 029
- 030
- 031
- 032
- 033
- 034
- 035
- 036
- 037
- 038
- 039
- 040
- 041
- 042
- 043
- 044
- 045
- 046
- 047
- 048
- 049
- 050
- 051
- 052
- 053
- 054
- 055
- 056
- 057
- 058
- 059
- 060
- 061
- 062
- 063
- 064
- 065
- 066
- 067
- 068
- 069
- 070
- 071
- 072
- 073
- 074
- 075
- 076
- 077
- 078
- 079
- 080
- 081
- 082
- 083
- 084
- 085
- 086
- 087
- 088
- 089
- 090
- 091
- 092
- 093
- 094
- 095
- 096
- 097
- 098
- 099
- 100
-- Few Scum
import Data.Char
import Text.Read
import Control.Applicative
import Data.Ratio
import Numeric
import Data.List
import Data.Maybe
data Token
=TLetter Char
|TNumf Rational
|TOp Char
|LBrace
|RBrace
deriving (Show, Eq)
data Expr
=Letter Char
|Numf Rational
|Op Char Expr Expr
|Diff Expr
instance Show Expr where
show (Letter c) = [c]
show (Op c el er) = '(' : show el ++ ')' :
c : '(' : show er ++ ")"
show (Numf v) = show $ toDouble v
show (Diff e) = '(' : show e ++ ")'"
toDouble r = fromRational r :: Double
readUnsignedRationalMaybe f = getParseResult $ parseValue f where
parseValue f = {- readSigned -} readFloat f :: [(Rational, String)]
getParseResult [(value, "")] = Just value
getParseResult _ = Nothing
-- Разбиваем строку на элементы, возаращает перевернутый список токенов
tokenize "" = Nothing
tokenize sourceExpressionString = tok [] sourceExpressionString where
tok [] (c:s)
| c == '-' = tok [TOp '-', TNumf 0] s
tok r@(LBrace:_) (c:s)
| c == '-' = tok (TOp '-':TNumf 0:r) s
tok r (c:s)
| c == '(' = tok (LBrace:r) s
| c == ')' = tok (RBrace:r) s
| isLetter c = tok (TLetter c:r) s
| isOperation c = tok (TOp c:r) s
| isNumber c = parseNumf r (c:s)
tok r "" = Just r
tok resultParsedTokens sourceExpressionString = Nothing
isOperation = (`elem` "+-*/")
isNumf c = isNumber c || c == '.'
parseNumf r s = maybeNumber >>= makeResult where
(numberString, tail) = span isNumf s
maybeNumber = readUnsignedRationalMaybe numberString--readMaybe numberString
makeResult number = tok (TNumf number:r) tail
-- Дерево выражений из списка токенов
parse reversedTokens = reversedTokens >>= makeTree where
priorityOps = ["+-","/*"]
subExpr = splitIntoOperationAndSubExpressions
splitIntoOperationAndSubExpressions reversedTokens =
id =<< find isJust (map (findOp reversedTokens [] 0) priorityOps)
findOp (LBrace:_) _ 0 _ = Nothing -- dont checked on left expression, probably can safety removed
findOp (RBrace:l) r b ops = findOp l (RBrace:r) (b+1) ops
findOp (LBrace:l) r b ops = findOp l (LBrace:r) (b-1) ops
findOp (TOp c:l) r 0 ops
| c `elem` ops = Just (c, l, reverse r)
| otherwise = findOp l (TOp c:r) 0 ops
findOp leftSubExpression [] b operationsForFind
| b > 0 = Nothing
findOp (c:l) r b ops = findOp l (c:r) b ops
findOp [] rightSubExpression braceAmount operationsForFind = Nothing
makeTree reversedTokens = mt reversedTokens $ subExpr reversedTokens
mt t@(RBrace:tt) Nothing
| last t == LBrace = mt (init tt) $ subExpr (init tt)
mt [TLetter v] Nothing = Just $ Letter v
mt [TNumf v] Nothing = Just $ Numf v
mt _ Nothing = Nothing
mt _ (Just (o, l, r)) = makeOperationExpression leftExpressionTree rightExpressionTree o where
leftExpressionTree = mt l $ subExpr l
rightExpressionTree = mt r $ subExpr r
makeOperationExpression = moe
moe Nothing _ _ = Nothing
moe _ Nothing _ = Nothing
moe (Just leftExpressionTree) (Just rightExpressionTree) operation = Just $ Op operation leftExpressionTree rightExpressionTree
-- Простейшее упрощение выражений
firstSimplify e = simplifyTreeHeightTimes <$> e where
stepSimplify = fs
fs (Op '*' e (Numf 1)) = e
fs (Op '*' (Numf 1) e) = e
fs (Op '+' e (Numf 0)) = e
fs (Op '+' (Numf 0) e) = e
fs (Op '/' e (Numf 1)) = e
fs (Op '-' e (Numf 0)) = e
fs (Op '*' (Numf 0) _) = Numf 0
fs (Op '*' _ (Numf 0)) = Numf 0
fs (Op '/' (Numf 0) _) = Numf 0
fs (Op '/' (Letter l) (Letter r))
| l == r = Numf 1
fs (Op '-' (Letter l) (Letter r))
Новая Специальная Олимпиада объявляется открытой.
https://ideone.com/Bottp0
Реализовать поиск производной по выражению на любом языке. У кого получится компактнее, правильнее и больше функционала, тот и победил. Заявлять кандидата в победители (код и его автора) можно несколько раз если код улучшил или написал на другом языке. Призов, кроме почета и приятного времяпрепровождения, - не будет
Если кто-то что-нибудь поломает, то я буду очень рад.
Пока упрощение не работает на полную катушку и из функций производных только +-*/
Мой друг обещает ещё версию на крестах подогнать.
Follow us!
Походу, надо пожелать ему удачи. У меня строк на 1000+ подобный парсер для лаб был... Правда там можно было регать новые операторы, не трогая основной код.
И более качественное упрощение выражений.
Но что-то мне подсказывает, что он так может ничего и не выдать, если не остепенится и не выкатит первую версию с минимальным механизмом упрощения выражений и с минимумом операций.
А насчет лишних скобок: Это можно реализовать не передавай дополнительные параметры между функциями? Ибо хочется через стандартную виртуальную функцию show делать, но ты прав, это уже ребячество. Можно и отдельную функцию завести для вывода, а потом вызывать ее из show
А что там сложного? Просто мусорных нод много генерится, но для простых случаев (типа x^5 или 3^x) они потом отлично съедаются упрощением.
> не передавай дополнительные параметры между функциям
Да можно, но один фиг придётся подглядывать в дочерние или родительские узлы.
Я не считаю, что упрощение достаточно тривиальная задача. Иной раз сродни общета ходов в шахматах. Иной раз надо аст разростить, чтобы оно в итоге все посокрощалось. У меня так firstSimplify пока весьма туп и недотягивает даже до школьника с логарифмической линейкой.
> А что там сложного?
Ну я так вспомнить сходу формулу общего вида для степенных функций не могу. Там экспоненты были и простые степенные функции типа квадратов, кубов и более высоких порядков.
Конечно я пока таблицу не гуглил и может там что-то подобное было, но без гуглежки не вспомню как найти производную f(x)^g(x). Там небось еще и логарифмы всякие появятся.
Там будет два слагаемых. В первом предполагаем, что f(x) = const, во втором — что g(x) = const.
А вообще f(x)^g(x) = exp(g(x) * ln(f(x))) [с некоторыми ограничениями на область значений f(x)],
поэтому (f(x)^g(x))' = exp(g(x) * ln(f(x))) * [g(x) * ln(f(x))]' =
= exp(g(x) * ln(f(x))) * [g'(x) * ln(f(x)) + g(x) * f'(x) / f(x)] =
= f(x) ^ g(x) * [g'(x) * ln(f(x)) + g(x) * f'(x) / f(x)] =
= f(x) ^ g(x) * ln(f(x)) * g'(x) + g(x) * f(x) ^ (g(x) - 1) * f'(x)
Что совпадает с тем, что бы мы получили, если бы предположили, что там будет два слагаемых: в первом предполагаем, что f(x) = const, во втором — что g(x) = const.
У меня самая жопа была из-за разной ассоциативности - АСТ почти перебором строилось, чтобы ловить все неоднозначности и ругаться на них. Зато парсило даже говно, в котором операторы поналеплены без пробелов, типа a--b => a - (-b).
Numerically computes the derivative of f, f′(x), or generally for an integer n≥0, the n-th derivative f(n)(x).
Печаль, я уж подумал, что действительно как-то хитро парсит, и можно так многие функции аналитически продифференцировать.
Чёрт, я не спал, не пил, не ел, писал код. laMer007, демон-искуситель, зачем?
На полноценное участие в специальной олимпиаде не претендую, т.к. обычно многословен в коде и жизни, а также лень запиливать все фичи. Просто демонстрация решения.
Работает для функции с явно указанным списком аргументов. Если тело функции просто возвращает выражение с переменными, целыми числами, круглыми скобками и бинарными операторами *+-/, возвращается функция, вычисляющая аналитическую производную (выражение по своему желанию оптимизирует жс-движок). Иначе - функция, которая численно.
Использование: diff(жс-функция, строка с переменной или номер аргумента, дельта аргумента для численного вычисления)
Возвращает жс-функцию или бросает исключение.
Всегда приклонялся перед людьми, пищущими парсер на каких-то регулярках. Как это возможно? Но имхо поддерживать код будет не просто. Хотя наверное мой код на хаски тоже никто ни осилил бы в поддержку
Рассказывай как делал, потому что я тут даже ивал и getElementById вижу.
Если мне захочится парсить ввод юзера, то придется сначала его преобразовать в лямбду на джс?
Говнокод+нет поддержки крайних случаев
> Всегда приклонялся перед людьми, пищущими парсер на каких-то регулярках. Как это возможно?
а) повторное применение регулярок. Регулярки, вызванные в цикле/рекурсивной функции уже поднимаются до КС-грамматик
б) объединение сущностей в одну
Вот я сначала (41-42 строки) парсил штуки вида (a, b, c) => expression; и function (a,b,c) { return expression; }. Они описываются регулярными грамматиками. Дальше работал со списком аргументов и выражением.
> Если мне захочится парсить ввод юзера, то придется сначала его преобразовать в лямбду на джс?
Я вырывал это выражение из жс, затем его преобразовывал, затем генерировал функцию (вот тут и нужен eval). Поэтому можно обойтись без ЖС (убрать 40-43) и задать в строке 44 свои args, expr (expr надо без пробелов).
Собственно, можно оставить только diff(parseExpr(expr), 1): https://jsfiddle.net/kmvohnb4/1/ Численное дифференцирование тут выпилилось, в исходной версии оно описано в строках 51-57, сразу создаёт функцию.
> Рассказывай как делал, потому что я тут даже ивал вижу.
Алгоритм работы (в общем, я в этом порядке и писал):
1. Выделяем тело функции и аргументы (40-44)
2. Парсим (функция parseExpr).
2.1. Выделяем токены. Регулярка в строке 5 выделяет токены.
2.2. В цикле, пока есть изменения, несколько раз проходим по строке и сворачиваем токены
Строка 15 - проверка штук вида left_bracket A right_bracket; Строка 20 - проверка штук вида A op B
3. Рекурсивно обходим получившееся AST (функция diff на строке 30) и генерируем выражение (оптимизации выражения нет)
4. Генерируем функцию, имея список аргументов и тело
5. Если не получилось, выполняем численное дифференцирование. $$df на строке 52 вызывает f с разными значениями аргумента номер id. eval тут нужен для того, чтобы сохранить список аргументов, чтобы при повторном вызове diff можно было понять, по какому аргументу дифференцировать.
Вот отсюда вся краткость (помимо неоптимального брутфорс-парсинга)
Остальное - красиво, на языках без паттерн-матчинга были бы портянки говн...
> fs (Diff e) = fs e
надо
fs (Diff e) = Diff $ fs e.
Теряет знак ' производной.
Еще был тонкий момент с паттерн матчингом, пока я рациональные числа вместо флоатов не пихнул - не упрощало часто, ну там 0 с 0 не матчился например и тд. Вот в крестах этого типа нет и это уже проблема
Еще в крестах конечно дико не хватает алгебраических типов и паттернаматчинга. Почему страус не может запилить очевидные и важные вещи?
Пропозиция есть http://tinyurl.com/z5fzyfd
По номеру аргумента даже нативную фигню может
Но так любой дурак сможет.
Это несложно. Производных от jquery бесконечно много, надо определиться только со значением аргумента.
Теоретически jQuery'(google)=angular
http://www.google.com.ua/search?q=jquery+derived+framework
А мне вот теперь в свой калькулятор производные запиливать
Ну и ещё потом парсер требует поиска операций +-*/ среди токинов в обратном порядке. Ну то есть я не смогу в парсере итерировать по списку токенов удобно и легко, если там список токенов в прямом порядке, поэтому мне в двойне повезло, что токинизатор генерирует список токенов в обратном порядке.
Почему парсер требует обратного поиска операций в списке токенов? Ну потом у чтобы потом операции в правильном порядке вычислялись при сворачивании дерева выражений при вычислении. Иначе же будет неправильный порядок вычисления например в случае a-b-c (a-b должно оказаться в листах дерева в данном случае)
А порядок вычислений зависит от ассоциативности операторов. Твой парсер всосет на правоассоциативном операторе степени ^.
Однострочник на Wolfram Language катит?
Можно было писать такой код:
http://www.gamedev.ru/flame/forum/?id=185983&page=7#m91
(если кому интересно)
Псевдо-Глобалисты самоназванного “Нового Мирового Порядка” уже подготовили всё для коллапса доллара. Цель – обнулить, то есть, обворовать через ФОРС МАЖОР долларово-валютные резервы России и Китая. Чтобы получилось так, что Россия отдавала им свои ресурсы десятилетия бесплатно, а Китай пахал на них десятилетия бесплатно. Уже создана новая ГЛОБАЛЬНАЯ резервная валюта — СПЗ (Специальные Права Заимствования / SDR – The Spec
По размеру не оптимизировал. Да и по красоте не очень.
Можно было бы попробовать считерить и переопределить операторы чтоб не приходилось ничего парсить, но я ориентировался на то чтоб потом на паскале аналогичный код использовать.
Зато есть функции, степени и всякое такое. Правда про правоассоциативность степени я забыл.
> Challenge accepted
Плохо accepted пока
А слабо найти полином с целыми коэффицентами P(x): P(e) = 0?
AFAIK, неопределённый интеграл большинства функций, записанных в виде суперпозиции элементарных, не выражается через элементарные функции.
очень прозрачно
Или тут ещё на этапе компиляции оптимизация выражений в некоторых случаях добавлена?
То же самое сейчас Сатанинсксо-Сионисткий альянс проделывает по отношению к Исламу. ИГИШ (ИГИЛ, ИГ) — это грандиозное шоу, разыгрываемое агентами Моссада по дискредитации Ислама, и заправляемое “главой Исламского Государства” Абу Бахр Аль-Багдади, кто, на самом деле, является агентом Моссада Шимоном Эллиотом.
Цель Сатанинско-Сионисткого Альянса — уничтожить суверенные государства и суверенные валюты, и установить глобальное господство одной нации в двуклассовом обществе рабов и господ. Недаром, банковская элита исповедует Талмуд — глобальный геноцид Гое
Сканер памяти обнаружил вредоносную программу! Очень опасно работать на компьютере, в памяти которого активен вирус. Рекомендуется назначить загрузочное сканирование.
Репрессии в СССР и голодомор лежат на совести Иудо-Троцкистов, специально подготовленных и засланных пароходом из Нью-Йорка Сионисткими банкирами Нью-Йорка и Сити оф Лондон. Никакого отношения эти зверства не имеют к светлым идеалам свободы, равенства и братства, которые лежали в основе СССР и которые лежат в основе Православного Христианства (сейчас уже исковерканные Институционной Церковью, подмятой под себя мировым Сионизмом).
Ту же компанию по дискредитации Сатанинско-Сионисткий альянс провёл и по отношению к Арийским народам и Арий