Алгоритмы и структуры данных · 30 из 30
Обратная польская запись
Курсовая у старшекурсников, которую Борис Аркадьевич даёт сильным первокурсникам: перевести выражение в обратную польскую запись — ту, где знак действия стоит после чисел, а скобок нет вовсе. Так выражения разбирают калькуляторы и компиляторы. Алгоритм придумал Дейкстра и назвал его «сортировочной станцией»: числа идут прямо на выход, а знаки ждут на запасном пути — в стеке.
Что сделать
Переведите арифметическое выражение в обратную польскую запись алгоритмом «сортировочной станции».
Что приходит
vyrazhenie— правильное выражение: целые числа без знака,+ - * / ^, скобки, пробелы где угодно
Что вернуть
Строку записи: числа и знаки через один пробел, без скобок; "3 + 4 * 2" → "3 4 2 * +".
Допишите функцию v_opz в редакторе справа.
Результат верните через return — то, что
напечатано, на проверку не влияет.
v_opz("3 + 4 * 2")
'3 4 2 * +'
Приоритеты: ^ — высший, * и / — средний, + и - — низший. + - * / левоассоциативны (8 − 3 − 2 = (8 − 3) − 2), ^ — правоассоциативна (2 ^ 3 ^ 2 = 2 ^ (3 ^ 2)).
Алгоритм. Число — сразу на выход. Открывающая скобка — в стек. Закрывающая — снимать знаки со стека на выход до открывающей, саму открывающую выбросить. Знак действия — пока на вершине стека знак (не скобка) с большим приоритетом или с равным, если новый знак левоассоциативный, снимать его на выход; затем положить новый знак в стек. В конце снять со стека на выход всё оставшееся.
Числа бывают многозначными: «12» — одно число, а не две цифры. Пробелы в выражении могут стоять где угодно или отсутствовать.
Обсуждение
Вопросов пока нет.
Войдите, чтобы спросить.