Perl регулярные выражения: проверка правильности арифметического выражения

Иногда при вводе пользователя, а также в других случаях, требуется проверять правильность арифметических выражений. Кто-то продвинутый, вероятно, использует для этого модули Perl, а мы сделаем по-простому: напишем для этой проверки Perl регулярное выражение.

Если скобок в выражении нет, то тогда, конечно, всё просто. Как говорил принц Гамлет, "быть иль не быть? Вот в чём загвоздка". Вся загвоздка здесь в скобках, которые ещё и могут иметь произвольный уровень вложенности. Кое-кто из программистов даже не верил, что можно одним Perl регулярным выражением проверить правильность арифметического выражения. Но мы ведь уже почувствовали эту самую "мощь регулярных выражений Perl", особенно, если применяются динамические регулярные выражения?

В арифметических выражениях будем использовать целые числа, знаки +, -, * и / и круглые скобки. Впоследствии, если кому-нибудь понадобиться расширить этот набор элементов, то сделать это будет нетрудно. Вот примеры верных арифметических выражений:

 +3
 -(3/4+(-2-3)/3)
 (-((3)))

А вот пример ошибочных арифметических выражений:

 2*-3
 -(3/4+(-2-3)/3
 (-((3)+))

(Более позднее примечание: когда я писал эту статью, то не знал, что трансляторы (Perl, Delphi, ...) не считают ошибочным выражение 2*-3, и поэтому исходил из интуитивного, "человеческого" определения правильности записи арифметических выражений. По нему надо писать 2*(-3).)

Разумеется, мы не ставим задачу проверки, нет ли деления на 0, нас интересует только правильность синтаксиса арифметического выражения.

Если пытаться решать задачу в лоб с наскока, то будет разочарование, и после неудачных результатов проверки выражений со скобками могут прозвучать сложные и местами, быть может даже, рекурсивные, хотя и совсем не регулярные выражения... Perl регулярные выражения Лобовой путь здесь идеологически ошибочный и политически вредный. Мы пойдём другим путём и вспомним, как учили в институте на лекциях по конструированию компиляторов, где при описании грамматики языка использовалась форма Бэкуса-Наура:

 <арифм. выражение>             -> <терм><продолжение арифм. выражения>
 <продолжение арифм. выражения> -> +<терм><продолжение арифм. выражения>
                                -> -<терм><продолжение арифм. выражения>
                                -> пусто
 <терм>                         -> <множитель><продолжение терма>
 <продолжение терма>            -> *<множитель><продолжение терма>
                                -> /<множитель><продолжение терма>
                                -> пусто
 <множитель>                    -> <число>
                                -> (<арифм. выражение>)

Мы получили описание LL(1) грамматики арифметических выражений, и это описание рекурсивное: мы начинаем с самого корня (арифметического выражения), представляем его в виде слагаемых, или "термов":

 <term>-<term>-<term>+<term>+<term>+<term>...

Слагаемые, в свою очередь, дробятся на "множители":

 <множитель>/<множитель>*<множитель>*<множитель>...

А "множитель" может быть просто числом или исходным арифметическим выражением, но только в скобках. Проверьте вручную на нескольких арифметических выражениях эту грамматику и вы убедитесь, что она верна. Правда, внимательные читатели могут заметить, что в первом правиле перед термом может стоять унарный минус и даже плюс. Да, мы это легко учтём, а здесь я не хотел попусту увеличивать количество правил нашей формальной грамматики. И тогда у нас получится грамматика, которая будет проверять арифметические выражения так же хорошо, как и интерпретатор Perl и трансляторы других языков программирования.

Теперь начнём переводить правила грамматики в последовательность объектов Perl регулярных выражений. Заменим непонятное слово "терм" словом "слагаемое" и учтём унарный плюс-минус:

 my $arifm=qr#[+-]?$slag(?:[+-]$slag)*#;
 my $slag=qr#$mnog(?:[*/]$mnog)*#;

Мы учли здесь правила насчёт продолжения арифметического выражения и терма (слагаемого) и пустые правила. Пока всё легко ложится на язык Perl регулярных выражений. А как же записать правило для множителя? Не так ведь:

 my $mnog=qr#$number|\($arifm\)#;

Конечно, нет, интерпретатор это не пропустит, в этом рекурсивном замыкании арифметического выражения на себя где-то возникнет неопределённая переменная... Но динамические регулярные выражения Perl позволяют определять переменные рекурсивно. Немного подправив предыдущее правило, получим:

 my $mnog=qr#$number|\((??{$arifm})\)#;

Ну, и

 my $number=qr#\d+#;

Определяя $number соответствующим образом, мы легко можем ввести в нашу формальную гамматику дробные числа и идентификаторы. С возведением в степень чуть сложнее: надо по образцу правила для терма изменить правило для множителя и ввести правило для степени:

 <множитель>             -> <степень><продолжение множителя>
 <продолжение множителя> -> ^<степень><продолжение множителя>
                         -> пусто
 <степень>               -> <число>
                         -> (<арифм. выражение>)

Внимательный читатель по этой подсказке без труда сможет написать Perl регулярное выражение, учитывающее операцию возведения в степень, а мы ограничимся четырьмя дейсвиями арифметики.

Что делать дельше? Ведь вышеприведённый код Perl не годится для трансляции. Сейчас пора вспомнить правило исключения неизвестных методом подстановки при решении уравнений. В правило для $arifm мы вместо $slag подставим регулярное выражение для $slag и получим:

 my $arifm=qr#[+-]?$mnog(?:[*/]$mnog)*(?:[+-]$mnog(?:[*/]$mnog)*)*#;

Теперь вместо $mnog надо подставить регулярное выражение для него

 $number|\((??{$arifm})\)

Но в таком виде это делать нельзя, ведь это регулярное выражение является конструкцией выбора альтернативы, а она имеет самый низкий приоритет. Чтобы отгородить её от остального регулярного выражения Perl, её надо взять в незахватывающие скобки:

 (?:$number|\((??{$arifm})\))

Это выражение получается слишком длинным для нашей HTML-страницы, поэтому мы его разобьём на два, поставив модификатор x. Получим:

 my $arifm=qr#[+-]?(?:$number|\((??{$arifm})\))(?:[*/](?:$number|\((??{$arifm})\)))*
    (?:[+-](?:$number|\((??{$arifm})\))(?:[*/](?:$number|\((??{$arifm})\)))*)*#x;

Мы исключили $slag и $mnog и добились того, что теперь $arifm выражается через $arifm и $number. Остаётся оформить это в виде законченной программы:

#!perl -w
use strict;
use re 'eval';

# Проверка правильности арифметических выражений типа +1*(2-3/(4*5))
# Автор Сергей Мельников. Сделано для сайта "Perl регулярные выражения, статьи вебмастеру"
# http://www.cronc.com/ru.shtml
 
my @testexpr=(
# Верные арифметические выражения
'+3',
'-(3/4+(-2-3)/3)',
'(-((3)))',
'-(+1+2)*(3/(1-2))/((-3))',
# Ошибочные (с точки зрения арифметики) арифметические выражения 
'2*-3',
'-(3/4+(-2-3)/3',
'(-((3)+))');
 
my $number=qr/\d+/; # шаблон для числа/переменной
my $arifm;
# Модификатор x применён, чтобы разбить длинное re пополам для публикации в Web
$arifm=qr#[+-]?(?:$number|\((??{$arifm})\))(?:[*/](?:$number|\((??{$arifm})\)))*
   (?:[+-](?:$number|\((??{$arifm})\))(?:[*/](?:$number|\((??{$arifm})\)))*)*#x;
 
print /^$arifm$/ ? "Верно: $_\n" : "Неверно: $_\n" for (@testexpr);

Директива use re 'eval'; нам уже знакома, она нужна для предотвращения сообщения

 Eval-group not allowed at runtime, use re 'eval' in regex m/[+-]?...

Также обратите внимание, что мы сначала определяем переменную $arifm, а потом присваиваем ей значение. Это нужно потому, что в выражении $arifm=qr#[... в правой части встречается $arifm, и при проверке арифметического выражения, содержащего второй уровень вложенности скобок (как у нас) или более, мы получим сообщение

 Use of uninitialized value $arifm in pattern match (m//)...

В арифметическом выражении, а также вокруг него, могут быть пробельные символы, которые надо игнорировать. Для этого нетрудно исправить наши правила, добавив \s* вокруг знаков +, -, *, /, скобок (, ) и $number, а потом, повторить исключение переменных. Но лучше всё-таки убирать перед проверкой пробельные символы оператором tr///, т.к. бесконечные \s* в случае ошибочного арифметического выражения серьёзно затормозят работу Perl регулярного выражения. Применив атомарную группировку (?>\s*) или, если у вас Perl 5.10+, \s*+, вы сократите задержку в несколько раз, но всё таки она будет заметна. Атомарную группировку здесь можно применить и к другим квантификаторам.

Как видите, искомое Perl регулярное выражение оказалось не таким уж и большим. Вы можете легко растолковать его другим программистам (не показывая исходных правил), сказав: вот здесь слагаемые, здесь множители, а здесь всё выражение в скобках. Perl регулярные выражения