Алгоритм вычисления арифметического выражения в виде строки / Хабр

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

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

Решение писать будем на 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;

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

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

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

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

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

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

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

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

Смотрим дальше. Есть выражение с двумя унарными минусами, например --2.
Как его должна считать машина? Если следовать нашей логике, то так: 0 - (0 - 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];
    }
}

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

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

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

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

Алгоритм вычисления арифметического выражения в виде строки

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

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

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

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

Публикации

Ближайшие события