Здравствуйте, frёёm, Вы писали:
ёё>Товаристчи... ёё>подскажите как отсортировать мат. выражение.
ёё>тоесть у меня выражение ёё>
ёё> !9*8+7>6 которое нужно привести к 6>7+8*!9
ёё>
ёё>Привести нужно так я вычисляю его через полиз...соответственно с конца...
ёё>Тоесть у меня есть 2 массива...один с числами другой с оперциями... ёё>нужно его перевести вот таким образом ёё>
Ну как бы...
я просто выражения вычисляю при помоши ПОЛьской Инверсной Записи.
Вот.
Соответсвенно работает всё так...ко мне приходит стригна с выражением
типа
"!9*8+7>6"
я его долго парсю через конечный автомат...в итоге получаю два стека (массива)
операций и числов...
9 8 7 6
! * + >
и потом я начинаю вычислять...
Дёргаю из стека оперцаций > дёргаю для неё два числа...и их сравниваю...получаеться 7>6=true которую и пишу в стек числов вместо выдернутых.
9 8 true
! * +
потом я опять делаю тоже...у меня получаеться 8 + true и он мне говорит что, незя складывать 8 и true и это правильно =))
Человек когда видит выражение вида
"!9*8+7>6"
он начинает догадываться что на выходе должна быть булевская константа...
Но вот прога моя этого не понимает...
Соответственно я хотел ввести промежуточный этап между парсингом и вычислением...сортировку, дабы
9 8 7 6
! * + >
превратить вот в это...
6 7 8 9
< + * !
ибо так оно вычислиться правильно...но проблема тут такая...
9 8 7 6
! * + >
допустим я просматриваю стэк операций как массив с начала...
выкавыриваю от туда ! u * у отрицания приоритет больше след-но оно должно выполняться ранее (ближе к концу) след-но меняем местами...но как правильно менять местами опернды ???
Ни что в жизни ни даёться так просто как... хотелось бы...
ёё>Соответсвенно работает всё так...ко мне приходит стригна с выражением ёё>типа
"!9*8+7>6"
ёё>я его долго парсю через конечный автомат...в итоге получаю два стека (массива) ёё>операций и числов...
Понятно, ты просто неправильно реализовываешь разбор и вычисление. Почитай тут, например http://en.wikipedia.org/wiki/Reverse_Polish_notation
Там достаточно подробные объяснения и ссылки на реализации. Еще надо будет правильно расставить приоритеты операциям.
Да, ты меня раскусил я не её использовал...я породию на неё использовал...
Но прога то работает...и считает правильно...если правильно раставленный операции...
Мне нужно просто отсортировать...перекраивать всю прогу (тем более) рабочее под правильный полиз
честно говорю не охота...
не ужели ни как нельзя всё отсортить на уровне массивов
Ни что в жизни ни даёться так просто как... хотелось бы...
Здравствуйте, frёёm, Вы писали:
ёё>я просто выражения вычисляю при помоши ПОЛьской Инверсной Записи. ёё>Вот.
ёё>Соответсвенно работает всё так...ко мне приходит стригна с выражением ёё>типа
"!9*8+7>6"
ёё>я его долго парсю через конечный автомат...в итоге получаю два стека (массива) ёё>операций и числов...
Ты не с того конца начал.
У каждого оператора есть приоритет... поэтому, получив очередной оператор, нужно решить — запихать его в стек либо вычислить уже имеющиеся.
Здравствуйте, Sinclair, Вы писали:
S>А ты точно не должен получить в итоге дерево выражения? А вовсе не массивы? ёё>>и потом я начинаю вычислять...
Грамматика-то операторная, для вычисления достаточно завести два стека. Как именно — я показал выше.
Вот, к примеру, научные калькуляторы. Никаких деревьев внутри — микроконтроллеры сие не разумеют, и глубина стека там ограничена
(скажем, 10 скобок и 3 уровня приоритета — аддитивный, мультипликативный, показательный — итого максимум 30 операторов и соответственно, 31 операнд).
Здравствуйте, Sinclair, Вы писали: S>А ты точно не должен получить в итоге дерево выражения? А вовсе не массивы?
нет... я получаю дерево в памати неявно....но мне достаточно работать с масивами...
то есть для выражения типа 9*(5+3-8/24^65) мне как-то плевать на второй операнд я с ним работаю как с числом...
он уже к этому моменту вычислен...я просто всё в скобках вырезаю и рекусрсивно вычисляю...
2 _DAle_:
Кстати в том примере опять же нет сортировки...такой и у меня вычислиться...
там все операции раставлены по приоритетам...
2 Кодт:
Вобше, интересно конечно...но уж очнь не хочеться переписывать парсер.....там много
2 All:
Ну может быть всё таки возможно массивами отсортить...?
Ни что в жизни ни даёться так просто как... хотелось бы...
Здравствуйте, frёёm, Вы писали:
ёё>Ну может быть всё таки возможно массивами отсортить...?
Нельзя. Хотя бы потому, что не все операторы коммутативны.
Например, (1+2*3) можно заменить на (2*3+1), но (1-2*3) придётся заменять на (2*3~1) где x~y = y-x
Мне кажется, оберёшь ещё больше проблем, чем просто сделаешь интерпретатор с таблицей предшествования.
Кстати говоря, никто не мешает тебе вместо интерпретации заниматься компиляцией из инфиксной в обратно-польскую запись.
Вместо "вычислим x$y" подставь "положим x, положим y, положим $".
В результате разбора получишь строку инструкций, исполнение которых требует только стека данных.
Здравствуйте, frёёm, Вы писали:
ёё>Здравствуйте, Sinclair, Вы писали: S>>А ты точно не должен получить в итоге дерево выражения? А вовсе не массивы?
ёё>нет... я получаю дерево в памати неявно....но мне достаточно работать с масивами... ёё>то есть для выражения типа 9*(5+3-8/24^65) мне как-то плевать на второй операнд я с ним работаю как с числом... ёё>он уже к этому моменту вычислен...я просто всё в скобках вырезаю и рекусрсивно вычисляю...
ёё>2 _DAle_: ёё>Кстати в том примере опять же нет сортировки...такой и у меня вычислиться... ёё>там все операции раставлены по приоритетам...
ёё>2 Кодт: ёё>Вобше, интересно конечно...но уж очнь не хочеться переписывать парсер.....там много
ёё>2 All: ёё>Ну может быть всё таки возможно массивами отсортить...?
Если нет операторов одновременно унарных и бинарных, то можно восстановить исходную последовательность и вычислить ее нормально . {{9,8,7,6},{!,*,+,>}} Перебор лексем для этого примера определен однозначно. Если первый оператор унарный, берем его, иначе берем число и оператор и т.д.
! {} {!}
9 {9} {!}
* {9} {!*}
8 {9,8} {!*}
+ {9,8} {!*+} // выталкиваем из стека оператор с большим приоритетом
{72} {!+}
7 {72,7} {!+}
> {72,7} {!+>}// выталкиваем из стека оператор с большим приоритетом
{79} {!>}
6 {79,6} {!>} //выталкиваем все оставшиеся операторы из стека
{true} {!}
{true}
Мдя
На самом деле я так смотрю придёться вариант тов. Кодта и Дэйла мутить...
Но меня вот чё ещё волнует... если попробовать компиляцию в полиз...в принцыпе меня всё устраивает..довольно удобно и вобше.... но вот всё это время как только речь касалась полиза я так и не понял как там с приоретитом операций ?
там не ведёться подобный учёт ?
Ни что в жизни ни даёться так просто как... хотелось бы...
Здравствуйте, frёёm, Вы писали:
ёё>Мдя ёё>На самом деле я так смотрю придёться вариант тов. Кодта и Дэйла мутить...
ёё>Но меня вот чё ещё волнует... если попробовать компиляцию в полиз...в принцыпе меня всё устраивает..довольно удобно и вобше.... но вот всё это время как только речь касалась полиза я так и не понял как там с приоретитом операций ? ёё>там не ведёться подобный учёт ?
Приоритеты операций, скобки, учитываются при преобразовании. Затем получаем выражение в постфиксной форме, которое вычисляется просто слева направо.
Хорошо, и последжний я недеюсь вопрос...
не могли вы привести пример, (алгоритм, на словах) как вот такое выражение должно парситься...
Просто те были мне кажеться не очень представительными а здесь как бы разноприоритентные операции в разнобой
Очень большая просьба
1+2<4+5*6-7;
Ни что в жизни ни даёться так просто как... хотелось бы...
Здравствуйте, frёёm, Вы писали:
ёё>Хорошо, и последжний я недеюсь вопрос...
Будем вместе надеяться.
ёё>не могли вы привести пример, (алгоритм, на словах) как вот такое выражение должно парситься... ёё>Просто те были мне кажеться не очень представительными а здесь как бы разноприоритентные операции в разнобой ёё>Очень большая просьба ёё>
ёё>1+2<4+5*6-7;
ёё>
1 (1) ()
+ (1) (+)
2 (1,2) (+)
< (1,2) (+,<) // приоритет у < не больше, чем у +, поэтому достаем из стека +, из стека чисел два операнда,
(3) (<) // получаем результат, добавляем в стек операндов.
4 (3,4) (<)
+ (3,4) (<,+) // приоритет у + больше, чем у <, просто добавляем в стек
5 (3,4,5) (<,+)
* (3,4,5) (<,+,*) // приоритет у * больше, чем у +, просто добавляем в стек
6 (3,4,5,6) (<,+,*)
— (3,4,5,6) (<,+,*,-) // приоритет у — не больше, чем у *, умножаем
(3,4,30) (<,+,-) // приоритет у — не больше, чем у +, складываем
(3,34) (<,-) // приоритет у — больше, чем у <
7 (3,34,7) (<,-)
(3,27) (<)
(true)
Если опять что-то непонятно, прочитай все же статью в википедии.
Здравствуйте, frёёm, Вы писали:
ёё>Хорошо, и последжний я недеюсь вопрос... ёё>не могли вы привести пример, (алгоритм, на словах) как вот такое выражение должно парситься... ёё>Просто те были мне кажеться не очень представительными а здесь как бы разноприоритентные операции в разнобой ёё>Очень большая просьба ёё>
ёё>1+2<4+5*6-7;
ёё>
Сорри, забыл про моноширинность
1 (1) ()
+ (1) (+)
2 (1,2) (+)
< (1,2) (+,<) // приоритет у < не больше, чем у +, достаем из стека +, а из стека чисел два операнда,
(3) (<) // получаем результат, добавляем в стек операндов.
4 (3,4) (<)
+ (3,4) (<,+) // приоритет у + больше, чем у <, просто добавляем в стек
5 (3,4,5) (<,+)
* (3,4,5) (<,+,*) // приоритет у * больше, чем у +, просто добавляем в стек
6 (3,4,5,6) (<,+,*)
— (3,4,5,6) (<,+,*,-) // приоритет у — не больше, чем у *, умножаем
(3,4,30) (<,+,-) // приоритет у — не больше, чем у +, складываем
(3,34) (<,-) // приоритет у — больше, чем у <
7 (3,34,7) (<,-)
(3,27) (<)
(true)
Здравствуйте, frёёm, Вы писали:
ёё>Огромное вам человеческое спасиба
На этом форуме огромность и человечность спасибы можно выражать при помощи баллов.
... << RSDN@Home 1.1.4 beta 5 rev. 395>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Здравствуйте, frёёm, Вы писали:
ёё>Уже исправилься... ёё>Но, господа на самом деле, я вас если можно так выразиться
Скромнее с ненормативом. За него здесь в бан уезжают. ёё>Меня вот ешё скобки волнуют...
Тебе все уже рассказали.
... << RSDN@Home 1.1.4 beta 5 rev. 395>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
я не её использовал...я породию на неё использовал...
Перекуём баги на фичи!
. {{9,8,7,6},{!,*,+,>}} Перебор лексем для этого примера определен однозначно. Если первый оператор унарный, берем его, иначе берем число и оператор и т.д.
