Математический парсер

[shmalex]

Всем ПРЕВЕД.
нужно написать матемитический парсер т.е. - входные данные 12+45*548+54-(45+34*34+(2/8)-4)*10 а на выходе будет ... эээ.. ну в общем либо ошибка либо число. был реализован один алгоритм.... меня подвели отрицательные числа т.е. после резолва части строки получалось ...12*-10.. в общем пошело дописалование когда и все посыпалось... я думаю что просто начал не с того конца... ну вот. у кого какие предложения

[NKolea]

Помоему такой пример у меня завалялся где-то! Если хочешь могу на мыло послать исходник на С#/С++... Помоему этот пример я встретил в книжке "Керниган и Ритчи" . Можешь в инете и поискать.

[shmalex]

shmalex,
высылай. мыло в личных данныхЪ

[DiMoN]

shmalex,
[off]нет у тебя мыла в личных данных![/off]

[shmalex]

теперь есть

[NKolea]

Я выслал тебе исходник на мыло... он слишком большой чтоб в сообщения его кидать. Я сам его потестил и всё работает отлично! =)

[sadman]

NKolea,
кинь и мне, плз. очень интересно посмотреть. сам брался писать, но не довйл дело до конца. ящик в личке

[shmalex]

зверская штука на первый взгляд... хочеться свой добацать... либо этот переносить на C#
подход интересный, у меня идет более очевидный парс:
сначало разметить все скобки, найти самую глубокую.
в ней найти максимальный приоритет операции
рекурсивно разрешить операцию т.е. если в строке есть 2*2*5*4 нужно все их разрешить разом поличуть 80.
и так до тех пор пока будет НЕ найденна операция.
к томуже парс идет в самой страке т.е. 2+5+8*2 после первой операции переходит в 2+5+16 после в торой 23. решение найденно.
+вспомогательный фции для поиска чисел операции и т.п.
дальше хотелось бы произвести сравнительный анализ по производительности... но думаю, что мой метод уже здал позиции. .
у кого какие идеи... а может улучшить предложанный... если он конечно в этом нужндается

[NKolea]

shmalex, алгоритм Богатырёва сначало превращает математическое выражение в польскую запись по методу приоритетов. Потом рекурсивно рассматривается польская запись и выполняются операции над числами.
Пример:
Математическое выражение: (a+b)*c
Польская запись этого выр-я: a b + c *
Этот алгоритм используется в компиляторах и в скриптовых языках. Ну а в твоём методе я не вижу ничего нового, да и к тому ты ещё больше усложнил задачу тем самым увеличивая размер кода программы, производительность наоборот снизится. Какая разница когда будет выполняться сложение? Всёравно оно будет производиться...

sadman, я почему-то не вижу твоё мыло в инфе...

Я бы вам всю книжку Богатырёва скинул если-б не по дайлапу...
Но если будет возможность пошлю вам на мыло... Пока тока маленького размера файлы могу скинуть!

[sadman]

NKolea,
eugen87k@inbox.ru

[sadman]

NKolea,
спасибо.
Хорошая штука. Захотелось свой написать.

[shmalex]

NKolea,
Да, колесо уже изобрели, осталось его делать "круглее и круглее" спосибо за исходник.

[off]добавлено спустя 4 часа 11 минут:[/off]

т.е. расширить алгоритм чтобы ,к примеру, правельно парсилось выражнение -1*2. и не самое сложно - дробнае числа.