1. Если вы только начинаете программировать на ассемблере и не знаете с чего начать, тогда попробуйте среду разработки ASM Visual IDE
    (c) на правах рекламы
    Скрыть объявление

Упрощение выражений

Тема в разделе "WASM.A&O", создана пользователем Dr.Golova, 19 июл 2005.

  1. Dr.Golova

    Dr.Golova New Member

    Публикаций:
    0
    Регистрация:
    7 сен 2002
    Сообщения:
    348
    Собсно как заставить машину делать сабж?

    Например есть выражение: a+b-a+a+b

    Из курса начальной церковно-приходской школы я знаю что это можно упростить до a+2b

    Но как это обьяснить машине? Изобретать велосипед неохота - наверняка на эту тему писалась неодна диссертация :)

    any ideas?
     
  2. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    Dr.Golova



    То что тебе нужно называется "symbolic calculation" и встроенно в любую algebra system. Так как пока непонятно, что тебя конкретно интересует(операции,сложность,язык и т.д), то могу только отправить в Google. Пара примеров, откуда наверное можно взять код:

    gTybalt

    Math::Symbolic - Symbolic math for Perl
     
  3. _staier

    _staier New Member

    Публикаций:
    0
    Регистрация:
    3 окт 2003
    Сообщения:
    738
    Адрес:
    Ukraine
    по идее это довольно просто для

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

    потом список распечатываем







    типа так





    1)+a,-a,+a,+b,+b

    2)+a-a+a = +a

    вставляем в новый список +a

    +b+b= +2b

    вставляем в новый список +2b



    получаем список +a,+2b



    распечатываем - получаем a+2b





    сумноржением тоже можно придумать , например разложить на слагаемые

    насчет деления, не приходит в голову ничего кроме коэффициентов
     
  4. Dr.Golova

    Dr.Golova New Member

    Публикаций:
    0
    Регистрация:
    7 сен 2002
    Сообщения:
    348
    > что тебя конкретно интересует



    Конкретнее - a, b, c и т.д. - некие эфемерные неделимые обьекты, к которым многократно могут быть применены некоторые действия, необязательно математические (например "выделить"/"отменить выделение"), и действия необязательно из двух состояний как в примере с +/-. Хочется выкинуть как можно больше (необязатльно все) лишних/взаимоисключающих действий.
     
  5. Stiver

    Stiver Партизан дзена

    Публикаций:
    0
    Регистрация:
    18 дек 2004
    Сообщения:
    812
    Адрес:
    Germany
    Dr.Golova





    Мда, тогда не думаю, что удастся использовать готовый код, проще написать самому. В принципе ничего сложного, пишешь обычный парсер для выражений и упрощаешь получившееся дерево. Точнее сказать сложно, зависит от самих действий.
     
  6. S_T_A_S_

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.754
    Преобразование к обратной польской нотации может помочь + прикрутить простейший калькулятор для вычисления коэффициентов a, b, c и т.д. при выталкивании из стэка.
     
  7. Dr.Golova

    Dr.Golova New Member

    Публикаций:
    0
    Регистрация:
    7 сен 2002
    Сообщения:
    348
    > Преобразование к обратной польской нотации



    ИМХО это для расстановки скобок, а у меня все действия линейно друг за другом. Складывается впечатление что если я стэки на каждую операцию то будет мне щастье, но помойму это извращение и должен быть алгоритм пограмотнее.
     
  8. S_T_A_S_

    S_T_A_S_ New Member

    Публикаций:
    0
    Регистрация:
    27 окт 2003
    Сообщения:
    1.754
    не только для скобок, но и для разных приоритетов операций. Если приоритеты не важны, мона просто парсить строчку и считать символы a, b, c и т.д.
     
  9. SDragon

    SDragon New Member

    Публикаций:
    0
    Регистрация:
    6 июн 2005
    Сообщения:
    133
    Адрес:
    Siberia
    Если программа делается только для себя, то проще всего делать на функциональных языках типа ЛИСП или Пролог. Там получается очень короткий и понятный код с учетом приоритетов и скобок:

    http://www.csc.vill.edu/~dmatusze/resources/lisp/lisp-example.html



    Иначе нужно писать на обычных процедурных языках (деревья синтаксического разбора, стеки и все такое).
     
  10. rgo

    rgo New Member

    Публикаций:
    0
    Регистрация:
    21 мар 2005
    Сообщения:
    87
    есть maxima вся из себя написанная на LISP, которая предназначена для всяких символических вычислений...

    Она имеет ряд функций упрощения, типа превратить в произведение или в сумму для разных типов выражений. Плюс функцию expand которая наоборот, стремится раскрыть все скобки/функции, и оставить только сумму степеней переменных с коэффициентами. В общем на относительно простых выражениях, maxima упрощает правильно.

    Я бы на месте Dr.Golova научился заставлять maxima делать то что надо (то есть написал бы скрипт), а потом бы думал сколько стеков надо.



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



    ЗЫ вместо maxima, наверное можно пользовать Maple -- он коммерческий, и быть может имеет более дружественный интерфейс установки/использования.