Мы привыкли записывать математические выражения, опираясь на приоритет операций и на скобки. Именно поэтому: , но .
Далеко не все помнят из школьной математики приоритеты сложения и умножения, поэтому в социальных сетях распространены задачи «Сколько будет ».
Польский математик Ян Лукасевич около ста лет назад предложил необычный способ записи выражений, в котором не нужны ни приоритеты операций, ни скобки. Сейчас этот способ называют обратной польской записью.
Обратная запись непривычна и не получила широкого распространения, но ее можно встретить в таких языках программирования, как Forth и PostScript.
В обратной польской записи знак операции записывается не между операндами, а после них. Посмотрим, как это выглядит на примерах:
Обычная запись — , обратная —
Обычная запись — , обратная —
Операторы в обратной записи не всегда должны быть в конце. Например, можно записать так:
Эта запись читается слева направо и воспринимается так:
Число
Число
Операция сложения
Число
Число
Операция сложения
Операция умножения
Преимущество обратных выражений в том, что они не вызывают разночтения.
Чтобы разобраться на примере, дальше мы пошагово вычислим такое выражение:
Шаг 1. Берем из стопки два верхних числа — и . Выполняем над ними первую операцию — сложение:
Шаг 2. Идем дальше по выражению — нужно взять следующие два значения и второй оператор. Берем эти значения и применяем к ним вторую операцию сложения:
Шаг 3. Вспомним изначальное выражение:
Мы провели две операции сложения. Оставим только умножение и запишем в выражение результаты первых двух вычислений:
Шаг 4. Проводим последнюю операцию и получаем результат:
Алгоритм вычисления очень прост, но требует новой для нас структуры данных. Представьте, что в вычислениях выше мы бы записывали каждое число на карточки и складывали бы из них стопку. Наверху стопки лежало бы число 45.
В программировании такие стопки называются стеком — от английского stack, то есть куча или кипа.
В стеке, как и в стопке, мы имеем дело только с верхней карточкой — вершиной. Задача, которую решает стек — запомнить промежуточный результат для будущих вычислений.
В отличие от ранее изученных нами структур, стек обычно реализуют поверх других структур — массива или односвязного списка.
Реализуя структуру данных, разработчик ради удобства может добавить в нее дополнительные методы.
Разные реализации могут быть непохожи друг на друга, но мы всегда ожидаем найти основные методы — конечно, у разных структур они разные. У стека должны быть реализованы три обязательных метода:
Метод push()
помещает элемент на вершину стека, как карточку наверх стопки
Метод pop()
убирает элемент с вершины и возвращает его
Метод isEmpty()
проверяет, пуст ли стек
В JavaScript методы push()
и pop()
уже присутствуют в массиве, поэтому мы можем использовать их как есть:
class Stack {
items = [];
push(value) {
this.items.push(value);
}
pop() {
return this.items.pop();
}
isEmpty() {
return this.items.length == 0;
}
}
class Stack:
items = []
def push(self, value):
self.items.append(value)
def pop(self):
return self.items.pop()
def is_empty(self):
return len(self.items) == 0
<?php
class Stack {
public $items = [];
public function push($value)
{
array_push($this->items, $value);
}
public function pop()
{
return array_pop($this->items);
}
public function isEmpty()
{
return count($this->items) == 0;
}
}
class Stack {
List items = new ArrayList<>();
public <T> void push(T item) {
items.add(item);
}
public <T> T pop() {
var lastElementIndex = items.size() - 1;
var lastElement = (T) items.get(lastElementIndex);
items.remove(lastElementIndex);
return lastElement;
}
public boolean isEmpty() {
return items.isEmpty();
}
}
Метод isEmpty()
возвращает true
, потому что массив пусть — содержит
элементов.
Воспользуемся нашим стеком, чтобы вычислить значение выражения :
let stack = new Stack();
const expression = '3 2 + 4 5 + *';
const lexems = expression.split(' ');
for (lexem of lexems) {
let a;
let b;
switch (lexem) {
case '+':
b = stack.pop();
a = stack.pop();
stack.push(a + b);
break;
case '-':
b = stack.pop();
a = stack.pop();
stack.push(a - b);
break;
case '*':
b = stack.pop();
a = stack.pop();
stack.push(a * b);
break;
case '/':
b = stack.pop();
a = stack.pop();
stack.push(a / b);
break;
default:
stack.push(parseFloat(lexem));
}
}
console.log(stack.pop()); // 45
stack = Stack()
expression = '3 2 + 4 5 + *'
lexems = expression.split(' ')
for lexem in lexems:
# В Python версии 3.10 и выше возможно использовать конструкцию match/case, но в данном случае рассмотрим реализацию через if/else
if lexem == '+':
a = stack.pop()
b = stack.pop()
stack.push(a + b)
break
elif lexem == '-':
a = stack.pop()
b = stack.pop()
stack.push(a - b)
break
elif lexem == '*':
a = stack.pop()
b = stack.pop()
stack.push(a * b)
elif lexem == '':
a = stack.pop()
b = stack.pop()
stack.push(a / b)
else:
stack.push(float(lexem))
print(stack.pop()) # 45
<?php
$stack = new Stack();
$expression = '3 2 + 4 5 + *';
$lexems = explode(' ', $expression);
foreach ($lexems as $lexem) {
$a;
$b;
switch ($lexem) {
case '+':
$b = $stack->pop();
$a = $stack->pop();
$stack->push($a + $b);
break;
case '-':
$b = $stack->pop();
$a = $stack->pop();
$stack->push($a - $b);
break;
case '*':
$b = $stack->pop();
$a = $stack->pop();
$stack->push($a * $b);
break;
case '/':
$b = $stack->pop();
$a = $stack->pop();
$stack->push($a / $b);
break;
default:
$stack->push(floatval($lexem));
}
}
print_r($stack->pop()); // 45
var stack = new Stack();
var expression = "3 2 + 4 5 + *";
String[] lexems = expression.split(" ");
for (String lexem : lexems) {
float a;
float b;
switch (lexem) {
case "+":
b = stack.pop();
a = stack.pop();
stack.push(a + b);
break;
case "-":
b = stack.pop();
a = stack.pop();
stack.push(a - b);
break;
case "*":
b = stack.pop();
a = stack.pop();
stack.push(a * b);
break;
case "/":
b = stack.pop();
a = stack.pop();
stack.push(a / b);
break;
default:
stack.push(Float.parseFloat(lexem));
}
}
stack.pop(); // 45
Как видите, решение не очень сложное. Мы разбиваем строку с выражением на лексемы и обрабатываем каждую лексему в цикле.
Если лексема — это знак операции, то мы «снимаем» с вершины стека два числа, выполняем операцию и помещаем результат обратно на стек.
При выполнении операций важно обращать внимание на порядок чисел. Числа в стеке расположены в порядке, обратном тому, в котором мы их туда помещали. Поэтому сначала мы извлекаем второй операнд b
, а потом первый a
.
Порядок операндов не важен для таких операций, как сложение и умножение, потому что равно . Но при делении это уже не так — не равно .
Если лексема не похожа на знак операции, мы считаем, что это число. Тогда с помощью функции parseFloat()
мы приводим строковую лексему к численному типу, чтобы ее можно было умножать и делить.
После завершения цикла на вершине стека должен храниться результат.
Реализация стека с помощью массива выглядит простой, но вставка элементов в конец списка может приводить к задержкам. Чтобы избежать ресурсоемких операций, реализуем стек при помощи связного списка.
Метод push()
будет добавлять узел в начало списка, а pop()
— удалять узел из начала:
class Stack {
items = new LinkedList();
push(value) {
this.items.add(value);
}
pop() {
return this.items.remove();
}
isEmpty() {
return this.items.head == null;
}
}
class Stack:
items = LinkedList()
def push(self, value):
self.items.add(value)
def pop(self):
return self.items.remove()
def is_empty(self):
return self.items.head is None
<?php
class Stack {
public $items = new LinkedList();
public function push($value)
{
$this->items->add($value);
}
public function pop()
{
return $this->items->remove();
}
public function isEmpty()
{
return $this->items->head === null;
}
}
class Stack {
var items = new LinkedList();
public <T> void push(T value) {
items.add(value);
}
public <T> T pop() {
return (T) items.remove();
}
public boolean isEmpty() {
return items.head == null;
}
}
Метод isEmpty()
проверяет, есть ли у списка голова. Если в списке нет ни одного узла, поле head
будет содержать null
— это означает, что стек пуст.
Методы в старом и новом классах Stack выглядят совершенно одинаково: имеют одинаковые названия, параметры и поведение. Поэтому вместо старой реализации нового стека мы можем использовать новую. Она будет немного быстрее, но чтобы это заметить, нам потребуются достаточно большие выражения.
Сейчас мы практически никуда не выходим без смартфона. Кажется, что телефонные звонки — уже не самая нужная функция. В основном мы пользуемся мессенджерами, трекерами, календарями и программами учета калорий.
Программы часто хранят данные в облаке — то есть на серверах в интернете. Скажем, календарь нам нужен не только на смартфоне, но и а ноутбуке. А иногда нужно не только предоставить доступ с разных устройств, но и надежно хранить данные. В облаке надежнее, чем на смартфоне.
В теории, как только в программе появляются новые данные, она должна отправить их на сервер. Например, трекер понимает, что наша позиция изменилась и посылает в облако новые координаты.
Но мобильная связь не всегда надежна и мы регулярно оказываемся без интернета. Простые программы в этом случае показывают ошибку подключения.
Однако, кратковременная потеря связи — это штатная ситуация и современные программы научились с ней справляться. Если связи нет, они складывают данные во временное хранилище, а когда связь появляется, отправляют их на сервер.
Но для хранения данных подойдет не любое хранилище. Представим, что программа-трекер складывает координаты в стек. Из стека координаты извлекаются в обратном порядке, как будто человек двигался задом наперед.
Нам нужна структура данных, похожая на стек и проводящая те же операции — поместить и извлечь. При этом в отличие от стека, она не должна менять порядок элементов. Это похоже на очередь в магазине, где люди обслуживаются в том же порядке, в котором они подошли к кассе.
Такая структура действительно существует. Она называется очередь, а по английски — queue.
Как и в стеке, в очереди если три основных метода:
push()
pop()
isEmpty()
Отличие в том, что в стеке элементы вставляются и извлекаются с одного конца. В очереди элементы вставляются с одного конца, а извлекаются из другого.
Как мы помним, односвязный список — не симметричная структура данных. Вставка и удаление элементов в начале списка выполняются гораздо быстрее, чем в конце, поэтому односвязный список не очень подходит для реализации очереди.
Зато для этой цели подходит двусвязный список, одинаково быстро работающий как в начале, так и в конце:
class Queue {
items = new DoublyLinkedList();
push(value) {
this.items.insertBegin(value);
}
isEmpty() {
return this.items.head == null;
}
}
class Queue:
items = DoublyLinkedList()
def push(self, value):
self.items.insert_begin(value)
def is_empty(self):
return self.items.head is None
<?php
class Queue {
public $items = new DoublyLinkedList();
public function push($value)
{
$this->items->insertBegin($value);
}
public function isEmpty() {
return $this->items->head === null;
}
}
class Queue {
var items = new DoublyLinkedList();
public <T> void push(T value) {
items.insertBegin(value);
}
public boolean isEmpty() {
return items.head == null;
}
}
Операция push()
сводится к вставке узла в начало двусвязного списка. А реализация pop()
останется вам в виде упражнения.
Иногда в технической литературе вместо терминов стек и очередь, можно встретить другие термины:
Стек или список LIFO — Last In First Out (последним пришел — первым ушел)
Очередь или список FIFO — First In First Out (первым пришел — первым ушел)
Повторим ключевые моменты из этого урока:
Стеки и очереди полезны для решения широкого круга задач
Стек может быть реализован либо с помощью массива, либо с помощью односвязного списка
Очередь может быть реализована с помощью двусвязного списка
Работу стека описывает принцип LIFO (последним пришел — первым ушел)
Работу очереди описывает принцип FIFO (первым пришел — первым ушел)
Вам ответят команда поддержки Хекслета или другие студенты.
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно
Наши выпускники работают в компаниях:
Зарегистрируйтесь или войдите в свой аккаунт