Обратная польская запись, преобразование не туда, а обратно Опции

[ARV]

Уважаемые коллеги!

Ковыряюсь тут по своим надобностям с обратной польской записью выражений. Задача - сделать интерпретатор формул в собственный байт-код для последующего автоматического исполнения. Интерпретация польской записи хороша по быстродействию, и при хранении дает минимум накладных расходов памяти. Вроде с преобразованием текстовой строки в байт-код по "польски" разобрался, все получается. А вот с обратным преобразованием что-то туплю - не могу понять, как по польской записи восстановить наличие скобок в выражении.

может кто знает алгоритм преобразования обратной польской записи в обычное выражение со скобками?

[andrewlekar]

Думается мне, что обратная польская запись не имеет однозначного выражения в скобочной форме. Поэтому стоит задуматься, зачем вам обратное преобразование. Храните в обычной форме, преобразовывайте при интерпретации.

[ARV]

храню и исполняю я в польской, но ведь пользователю надо иной раз показать, что именно там харнится и исполняется? и показать надо в том виде, как он вводил.

[andrewlekar]

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

[ARV]

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

[ARV]

вот, кстати, на хабре нашел алгоритм: http://habrahabr.ru/post/147104/
только вот для МК с небольшим объемом ОЗУ алгоритм с динамическим выделением памяти - это не фонтан... и работа со строками тоже не очень хороша...

[XVR]

только вот для МК с небольшим объемом ОЗУ алгоритм с динамическим выделением памяти - это не фонтан... и работа со строками тоже не очень хороша...

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

Кстати, дерево можно использовать вместо ОПЗ и при вычислении (в интерпретаторе), вместо отдельного стека будет использоваться С'ный процедурный стек, а в остальном они совпадают.

[=AK=]

может кто знает алгоритм преобразования обратной польской записи в обычное выражение со скобками?

На Форте - в книге С.Н. Баранов, Н.Р. Ноздрунов — Язык Форт и его реализации

[ARV]

форт?! Си - наше все!

[kolobok0]

...алгоритм преобразования обратной польской записи в обычное выражение со скобками?

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

[Kopa]

форт?! Си - наше все!

Форт - это другое всё! (c хорошими, но изданными давно книгами)

[=AK=]

форт?! Си - наше все!

А в чем проблема-то? Пишите ядро Форта на С, а потом достраиваете нужную функциональность уже на Форте, компактно и эффективно. Разве вы не этого хотели? Иначе зачем бы вам было огород городить с обратной польской записью?

[ARV]

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

[XVR]

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

Я вам уже дал совет - сделать дерево, а не ОПЗ. Чем он вас не устраивает?

[ARV]

Я вам уже дал совет - сделать дерево, а не ОПЗ. Чем он вас не устраивает

я делаю интерпретатор собственного байт-кода. ОПЗ позволяет получить строго линейный байт-код, т.е. извлекаю байт за байтом и исполняю, не нужно передвигать указатели, помнить предыдущие состояния и т.п., как для дерева. получение ОПЗ из нативной формулы достаточно простое, я его уже реализовал. чем лучше дерево для интерпретации - не понимаю. возможно, был бы смысл в нем для интерпретации не формул, а именно языка более высокого уровня, с ветвлениями, подпрограммами, циклами и т.п., но даже и в этом не уверен.

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


спасибо за внимание.

[XVR]

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

Дерево может быть представлено в виде префиксной записи (ОПЗ - это постфиксная запись). Т.е. в том же линейном виде, без каких либо указателей и предыдущих состояний. Для вычисления (и печати) дерева применяется рекурсивная функция, т.е. если ваш CPU не накладывает ограничений на глубину стека, то префиксная запись однозначно лучше.

Выглядит это приблизительно так (пример):
Исходная формула: (10+20)*30
ОПЗ: 10 20 + 30 *
Префиксная форма: * (+) 10 20 30 (Скобки вокруг операции показывают наличие скобок, используется только для вывода, кодируется старшим битом)

Процедура вычисления (кусочек):

Код

char* position;
int eval()
{
int arg1, arg2;
switch(*position++ & 0x7F)
  {
    case '+': arg1=eval(); arg2=eval(); return arg1+arg2;
    case '*': arg1=eval(); arg2=eval(); return arg1*arg2;
    case 'I': /* constant */ arg1=*(int*)position; position+=sizeof(int); return arg1;
...
  }
}

Процедура печати (тоже кусочек)

Код

char* position;
void print()
{
char cmd=*position++;
int arg1;

if (cmd&0x80) printf("(");
switch(cmd & 0x7F)
  {
    case '+': print(); printf("+"); print(); break;
    case '*': print(); printf("*"); print(); break;
    case 'I': /* constant */ arg1=*(int*)position; position+=sizeof(int); printf("%d",arg1); break;
...
  }
if (cmd&0x80) printf(")");
}

[ARV]

хоть убейте, не понимаю, чем лучше префиксная запись. если в байт-код писать признак скобок для будущей "печати", то совершенно без разницы, что пре-, что пост-
вот на счет бита скобок - это хорошая идея, сразу бы ее подкинули - может, я б давно все сделал

[XVR]

хоть убейте, не понимаю, чем лучше префиксная запись. если в байт-код писать признак скобок для будущей "печати", то совершенно без разницы, что пре-, что пост-

Отнюдь. пост- вообще плохо предназначенна для печати (что со скобками, что без). В процессе печати придется хранить формируемую строку как минимум для одного операнда (ее нельзя сразу вывести). В случае пре- никакие строки вообще хранить не надо - все выводится 'на лету'.

Посмотрите еще раз в мой код - там никаких буферов нет (ни динамических ни статических)

[_Ivana]

храню и исполняю я в польской, но ведь пользователю надо иной раз показать, что именно там харнится и исполняется? и показать надо в том виде, как он вводил.

Имхо, "как он вводил" - не надо. А перевести это в нормальную инфиксную запись и показать - можно. Посмотрите вот здесь, как альфа преобразует введенный бред в строке поле "инпут".

[редактор]

А если хранить две записи - одну для пользователя, другую, уже преобразованную - для вычислений.