02.05.2021 04:58
proctoleha 60 2500 Источник

В нашей славной компании есть очень хорошая, стимулирующая система т.н. грейдов: раз в полгода, любой разработчик может повысить свой грейд, что влечет за собой увеличение зарплаты. Другими словами, грейд — это аттестация. Хочешь увеличить зарплату? Раз в полгода можешь аттестоваться на следующую ступень, и расти от джуна до сеньора (за один раз можно перепрыгнуть не более, чем на две ступени). Аттестация проходит в дружелюбной форме, вопросы выложены в базе знаний, никакой бюрократической волокиты нет. Условием для допуска к аттестации служит решение алгоритмической задачи.


И вот я аттестовываюсь, и мне дают задачу: вычислить арифметическое выражение в виде строки. Да фигня вопрос, скажете вы (как и я в начале). Все это давно описано, и ничего сложного здесь нет. Вы будете одновременно правы и неправы. Вопрос то, конечно фигня, но это алгоритмическая задача. Готовые библиотеки использовать нельзя, нужно написать именно алгоритмическое решение. И окунулся я в мир операндов, операторов, как бинарных, так и унарных. И как все это красиво распарсить, как не запутаться со скобками, и… самым коварным оказался унарный минус.


Решение писать будем на php.


Чего-то нового в этой задаче, конечно же, нет. После недолгого гугления мы находим, что для разбора арифметического выражения в виде строки, машиной, лучше всего подходит Обратная польская запись. Материалов по ОПЗ много, разбирать её подробно смысла нет. Например, ссылка на вики.


Пример записи в ОПЗ: 3 4 2 + *


В упрощенном виде можно сказать, что ОПЗ — это запись арифметического выражения, в котором операторы записываются после операндов, и в котором нет скобок.
Под операндами мы понимаем вещественные числа, под операторами — символы арифметических операций +, -, *, /, ^


Почему ОПЗ так хороша для машинных вычислений?


Да потому, что в выражении нет скобок, и машине не надо производить лишних действий. Есть только операнды и операторы. Причем операторы всегда пишутся после операндов (постфиксная запись).
Машина линейно идет по строке, если попалось число, то кладем его в стек, иначе, если оператор бинарный, берем из стека правый операнд, берем из стека левый операнд, вычисленное значение кладем в стек. Когда дойдем до конца строки, достаем из стека результат вычислений.


В упрощенном виде (без проверок) это выглядит так:


<?php

$expression = explode(' ', '32 44 2 + *');

$stack = [];

foreach ($expression as $item) {
    if (is_numeric($item)) {
        $stack[] = (float)$item;
        continue;
    }
    $right = array_pop($stack);
    $left = array_pop($stack);
    switch ($item) {
        case '-':
            $stack[] = $left - $right;
            break;
        case '+':
            $stack[] = $left + $right;
            break;
        case '*':
            $stack[] = $left * $right;
            break;
        case '/':
            $stack[] = $left / $right;
            break;
        case '^':
            $stack[] = $left ** $right;
            break;
    }
}
// результат вычисления арифметического выражения
echo $stack[0] . PHP_EOL;

Все вроде просто, понятно, пока мы не продолжим читать про ОПЗ дальше. Цитата из вики:


В отличие от инфиксной записи, невозможно использовать одни и те же знаки для записи унарных и бинарных операций

Т.е. знак - (минус) мы можем использовать только как оператор вычитания. Для обозначения унарного минуса в ОПЗ, мы его использовать не можем.
Нам прямо предписывается использовать для обозначения унарного минуса любой свой придуманный символ. Давайте договоримся, что это будет тильда ~.
Более того — унарный оператор в ОПЗ имеет наивысший приоритет (в данной статье мы будем говорить про унарный минус)!


Что за нафиг? Почему какому-то несчастному оператору (унарный минус), уделяется столько внимания? Мы должны придумать для него специальный символ, и вдобавок ко всему у него еще и наивысший приоритет при разборе выражения?


Ну, с приоритетом понятно — действительно, прежде чем вычислять выражение, мы, в первую очередь, должны разобраться с положительными и отрицательными числами.


Разбираемся дальше. Для этого примем (вспомним) два постулата:


  1. Любое число, в памяти машины, хранится в виде байт-кода. Отрицательное число определяется значением старшего бита
  2. Для машины символ минус — это всегда оператор вычитания. Ни о каких унарных минусах машина не знает

Что из этого следует? Давайте рассмотрим простейший пример:
$a = -2
Что происходит в данном примере, с точки зрения машины?
Переменной $a необходимо присвоить отрицательное значение числа 2.
Для машины минус — это оператор вычитания. Операция бинарная. Справа 2, а слева ничего нет. Т.е. слева 0.
Т.е. в $a попадет результат вычисления выражения 0 - 2. Вычитать машина умеет прекрасно, в память машины будет записано верное отрицательное число.


Смотрим дальше. Есть выражение с двумя унарными минусами, например --2.
Как его должна считать машина? Если следовать нашей логике, то так: 0 - (0 - 2).
Т.е. унарный минус — это не просто вычитание операнда из ноля, но еще и правоассоциативная арифметическая операция, как и оператор возведения в степень.


Прежде чем идти дальше, давайте дадим определение унарному минусу в инфиксном арифметическом выражении:


  • Унарный минус — это оператор - (минус), перед которым в арифметическом выражении всегда стоит не число, и не закрывающая скобка

Подведем промежуточные итоги


  1. Мы выяснили, что для машинного разбора строки с арифметическим выражением необходимо его привести к ОПЗ (постфиксная запись)
  2. Мы разобрались почему у унарного минуса наивысший приоритет, и мы запомнили, что у него должен быть свой символ (у нас это тильда ~)

Нам осталось разобрать алгоритм приведения инфиксного арифметического выражения к постфиксному


Опять же всё давно изобретено до нас, использовать мы будет классический алгоритм сортировочной станции. Просто распишем его максимально подробно и понятно.


Прежде чем приступить к описанию алгоритма уточним давно известный алгоритм приоритета стековых операций.


В нашем случае операторы и приоритеты стековых операций будут выглядеть так:


    private const UNARY_MINUS = '~';
    private const OPEN_BRACKET = '(';
    private const CLOSE_BRACKET = ')';
    private const MINUS = '-';
    private const PLUS = '+';
    private const DIVISION = '/';
    private const MULTIPLICATION = '*';
    private const EXPONENTIATION = '^';

    private const PRIORITY = [
        self::OPEN_BRACKET => 0,
        self::CLOSE_BRACKET => null,
        self::PLUS => 2,
        self::MINUS => 2,
        self::MULTIPLICATION => 3,
        self::DIVISION => 3,
        self::EXPONENTIATION => 4,
        self::UNARY_MINUS => 5
    ];

Также необходимо определить правоассоциативные арифметические операции:


    private const RIGHT_ASSOCIATIVE_EXPRESSION = [
        self::EXPONENTIATION, self::UNARY_MINUS
    ];

В процессе разбора строки мы будем использовать понятие выходная строка (постфиксное выражение) и стек.


Алгоритм приведения инфиксной записи к постфиксной


Если при разборе строки нам встретилось число, то помещаем его в выходную строку


Иначе


  • Если в стеке пусто, или нам попалась открывающая скобка — помещаем оператор в стек


  • Если нам попался правоассоциативный оператор, и на вершине стека лежит такой же оператор, то ничего не делаем, просто добавляем оператор в стек



Иначе


  • Если нам попалась не закрывающая скобка, то выталкиваем из стека, в выходную строку, операторы с бОльшим, или равным приоритетом. Если, при выталкивании из стека, нам попался оператор с мЕньшим приоритетом — останавливаемся.
    Добавляем оператор на вершину стека.
  • Если нам попалась закрывающая скобка, то выталкиваем из стека, в выходную строку, все операторы до первой открывающей скобки. Открывающую скобку из стека удаляем
  • Если строка закончилась — выталкиваем все операторы из стека в строку вывода

Собственно всё. Данный алгоритм можно реализовать на любом ЯП.



Давайте приведём "вручную" выражение 2 * (2 + -2 ^ 2 ^ 3) - 1 к ОПЗ, и вычислим его


Приводим к постфиксной записи


Определим переменные для вычисления


    $stack = [];
    $outString = [];

Разбираем строку 2 * (2 + -2 ^ 2 ^ 3) - 1


  • Первый символ в строке 2, это число — помещаем его в выходную строку 


    $outString = [2];

  • Следующий символ — это оператор * — помещаем его в стек


    $outString = [2];
$stack = ['*'];

  • Следующий символ — это оператор ( — помещаем его в стек


    $outString = [2];
$stack = ['*', '('];

  • Следующий символ — это число 2 — помещаем его в выходную строку


    $outString = [2, 2];
$stack = ['*', '('];

  • Следующий символ — это оператор + — помещаем его в стек


    $outString = [2, 2];
$stack = ['*', '(', '+'];

  • Следующий символ — это оператор унарный минус ~ — помещаем его в стек


    $outString = [2, 2];
$stack = ['*', '(', '+', '~'];

  • Следующий символ — это число 2 — помещаем его в выходную строку


    $outString = [2, 2, 2];
$stack = ['*', '(', '+', '~'];

  • Следующий символ — это оператор ^ — выталкиваем из стека унарный минус, помещаем ^ в стек


    $outString = [2, 2, 2, '~'];
$stack = ['*', '(', '+', '^'];


И так далее… — если число, то помещаем в строку вывода, если оператор, то пытаемся вытолкнуть из стека, в строку вывода, другие операторы, сам оператор ставим на вершину стека. Всё согласно алгоритму выше.
Открывающая скобка имеет наименьший приоритет, её вытолкнуть нельзя, она должна быть уничтожена закрывающей скобкой. Приоритеты операторов мы также определили.


В конечном итоге мы получаем постфиксное выражение 2 2 2 ~ 2 3 ^ ^ + * 1 -


Ну, дальше, как было написано выше, дело техники.


  • Мы идем по строке с постфиксным выражением.
  • Если нам попалось число, то кладём его в стек.
  • Если нам попался унарный минус, то приводим число на вершине стека, к отрицательному значению (0 минус операнд).

Если нам попался бинарный оператор


  • берем с вершины стека число — это правый операнд
  • берем с вершины стека число — это левый операнд
  • вычисляем выражение, кладем его в стек

Если строка закончилась, возвращаем вычисленное значение из стека (если арифметическое выражение верно, то в стеке останется один элемент).



Полное решение на языке php


Спойлер

Пример использования класса Calculate


<?php
require_once __DIR__ . '/Calculate.php';

$expression = '2.5 * (-22 + 2 ^ 2 ^ 3) * (3 - 1)' . PHP_EOL;
$calc = new Calculate($expression);
if ($calc->postfixString) {
    echo 'Исходное выражение: ' . $expression;
    echo 'Строка в постфиксной записи (~ - это унарный минус): ' . $calc->postfixString . PHP_EOL;
    echo 'Результат вычисления постфиксной записи: ' . $calc->result . PHP_EOL;
} else {
    echo $calc->result . PHP_EOL;
}

Листинг класса Calculate


<?php

/** @noinspection PhpIllegalPsrClassPathInspection */

class Calculate
{
    private const UNARY_MINUS = '~';
    private const OPEN_BRACKET = '(';
    private const CLOSE_BRACKET = ')';
    private const MINUS = '-';
    private const PLUS = '+';
    private const DIVISION = '/';
    private const MULTIPLICATION = '*';
    private const EXPONENTIATION = '^';

    private const PRIORITY = [
        self::OPEN_BRACKET => 0,
        self::CLOSE_BRACKET => 1,
        self::PLUS => 2,
        self::MINUS => 2,
        self::MULTIPLICATION => 3,
        self::DIVISION => 3,
        self::EXPONENTIATION => 4,
        self::UNARY_MINUS => 5
    ];

    private const RIGHT_ASSOCIATIVE_EXPRESSION = [
        self::EXPONENTIATION, self::UNARY_MINUS
    ];

    private array $stack = [];
    private array $outString = [];

    /**
     * @var float|string
     */
    public $result;
    public string $postfixString = '';

    public function __construct(string $expression)
    {
        try {
            $expression = $this->checkExpression($expression);
            $this->createOutString($expression);
            $this->postfixString = implode(' ', $this->outString);
            $this->calcFromOutString();
        } catch (Exception $e) {
            $this->result = $e->getMessage();
        }
    }

    private function checkExpression(string $expression): string
    {
        preg_match('/-?\d+\s+-?\d+/', $expression, $matches);
        if ($matches) {
            throw new DomainException('Между числами нет оператора!');
        }
        $openBracket = substr_count($expression, self::OPEN_BRACKET);
        $closeBracket = substr_count($expression, self::CLOSE_BRACKET);
        if ($openBracket !== $closeBracket) {
            throw new DomainException('Непарные скобки!');
        }
        // удаляем все пробелы из строки
        $expression = preg_replace('/\s/', '', $expression);
        $expression = str_replace(',', '.', $expression);
        preg_match('/[^\d()+\/*-.^]+/', $expression, $matches);
        if ($matches) {
            throw new DomainException('Ошибка! В строке могут быть только цифры, скобки, и операторы +, -, *, /, ^');
        }

        return $expression;
    }

    private function calc($left, $right, $operator)
    {
        switch ($operator) {
            case self::MINUS:
                return $left - $right;
            case self::PLUS:
                return $left + $right;
            case self::MULTIPLICATION:
                return $left * $right;
            case self::EXPONENTIATION:
                return $left ** $right;
            case self::DIVISION:
                if ($right == 0) {
                    throw new DomainException('Деление на ноль!');
                }
                return $left / $right;
            default:
                throw new DomainException('Неизвестный оператор ' . $operator);
        }
    }

    /**
     * приводим к постфиксной записи
     */
    private function createOutString(string $expression)
    {
        $length = strlen($expression) - 1;
        $number = null;

        for ($i = 0; $i <= $length; $i++) {
            $item = $expression[$i];
            $left = $i === 0 ? null : $expression[$i - 1];
            $right = $i === $length ? null : $expression[$i + 1];

            if (is_numeric($item) || $item === '.') {
                if ($item === '.') {
                    if ($left === null || $right === null || !is_numeric($left) || !is_numeric($right)) {
                        throw new DomainException('Неверное дробное выражение!');
                    }
                }
                $number .= $item;
                if ($right !== '.' && !is_numeric($right)) {
                    $this->outString[] = (float)$number;
                    $number = null;
                }
                continue;
            }

            if ($item === self::MINUS) {
                if (!is_numeric($left) && $left !== self::CLOSE_BRACKET) {
                    $item = self::UNARY_MINUS;
                }
            }

            if ($item === self::OPEN_BRACKET && is_numeric($left)) {
                throw new DomainException('Перед открывающей скобкой нет оператора');
            }
            if ($item === self::CLOSE_BRACKET && (is_numeric($right) || $right === self::OPEN_BRACKET)) {
                throw new DomainException('После закрывающей скобки нет оператора');
            }

            $this->addToStackAndPushFromStack($item);
        }

        while ($this->stack) {
            $this->outString[] = array_pop($this->stack);
        }
    }

    private function addToStackAndPushFromStack(string $operator)
    {
        if (!$this->stack || $operator === self::OPEN_BRACKET) {
            $this->stack[] = $operator;
            return;
        }

        $stack = array_reverse($this->stack);

        if ($operator === self::CLOSE_BRACKET) {
            foreach ($stack as $key => $item) {
                unset($stack[$key]);
                if ($item === self::OPEN_BRACKET) {
                    $this->stack = array_reverse($stack);
                    return;
                }
                $this->outString[] = $item;
            }
        }

        foreach ($stack as $key => $item) {
            if (in_array($item, self::RIGHT_ASSOCIATIVE_EXPRESSION) && $item === $operator) {
                break;
            }
            if (self::PRIORITY[$item] < self::PRIORITY[$operator]) {
                break;
            }
            $this->outString[] = $item;
            unset($stack[$key]);
        }

        $this->stack = array_reverse($stack);
        $this->stack[] = $operator;
    }

    /**
     * Вычисляем из постфиксной записи
     */
    private function calcFromOutString()
    {
        $stack = [];
        foreach ($this->outString as $item) {
            if (is_float($item)) {
                $stack[] = $item;
                continue;
            }
            if ($item === self::UNARY_MINUS) {
                $last = array_pop($stack);
                if (!is_numeric($last)) {
                    throw new DomainException('Неверное выражение!');
                }
                $stack[] = 0 - $last;
                continue;
            }
            $right = array_pop($stack) ?? null;
            $left = array_pop($stack) ?? null;
            if ($right === null || $left === null) {
                throw new DomainException('Неверное выражение!');
            }
            $stack[] = $this->calc($left, $right, $item);
        }
        $this->result = $stack[0];
    }
}

Подведем итоги


Для красивого вычисления арифметического выражения в виде строки необходимо:


  1. Разобраться что такое Обратная польская запись, и почему она идеально подходит для машинных вычислений
  2. Привести арифметическое выражение к ОПЗ, и вычислить его

И для первого, и для второго пункта ключевым понятием является стек — последовательность, организованная по принципу — последний зашел, первый вышел. На вершине стека всегда находится его последний элемент.