Решение задач по алгоритмам на Python.
A. Значения функции (evaluate_function.py)
Вася делает тест по математике: вычисляет значение функций в различных точках. Стоит отличная погода, и друзья зовут Васю гулять. Но мальчик решил сначала закончить тест и только после этого идти к друзьям. К сожалению, Вася пока не умеет программировать. Зато вы умеете. Помогите Васе написать код функции, вычисляющей y = ax2 + bx + c. Напишите программу, которая будет по коэффициентам a, b, c и числу x выводить значение функции в точке x.
На вход через пробел подаются целые числа a, x, b, c. В конце ввода находится перенос строки.
Выведите одно число — значение функции в точке x.
| Ввод | Вывод |
|
-8 -5 -2 7 |
-183 |
| Ввод | Вывод |
|
8 2 9 -10 |
40 |
B. Чётные и нечётные числа (check_parity.py)
Гоша и Тимофей нашли необычный тренажёр для скоростной печати и хотят освоить его. Тренажёр представляет собой поле из клавиш 4× 4, в котором на каждом раунде появляется конфигурация цифр и точек. На клавише написана либо точка, либо цифра от 1 до 9. В момент времени t игрок должен одновременно нажать на все клавиши, на которых написана цифра t. Гоша и Тимофей могут нажать в один момент времени на k клавиш каждый. Если в момент времени t были нажаты все нужные клавиши, то игроки получают 1 балл.
Найдите число баллов, которое смогут заработать Гоша и Тимофей, если будут нажимать на клавиши вдвоём.Представьте себе онлайн-игру для поездки в метро: игрок нажимает на кнопку, и на экране появляются три случайных числа. Если все три числа оказываются одной чётности, игрок выигрывает.
Напишите программу, которая по трём числам определяет, выиграл игрок или нет.
В первой строке записаны три случайных целых числа a, b и c. Числа не превосходят 109 по модулю.
Выведите «WIN», если игрок выиграл, и «FAIL» в противном случае.
| Ввод | Вывод |
|
1 2 -3 |
FAIL |
| Ввод | Вывод |
|
6 -2 0 |
WIN |
C. Соседи (neigbours.py)
Дана матрица. Нужно написать функцию, которая для элемента возвращает всех его соседей. Соседним считается элемент, находящийся от текущего на одну ячейку влево, вправо, вверх или вниз. Диагональные элементы соседними не считаются.
Например, в матрице A соседними элементами для (0, 0) будут 2 и 0. А для (2, 1) –— 1, 2, 7, 7.
В первой строке задано n — количество строк матрицы. Во второй — количество столбцов m. Числа m и n не превосходят 1000. В следующих n строках задана матрица. Элементы матрицы — целые числа, по модулю не превосходящие 1000. В последних двух строках записаны координаты элемента, соседей которого нужно найти. Индексация начинается с нуля.
Напечатайте нужные числа в возрастающем порядке через пробел.
| Ввод | Вывод |
|
4 3 1 2 3 0 2 6 7 4 1 2 7 0 3 0 |
7 7 |
| Ввод | Вывод |
|
4 3 1 2 3 0 2 6 7 4 1 2 7 0 0 0 |
0 2 |
D. Хаотичность погоды (chaos_wather.py)
Метеорологическая служба вашего города решила исследовать погоду новым способом.
Под температурой воздуха в конкретный день будем понимать максимальную температуру в этот день. Под хаотичностью погоды за n дней служба понимает количество дней, в которые температура строго больше, чем в день до (если такой существует) и в день после текущего (если такой существует). Например, если за 5 дней максимальная температура воздуха составляла [1, 2, 5, 4, 8] градусов, то хаотичность за этот период равна 2: в 3-й и 5-й дни выполнялись описанные условия. Определите по ежедневным показаниям температуры хаотичность погоды за этот период.
Заметим, что если число показаний n=1, то единственный день будет хаотичным.
В первой строке дано число n –— длина периода измерений в днях, 1 ≤ n≤ 105. Во второй строке даны n целых чисел –— значения температуры в каждый из n дней. Значения температуры не превосходят 273 по модулю.
Выведите единственное число — хаотичность за данный период.
| Ввод | Вывод |
|
7 -1 -10 -8 0 2 0 5 |
3 |
| Ввод | Вывод |
|
5 1 2 5 4 8 |
2 |
E. Самое длинное слово (longest_word.py)
Чтобы подготовиться к семинару, Гоше надо прочитать статью по эффективному менеджменту. Так как Гоша хочет спланировать день заранее, ему необходимо оценить сложность статьи.
Он придумал такой метод оценки: берётся случайное предложение из текста и в нём ищется самое длинное слово. Его длина и будет условной сложностью статьи.
Помогите Гоше справиться с этой задачей.
В первой строке дана длина текста L (1 ≤ L ≤ 105).
В следующей строке записан текст, состоящий из строчных латинских букв и пробелов. Слово —– последовательность букв, не разделённых пробелами. Пробелы могут стоять в самом начале строки и в самом её конце. Текст заканчивается переносом строки, этот символ не включается в число остальных L символов.
В первой строке выведите самое длинное слово. Во второй строке выведите его длину. Если подходящих слов несколько, выведите то, которое встречается раньше.
| Ввод | Вывод |
|
19 i love segment tree |
segment 7 |
| Ввод | Вывод |
|
21 frog jumps from river |
jumps 5 |
F. Палиндром (palindrom.py)
Помогите Васе понять, будет ли фраза палиндромом. Учитываются только буквы и цифры, заглавные и строчные буквы считаются одинаковыми.
Решение должно работать за O(N), где N — длина строки на входе.
В единственной строке записана фраза или слово. Буквы могут быть только латинские. Длина текста не превосходит 20000 символов.
Фраза может состоять из строчных и прописных латинских букв, цифр, знаков препинания.
Выведите «True», если фраза является палиндромом, и «False», если не является.
| Ввод | Вывод |
|
A man, a plan, a canal: Panama |
True |
| Ввод | Вывод |
|
zo |
False |
G. Работа из дома (binary.py)
Вася реализовал функцию, которая переводит целое число из десятичной системы в двоичную. Но, кажется, она получилась не очень оптимальной.
Попробуйте написать более эффективную программу.
Не используйте встроенные средства языка по переводу чисел в бинарное представление.
На вход подаётся целое число в диапазоне от 0 до 10000.
Выведите двоичное представление этого числа.
| Ввод | Вывод |
|
5 |
101 |
| Ввод | Вывод |
|
14 |
1110 |
H. Двоичная система (binary_system_sum.py)
Вася реализовал функцию, которая переводит целое число из десятичной системы в двоичную. Но, кажется, она получилась не очень оптимальной.
Попробуйте написать более эффективную программу.
Не используйте встроенные средства языка по переводу чисел в бинарное представление.
Тимофей записал два числа в двоичной системе счисления и попросил Гошу вывести их сумму, также в двоичной системе. Встроенную в язык программирования возможность сложения двоичных чисел применять нельзя. Помогите Гоше решить задачу.
Решение должно работать за O(N), где N –— количество разрядов максимального числа на входе.
Два числа в двоичной системе счисления, каждое на отдельной строке. Длина каждого числа не превосходит 10 000 символов.
| Ввод | Вывод |
|
1010 1011 |
10101 |
| Ввод | Вывод |
|
1 1 |
10 |
I. Степень четырёх (degree_four.py)
Напишите программу, которая определяет, будет ли положительное целое число степенью четвёрки.
Подсказка: степенью четвёрки будут все числа вида 4n, где n – целое неотрицательное число.
На вход подаётся целое число в диапазоне от 1 до 10000.
Выведите «True», если число является степенью четырёх, «False» –— в обратном случае.
| Ввод | Вывод |
|
15 |
False |
| Ввод | Вывод |
|
16 |
True |
J. Факторизация (factorization.py)
Основная теорема арифметики говорит: любое число раскладывается на произведение простых множителей единственным образом, с точностью до их перестановки. Например:
- Число 8 можно представить как 2 × 2 × 2.
- Число 50 –— как 2 × 5 × 5 (или 5 × 5 × 2, или 5 × 2 × 5). Три варианта отличаются лишь порядком следования множителей. Разложение числа на простые множители называется факторизацией числа.
Напишите программу, которая производит факторизацию переданного числа.
В единственной строке дано число n (2 ≤ n ≤ 10^9), которое нужно факторизовать.
Выведите в порядке неубывания простые множители, на которые раскладывается число n.
| Ввод | Вывод |
|
8 |
2 2 2 |
| Ввод | Вывод |
|
13 |
13 |
K. Списочная форма (list_form.py)
Вася просил Аллу помочь решить задачу. На этот раз по информатике.
Для неотрицательного целого числа X списочная форма –— это массив его цифр слева направо. К примеру, для 1231 списочная форма будет [1,2,3,1]. На вход подается количество цифр числа Х, списочная форма неотрицательного числа Х и неотрицательное число K. Число К не превосходят 10000. Длина числа Х не превосходит 1000.
Нужно вернуть списочную форму числа X + K.
В первой строке — длина списочной формы числа X. На следующей строке — сама списочная форма с цифрами записанными через пробел.
В последней строке записано число K, 0 ≤ K ≤ 10000.
Выведите списочную форму числа X+K.
| Ввод | Вывод |
|
4 1 2 0 0 34 |
1 2 3 4 |
| Ввод | Вывод |
|
2 9 5 17 |
1 1 2 |
L. Лишняя буква (extra_latter.py)
Васе очень нравятся задачи про строки, поэтому он придумал свою. Есть 2 строки s и t, состоящие только из строчных букв. Строка t получена перемешиванием букв строки s и добавлением 1 буквы в случайную позицию. Нужно найти добавленную букву.
На вход подаются строки s и t, разделённые переносом строки. Длины строк не превосходят 1000 символов. Строки не бывают пустыми.
Выведите лишнюю букву.
| Ввод | Вывод |
|
abcd abcde |
e |
| Ввод | Вывод |
|
go ogg |
g |
A. Ближайший ноль (distance_to_zero.py)
Тимофей ищет место, чтобы построить себе дом. Улица, на которой он хочет жить, имеет длину n, то есть состоит из n одинаковых идущих подряд участков. Каждый участок либо пустой, либо на нём уже построен дом.
Общительный Тимофей не хочет жить далеко от других людей на этой улице. Поэтому ему важно для каждого участка знать расстояние до ближайшего пустого участка. Если участок пустой, эта величина будет равна нулю — расстояние до самого себя.
Помогите Тимофею посчитать искомые расстояния. Для этого у вас есть карта улицы. Дома в городе Тимофея нумеровались в том порядке, в котором строились, поэтому их номера на карте никак не упорядочены. Пустые участки обозначены нулями.
В первой строке дана длина улицы —– n (1 ≤ n ≤ 10^6). В следующей строке записаны n целых неотрицательных чисел — номера домов и обозначения пустых участков на карте (нули). Гарантируется, что в последовательности есть хотя бы один ноль. Номера домов (положительные числа) уникальны и не превосходят 10^9.
Для каждого из участков выведите расстояние до ближайшего нуля. Числа выводите в одну строку, разделяя их пробелами.
| Ввод | Вывод |
|
5 0 1 4 9 0 |
0 1 2 1 0 |
| Ввод | Вывод |
|
6 0 7 9 4 8 20 |
0 1 2 3 4 5 |
B. Ловкость рук (sleight_of_hand.py)
Игра «Тренажёр для скоростной печати» представляет собой поле из клавиш 4x4. В нём на каждом раунде появляется конфигурация цифр и точек. На клавише написана либо точка, либо цифра от 1 до 9.
В момент времени t игрок должен одновременно нажать на все клавиши, на которых написана цифра t. Гоша и Тимофей могут нажать в один момент времени на k клавиш каждый. Если в момент времени t нажаты все нужные клавиши, то игроки получают 1 балл.
Найдите число баллов, которое смогут заработать Гоша и Тимофей, если будут нажимать на клавиши вдвоём.
В первой строке дано целое число k (1 ≤ k ≤ 5).
В четырёх следующих строках задан вид тренажёра –— по 4 символа в каждой строке. Каждый символ —– либо точка, либо цифра от 1 до 9. Символы одной строки идут подряд и не разделены пробелами.
Выведите единственное число –— максимальное количество баллов, которое смогут набрать Гоша и Тимофей.
| Ввод | Вывод |
|
3 1231 2..2 2..2 2..2 |
2 |
| Ввод | Вывод |
|
4 1111 9999 1111 9999 |
1 |
A. Мониторинг (monitoring.py)
Алла получила задание, связанное с мониторингом работы различных серверов. Требуется понять, сколько времени обрабатываются определённые запросы на конкретных серверах. Эту информацию нужно хранить в матрице, где номер столбца соответствуют идентификатору запроса, а номер строки — идентификатору сервера. Алла перепутала строки и столбцы местами. С каждым бывает. Помогите ей исправить баг.
Есть матрица размера m × n. Нужно написать функцию, которая её транспонирует.
Транспонированная матрица получается из исходной заменой строк на столбцы.
В первой строке задано число n — количество строк матрицы. Во второй строке задано m — число столбцов, m и n не превосходят 1000. В следующих n строках задана матрица. Числа в ней не превосходят по модулю 1000.
Напечатайте транспонированную матрицу в том же формате, который задан во входных данных. Каждая строка матрицы выводится на отдельной строке, элементы разделяются пробелами.
| Ввод | Вывод |
|
4 3 1 2 3 0 2 6 7 4 1 2 7 0 |
1 0 7 2 2 2 4 7 3 6 1 0 |
| Ввод | Вывод |
|
4 3 1 2 3 0 2 6 7 4 1 2 7 0 |
1 0 7 2 2 2 4 7 3 6 1 0 |
B. Список дел (to_do_list.py)
Васе нужно распечатать свой список дел на сегодня. Помогите ему: напишите функцию, которая печатает все его дела. Известно, что дел у Васи не больше 5000.
В качестве ответа сдайте только код функции, которая печатает элементы списка. Длина списка не превосходит 5000 элементов. Список не бывает пустым.
Функция должна напечатать элементы списка по одному в строке.
C. Нелюбимое дело (unloved_business.py)
Вася размышляет, что ему можно не делать из того списка дел, который он составил. Но, кажется, все пункты очень важные! Вася решает загадать число и удалить дело, которое идёт под этим номером. Список дел представлен в виде односвязного списка. Напишите функцию solution, которая принимает на вход голову списка и номер удаляемого дела и возвращает голову обновлённого списка.
Функция принимает голову списка и индекс элемента, который надо удалить (нумерация с нуля). Список содержит не более 5000 элементов. Список не бывает пустым.
Верните голову списка, в котором удален нужный элемент.
D. Заботливая мама (caring_mother.py)
Мама Васи хочет знать, что сын планирует делать и когда. Помогите ей: напишите функцию solution, определяющую индекс первого вхождения передаваемого ей на вход значения в связном списке, если значение присутствует.
Функция на вход принимает голову односвязного списка и элемент, который нужно найти. Длина списка не превосходит 10000 элементов. Список не бывает пустым.
Функция возвращает индекс первого вхождения искомого элемента в список(индексация начинается с нуля). Если элемент не найден, нужно вернуть -1.
E. Всё наоборот (all_the_way_around.py)
Вася решил запутать маму —– делать дела в обратном порядке. Список его дел теперь хранится в двусвязном списке. Напишите функцию, которая вернёт список в обратном порядке.
Функция принимает на вход единственный аргумент — голову двусвязного списка. Длина списка не превосходит 1000 элементов. Список не бывает пустым.
Функция должна вернуть голову развернутого списка.
F. Стек - Max (stack_MAX.py)
Нужно реализовать класс StackMax, который поддерживает операцию определения максимума среди всех элементов в стеке. Класс должен поддерживать операции push(x), где x – целое число, pop() и get_max().
В первой строке записано одно число n — количество команд, которое не превосходит 10000. В следующих n строках идут команды. Команды могут быть следующих видов:
- push(x) — добавить число x в стек;
- pop() — удалить число с вершины стека;
- get_max() — напечатать максимальное число в стеке; Если стек пуст, при вызове команды get_max() нужно напечатать «None», для команды pop() — «error».
Для каждой команды get_max() напечатайте результат её выполнения. Если стек пустой, для команды get_max() напечатайте «None». Если происходит удаление из пустого стека — напечатайте «error».
| Ввод | Вывод |
|
8 get_max push 7 pop push -2 push -1 pop get_max get_max |
None -2 -2 |
| Ввод | Вывод |
|
7 get_max pop pop pop push 10 get_max push -9 |
None error error error 10 |
G. Стек - MaxEffective (stack_MaxEffective.py)
Реализуйте класс StackMaxEffective, поддерживающий операцию определения максимума среди элементов в стеке. Сложность операции должна быть O(1). Для пустого стека операция должна возвращать None. При этом push(x) и pop() также должны выполняться за константное время.
В первой строке записано одно число — количество команд, оно не превосходит 100000. Далее идут команды по одной в строке. Команды могут быть следующих видов:
- push(x) — добавить число x в стек;
- pop() — удалить число с вершины стека;
- get_max() — напечатать максимальное число в стеке; Если стек пуст, при вызове команды get_max нужно напечатать «None», для команды pop — «error».
Для каждой команды get_max() напечатайте результат её выполнения. Если стек пустой, для команды get_max() напечатайте «None». Если происходит удаление из пустого стека — напечатайте «error».
| Ввод | Вывод |
|
10 pop pop push 4 push -5 push 7 pop pop get_max pop get_max |
error error 4 None |
| Ввод | Вывод |
|
10 get_max push -6 pop pop get_max push 2 get_max pop push -2 push -6 |
None error None 2 |
H. Скобочная последовательность (is_correct_bracket_seq.py)
Вот какую задачу Тимофей предложил на собеседовании одному из кандидатов. Если вы с ней ещё не сталкивались, то наверняка столкнётесь –— она довольно популярная.
Дана скобочная последовательность. Нужно определить, правильная ли она.
Будем придерживаться такого определения:
- пустая строка —– правильная скобочная последовательность;
- правильная скобочная последовательность, взятая в скобки одного типа, –— правильная скобочная последовательность;
- правильная скобочная последовательность с приписанной слева или справа правильной скобочной последовательностью —– тоже правильная. На вход подаётся последовательность из скобок трёх видов: [], (), {}. Напишите функцию is_correct_bracket_seq, которая принимает на вход скобочную последовательность и возвращает True, если последовательность правильная, а иначе False.
На вход подаётся одна строка, содержащая скобочную последовательность. Скобки записаны подряд, без пробелов.
Выведите «True» или «False».
| Ввод | Вывод |
|
{[()]} |
True |
| Ввод | Вывод |
|
() |
True |
I. Ограниченная очередь (limited_queue.py)
Астрологи объявили день очередей ограниченного размера. Тимофею нужно написать класс MyQueueSized, который принимает параметр max_size, означающий максимально допустимое количество элементов в очереди.
Помогите ему —– реализуйте программу, которая будет эмулировать работу такой очереди. Функции, которые надо поддержать, описаны в формате ввода.
В первой строке записано одно число — количество команд, оно не превосходит 5000. Во второй строке задан максимально допустимый размер очереди, он не превосходит 5000. Далее идут команды по одной на строке. Команды могут быть следующих видов:
- push(x) — добавить число x в очередь;
- pop() — удалить число из очереди и вывести на печать;
- peek() — напечатать первое число в очереди;
- size() — вернуть размер очереди; При превышении допустимого размера очереди нужно вывести «error». При вызове операций pop() или peek() для пустой очереди нужно вывести «None».
Напечатайте результаты выполнения нужных команд, по одному на строке.
| Ввод | Вывод |
|
8 2 peek push 5 push 2 peek size size push 1 size |
None 5 2 2 error 2 |
| Ввод | Вывод |
|
10 1 push 1 size push 3 size push 1 pop push 1 pop push 3 push 3 |
1 error 1 error 1 1 error |
J. Списочная очередь(list_queue.py)
Любимый вариант очереди Тимофея — очередь, написанная с использованием связного списка. Помогите ему с реализацией. Очередь должна поддерживать выполнение трёх команд:
- get() — вывести элемент, находящийся в голове очереди, и удалить его. Если очередь пуста, то вывести «error».
- put(x) — добавить число x в очередь
- size() — вывести текущий размер
В первой строке записано количество команд n — целое число, не превосходящее 1000. В каждой из следующих n строк записаны команды по одной строке.пераций pop() или peek() для пустой очереди нужно вывести «None».
Выведите ответ на каждый запрос по одному в строке.
| Ввод | Вывод |
|
10 put -34 put -23 get size get size get get put 80 size |
-34 1 -23 0 error error 1 |
| Ввод | Вывод |
|
9 get size put 74 get size put 90 size size size |
error 0 74 0 1 1 1 |
K. Рекурсивные числа Фибоначчи(fibonacci_recursion.py)
У Тимофея было n (0≤n≤32) стажёров. Каждый стажёр хотел быть лучше своих предшественников, поэтому i-й стажёр делал столько коммитов, сколько делали два предыдущих стажёра в сумме. Два первых стажёра были менее инициативными —– они сделали по одному коммиту. Пусть Fi —– число коммитов, сделанных i-м стажёром (стажёры нумеруются с нуля). Тогда выполняется следующее: F0=F1=1. Для всех i≥2 выполнено Fi=Fi−1+Fi−2. Определите, сколько кода напишет следующий стажёр –— найдите Fn. Решение должно быть реализовано рекурсивно.
На вход подаётся n — целое число в диапазоне от 0 до 32.
Нужно вывести Fn.
| Ввод | Вывод |
|
3 |
3 |
| Ввод | Вывод |
|
0 |
1 |
L. Фибоначчи по модулю(fibonacci_mod.py)
У Тимофея было очень много стажёров, целых N (0 ≤ N ≤ 106) человек. Каждый стажёр хотел быть лучше своих предшественников, поэтому i-й стажёр делал столько коммитов, сколько делали два предыдущих стажёра в сумме. Два первых стажёра были менее инициативными — они сделали по одному коммиту.
Пусть Fi —– число коммитов, сделанных i-м стажёром (стажёры нумеруются с нуля). Первые два стажёра сделали по одному коммиту: F0=F1=1. Для всех i≥ 2 выполнено Fi=Fi−1+Fi−2.
Определите, сколько кода напишет следующий стажёр –— найдите последние k цифр числа Fn.
Как найти k последних цифр
В первой строке записаны через пробел два целых числа n (0 ≤ n ≤ 106) и k (1 ≤ k ≤ 8).
В первой строке записаны через пробел два целых числа n (0 ≤ n ≤ 106) и k (1 ≤ k ≤ 8).
Выведите единственное число – последние k цифр числа Fn.
Если в искомом числе меньше k цифр, то выведите само число без ведущих нулей.
| Ввод | Вывод |
|
3 1 |
3 |
| Ввод | Вывод |
|
10 1 |
9 |
A. Дек (double_ended_queue.py)
Гоша реализовал структуру данных Дек, максимальный размер которого определяется заданным числом. Методы push_back(x), push_front(x), pop_back(), pop_front() работали корректно. Но, если в деке было много элементов, программа работала очень долго. Дело в том, что не все операции выполнялись за O(1). Помогите Гоше! Напишите эффективную реализацию.
Внимание: при реализации используйте кольцевой буфер.
В первой строке записано количество команд n — целое число, не превосходящее 100000. Во второй строке записано число m — максимальный размер дека. Он не превосходит 50000. В следующих n строках записана одна из команд:
- push_back(value) – добавить элемент в конец дека. Если в деке уже находится максимальное число элементов, вывести «error».
- push_front(value) – добавить элемент в начало дека. Если в деке уже находится максимальное число элементов, вывести «error».
- pop_front() – вывести первый элемент дека и удалить его. Если дек был пуст, то вывести «error».
- pop_back() – вывести последний элемент дека и удалить его. Если дек был пуст, то вывести «error». Value — целое число, по модулю не превосходящее 1000.
Выведите результат выполнения каждой команды на отдельной строке. Для успешных запросов push_back(x) и push_front(x) ничего выводить не надо.
| Ввод | Вывод |
|
4 4 push_front 861 push_front -819 pop_back pop_back |
861 -819 |
| Ввод | Вывод |
|
7 10 push_front -855 push_front 0 pop_back pop_back push_back 844 pop_back push_back 823 |
-855 0 844 |
B. Калькулятор (caclulator.py)
Задание связано с обратной польской нотацией. Она используется для парсинга арифметических выражений. Еще её иногда называют постфиксной нотацией.
В постфиксной нотации операнды расположены перед знаками операций.
Пример 1: 3 4 + означает 3 + 4 и равно 7
Пример 2: 12 5 / Так как деление целочисленное, то в результате получим 2.
Пример 3: 10 2 4 * - означает 10 - 2 * 4 и равно 2
Разберём последний пример подробнее:
Знак * стоит сразу после чисел 2 и 4, значит к ним нужно применить операцию, которую этот знак обозначает, то есть перемножить эти два числа. В результате получим 8.
После этого выражение приобретёт вид:
10 8 -
Операцию «минус» нужно применить к двум идущим перед ней числам, то есть 10 и 8. В итоге получаем 2.
Рассмотрим алгоритм более подробно. Для его реализации будем использовать стек.
Для вычисления значения выражения, записанного в обратной польской нотации, нужно считывать выражение слева направо и придерживаться следующих шагов:
Обработка входного символа: Если на вход подан операнд, он помещается на вершину стека. Если на вход подан знак операции, то эта операция выполняется над требуемым количеством значений, взятых из стека в порядке добавления. Результат выполненной операции помещается на вершину стека. Если входной набор символов обработан не полностью, перейти к шагу 1. После полной обработки входного набора символов результат вычисления выражения находится в вершине стека. Если в стеке осталось несколько чисел, то надо вывести только верхний элемент. Замечание про отрицательные числа и деление: в этой задаче под делением понимается математическое целочисленное деление. Это значит, что округление всегда происходит вниз. А именно: если a / b = c, то b ⋅ c — это наибольшее число, которое не превосходит a и одновременно делится без остатка на b.
Например, -1 / 3 = -1. Будьте осторожны: в C++, Java и Go, например, деление чисел работает иначе.
В текущей задаче гарантируется, что деления на отрицательное число нет.
В единственной строке дано выражение, записанное в обратной польской нотации. Числа и арифметические операции записаны через пробел.
На вход могут подаваться операции: +, -, *, / и числа, по модулю не превосходящие 10000.
Гарантируется, что значение промежуточных выражений в тестовых данных по модулю не больше 50000.
Выведите единственное число — значение выражения.
| Ввод | Вывод |
|
2 1 + 3 * |
9 |
| Ввод | Вывод |
|
7 2 + 4 * 2 + |
38 |