интересная задача

Тема в разделе "C/C++/C#", создана пользователем 9a9z9a, 25 фев 2011.

  1. 9a9z9a

    9a9z9a Гость

    Пишу дословно условие, т.к. не понял принцип преобразования.
    Дана некоторая строка, представляющая собой арифметическое выражение. Например, String = "12+4*56+(12*2+5)*13". Напишите программу, которая выведет постфиксную запись такого числа.
    В итоге должно получиться 12 4 56 * + 12 2 * 5 + 13 * +
    В итоге не понял саму суть преобразования. В инэте почитал , там пишут в решении с помощью графов и деревьев, но мы до такого ещё не дошли.
     
  2. ierofant

    ierofant Гость

    Ну и бред.. Убейте, пожалуйста, своего преподавателя, этим вы сделаете огромное одолжение всем.
     
  3. RiCrO

    RiCrO Гость

    ierofant, вы крайне категоричны. Парень заинтересован в решении данной задачи. "Препад" заинтересован в захламлении "свободного" времени студентам. Всё логично. ;)
     
  4. solova

    solova Гость

    Ну? Смысл преобразования понял? Точнее смысл преобразованного?
    Почитай про Конечные автоматы, от туда и алгоритм возьмёшь или сам придумаешь
    Открою секрет конечные автоматы, это и есть "графы", и от него никак(почти) не отвертеться , но об этом в конце сообщения
    Короче, вспоминай теорию 3-4 класса,
    помнишь? первым делается что в скобках, потом деление и умножения , ну и потом сложения и вычитания.
    Ну вот основы сперва () потом */ потом +-
    преобразовывается вроде так : цифры(числа) всегда остаются на своих местах
    : меняют места только знаки
    : скобки пропадают логическим перемещением знака(ов) из скобок
    : знак должен показывать действие с предыдущими двумя числами
    Примеры с (*) и (+) аналогично с (/) и (-)
    тут как то пофиг
    2+3 = 2 3+
    2*3 = 2 3*
    знак показывает действие с предыдущими двумя числами
    "но как быть тут ведь их три" 2 3 5+*
    просто 2 3 5+* -> 2 3+5 (*) -> 2 8* -> 2*8
    тут есть скобки они решаются первыми но не забываем что числа менять местами при преобразовании нельзя
    2*(3+5) = 2 3 5+* ( +* -> 5 нужно сложить с 3 и потом * на 2)
    (2+3)*5 = 2 3+5* ( выражение в скобках можно считать отдельно как уже выше решено 2+3=2 3+)
    2*3+5 = 2 3*5+ ( тут 2*3 можно считать в скобках и считать отдельно как уже выше решено 2*3 = 2 3*

    Тут я ещё накидал примерчиков чтоб алгоритм было легче понять
    2+3+5 = 2 3 5++
    2+3*5 = 2 3 5*+
    2*3*5 = 2 3 5**
    2*3+5 = 2 3*5+
    2*(3+5) = 2 3 5+*
    2+3+5+8 = 2 3 5 8+++
    2+3+5*8 = 2 3+5 8*+
    (2+3)*(5+8) = 2 3+5 8+*
    (2+3)*5*8 = 2 3+5*8*
    (2+3+5)*8 = 2 3 5++8* //скобка это как отдельное выражение типа //2+3+5 = 2 3 5++ просто потом домножаешь на 8*
    (2+3*5)+8 = 2 3 5*+8+ // ---||--- просто потом прибавляешь 8+
    (2*3+5)*8 = 2 3*5+8* // ---||--- просто потом домножаешь на 8*
    2+(3*5+8) = 2 3 5*8++ \\ тут первый плюс переносится в конец т.к. выполняется последним
    2*(3*5+8) = 2 3 5*8+* \\тут первое умножение переносится в конец т.к. выполняется последним

    1+2-3/5*8-13*21+34/55+89 = 1 2+3 5/8*-13 21*34 55/+89+

    на счёт способа избавится от векторов
    если препод текст проги не смотрит и задаст не очень большие примеры
    то можно шаблоны написать и по ним сравнивать формулы и в итоге переставлять всё как надо но это уже "дерево"
    Что то одно вы должны были проходить
     
  5. 9a9z9a

    9a9z9a Гость

    solova, спасибо. Вроде прояснил ситуацию, по крайней мере с логикой преобразования. Ни деревья , ни графы пока не изучали. Изучали стэки, но я их не до конца понял. Может через стэки можно?
     
  6. solova

    solova Гость

    2+3+5 = 2 3 5++
    2*3*5 = 2 3 5**
    2+3+5+8 = 2 3 5 8+++

    тут я ошибся
    правильно будет так
    2 3+5+
    2 3*5*
    2 3+5+8+
     
Загрузка...
Похожие Темы - интересная задача
  1. beloff
    Ответов:
    11
    Просмотров:
    2.409
  2. beloff
    Ответов:
    13
    Просмотров:
    2.741
  3. vbs
    Ответов:
    9
    Просмотров:
    4.028
  4. Янчик
    Ответов:
    0
    Просмотров:
    473
  5. TrishaRay
    Ответов:
    1
    Просмотров:
    778

Поделиться этой страницей