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

  • Автор темы 9a9z9a
  • Дата начала
9

9a9z9a

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

ierofant

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

RiCrO

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

solova

#4
Ну? Смысл преобразования понял? Точнее смысл преобразованного?
Почитай про Конечные автоматы, от туда и алгоритм возьмёшь или сам придумаешь
Открою секрет конечные автоматы, это и есть "графы", и от него никак(почти) не отвертеться , но об этом в конце сообщения
Короче, вспоминай теорию 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+

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

9a9z9a

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

solova

#6
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+