DS — PHP: Объектно-ориентированный дизайн

PHP поставляется с библиотекой, называемой SPL (Standard PHP Library). Кроме прочего, она содержит набор классов, реализующих популярные структуры данных, такие как стек или очередь.

<?php

$q = new SplStack();
$q->push(3);
$q->push(10);
$q->pop(); // 10
$q->pop(); // 3

Несмотря на то, что SPL встроен в язык, конкретно к структурам данных есть множество претензий со стороны сообщества, как по производительности, так и по интерфейсам классов. Всё это вылилось в создание расширения php-ds (DS). Подробнее о нем читайте в статье. Библиотеку php-ds можно установить как обычный пакет https://github.com/php-ds/polyfill. Вся документация доступна здесь: https://php.net/manual/ru/book.ds.php.

DS включает в себя Vector, Deque, Map, Set, Stack, Queue, PriorityQueue, Pair. Эти структуры в жизни обычного веб-разработчика нужны не каждый день, но всё же такое случается. Если вы с ними не знакомы, то имеет смысл хотя бы прочитать о них в википедии.

Stack

Стек — это коллекция типа "Последний вошёл, первый вышел" (Last In, First Out или LIFO), которая позволяет работать только с самым верхним (последним) значением. Итерация происходит от конца к началу с удалением взятого элемента.

<?php

$stack = new \Ds\Stack();
$stack->push(3);
$stack->push(10);
$stack->pop(); // 10
$stack->pop(); // 3
print_r($stack->toArray());

Методы pop() и push() составляют основной интерфейс класса. push() добавляет элемент (или элементы) на стек, pop() - снимает со стека.

Перепишем с использованием этого стека функцию, которая разбиралась в курсе "PHP: массивы". Напомню задачу:

Необходимо реализовать функцию, которая проверяет, что парные символы сбалансированы. То есть каждый открывающий символ имеет закрывающий, и они не перекрываются, например, так: [{]}. К таким символам в нашем случае относятся <>, {}, (), []. Входом в функцию может быть ()<>{}. Такой пример проходит проверку, а вот этот уже нет: [({)}]. Здесь происходит перекрытие фигурных и круглых скобок.

<?php

function checkIfBalanced(string $expression): boolean
{
    // инициализируем стек
    $stack = new \Ds\Stack();
    // инициализируем список открывающих элементов
    $startSymbols = ['{', '(', '<', '['];
    // инициализируем список пар
    $pairs = ['{}', '()', '<>', '[]'];

    // Проходим по строке от первого до последнего символа
    for ($i = 0; $i < strlen($expression); $i++) {
        $curr = $expression[$i];
        // Если текущий символ находится в списке открывающих символов, то заносим его в стек
        if (in_array($curr, $startSymbols)) {
            $stack->push($curr);
        } else { // Если элемент не входит в список открывающих, то считаем, что это закрывающий символ
            $prev = $stack->pop();
            // Составляем из этих символов пару
            $pair = "{$prev}{$curr}";
            // Проверяем, что она входит в список $pairs. Если входит, то все правильно, двигаемся дальше; если нет,
            // то это автоматически означает, что символы не сбалансированы
            if (!in_array($pair, $pairs)) {
                return false;
            }
        };
    }

    // Если стек оказался пустым после обхода строки, то значит все хорошо
    return sizeof($stack) === 0;
}

Объектный стиль никак не повлиял на алгоритм решения. Кода не стало меньше, он не стал проще. С другой стороны, такой подход в PHP распространен крайне широко.

---

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты