Решаем задачи Python - Джеймс Девис

Скачать книгу

результат (32) обратно в стек.

      7. Помещаем 32 в стек.

      8. Встречаем оператор "/", извлекаем из стека 32 и 4, выполняем операцию деления и помещаем результат (8) обратно в стек.

      После завершения итераций, в стеке остается только один элемент – результат вычислений, который равен 8.

      Давайте напишем код для вычисления выражения в обратной польской записи:

      ```python

      def evaluate_reverse_polish_notation(expression):

      stack = []

      operators = {'+': lambda x, y: x + y,

      '-': lambda x, y: x – y,

      '*': lambda x, y: x * y,

      '/': lambda x, y: x / y}

      for token in expression.split():

      if token.isdigit():

      stack.append(int(token))

      elif token in operators:

      operand2 = stack.pop()

      operand1 = stack.pop()

      result = operators[token](operand1, operand2)

      stack.append(result)

      return stack[0]

      # Пример использования:

      expression = "5 3 + 8 * 4 /"

      result = evaluate_reverse_polish_notation(expression)

      print("Результат вычислений:", result)

      ```

      Этот код работает аналогично предыдущему, но мы добавил функцию `evaluate_reverse_polish_notation`, которая принимает строку в обратной польской записи и возвращает результат вычислений. Каждый токен выражения разделяется пробелами при помощи метода `split()`, чтобы создать список токенов. Затем итерируется по этому списку. Если текущий токен является числом, он добавляется в стек. Если текущий токен – оператор, извлекаются два операнда из стека, выполняется операция и результат помещается обратно в стек. После завершения итераций в стеке остается только один элемент – результат вычислений, который возвращается из функции.

8. Задача о сортировке: Реализовать свой алгоритм сортировки и сравнить его производительность с встроенной функцией сортировки Python.

      Идея решения:

      Для реализации собственного алгоритма сортировки, мы можем использовать один из классических алгоритмов, таких как сортировка пузырьком, сортировка вставками, сортировка выбором или быстрая сортировка. Давайте выберем быструю сортировку (Quick Sort) из-за ее высокой производительности в среднем случае.

      Идея быстрой сортировки заключается в следующем:

      1. Выбирается опорный элемент из массива.

      2. Массив разделяется на две подгруппы: одна содержит элементы, меньшие опорного, а другая – большие.

      3. Рекурсивно применяется алгоритм к каждой подгруппе.

      Для сравнения производительности нашего алгоритма сортировки с встроенной функцией сортировки Python (например, `sorted()`), мы можем измерить время выполнения каждого метода на одних и тех же данных.

      Код:

      ```python

      import time

      import random

      def quick_sort(arr):

      if len(arr) <= 1:

      return arr

      pivot = arr[len(arr) // 2]

      left = [x for x in arr if x < pivot]

      middle = [x for x in arr if x == pivot]

      right = [x for x in arr if x > pivot]

      return quick_sort(left) + middle + quick_sort(right)

      # Функция для замера времени выполнения

      def measure_time(sort_function, arr):

      start_time = time.time()

      sorted_arr = sort_function(arr)

      end_time = time.time()

      return sorted_arr, end_time – start_time

      # Генерация случайного списка для сортировки

      arr = [random.randint(0, 1000) for _ in range(1000)]

      # Сравнение производительности с собственной и встроенной сортировкой

      sorted_arr_custom, time_custom = measure_time(quick_sort, arr)

      sorted_arr_builtin, time_builtin = measure_time(sorted, arr)

      print("Время выполнения собственной сортировки:",

Скачать книгу