Простой парсер арифметических выражений

Однажды мне нужно было создать парсер математических выражений. Я взялся за этот труд и сразу же понял, что используя посимвольный разбор, я просто погрязну в большом количестве строк кода. Тогда на помощь пришел очень замечательный инструмент - регулярные выражения. Использовать регулярные выражения в Delphi или Builder'е стало легко возможным благодаря подключению модуля RegExpr.pas, созданного Андреем Сорокиным. Всё о регулярных выражениях Вы можете найти на его сайте: http://RegExpStudio.com/ Итак, приступим к созданию самого парсера.

Принцип работы

Нашему парсеру мы передаем выражение в виде строки, а он возвращает результат тоже в виде строки символов.

В первую очередь, нам нужно убрать все пробелы и табуляции из входящей строки. Затем, найти в ней самые внутренние скобки и рассматривать их как подвыражение, которое можно разобрать. Получившийся результат мы вставим вместо скобок и получим новое выражение, тождественно равное исходному.

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

Ну, а теперь на деле. Создадим класс TExParser, в который мы заключим все необходимые нам функции.

  TExParser = class(TObject)
  private
    // Определяет, является ли выражение одиночным числом
    function IsSimple(exp: string): Boolean;
    // Заменяет знак минуса в начале строки на # или удаляем +
    function ReplaceUnarMinus(exp: string): string;
    // Удаляет пробелы и табуляции
    function RemoveSpaces(str: string): string;
    // Внутренняя функция, разбирающая выражение без скобок
    function ParseExp(exp: string): string;
    // Заменяет десятичный разделитель на точку и обратно
    function Trans(exp: string; Localize: Boolean): string;
  public
    // Разбирает выражение со скобками
    function Parse(exp: string):string;
  end;

Начнем с реализации функции RemoveSpaces. Использовать будем стандартную функцию StringReplace:

 // Удаляет пробелы и табуляции
 function TExParser.RemoveSpaces(str: string): string;
 begin
   str := StringReplace(str,' ','',[rfReplaceAll]);
   Result := StringReplace(str,#12,'',[rfReplaceAll]);
 end;

Чтобы нам не попутать унарный минус (плюс) заменим его временно символом решётки (#). Для этого создадим функцию ReplaceUnarMinus. В ней мы будем заменять "-" на "#" при условии, если знак стоит первым в строке; плюс и вовсе удалать.

 // Заменяет знак минуса в начале строки на # или удаляем +
 function TExParser.ReplaceUnarMinus(exp: string): string;
 var
   p : PChar;
 begin
   Result := exp;
   p := PChar(exp);
   if p[0] = '-' then
   begin
     p[0] := '#';
     Result := String(p);
   end;
   if p[0] = '+' then
   begin
     Delete(exp,1,1);
     Result := exp;
   end;
 end;

Теперь реализуем функцию, которая нам будет определять, нужно ли разбирать выражение, а вдруг нам уже подсунули готовое число. Назовем мы её IsSimple. Вот в ней мы и применим чудо-действенные регулярные выражения. На понадобятся несколько констант, содержащих те самые выражения, по которым будет происходить поиск в строках.

 Const mldv = '([\*/])'; { / и * }
 Const plms = '([-\+])'; { + и - }
 Const brc = '\(([^\(\)]+?)\)'; { Внутренние скобки }
 Const num = '(\#?\d+(\.\d+)?)'; { число }

И сама функция IsSimple:

 // Определяет, является ли выражение одиночным числом
 function TExParser.IsSimple(exp: string): Boolean;
 var
  rx : TRegExpr;
 begin
  rx := TRegExpr.Create;
  rx.Expression := '^' + num + '$';
  Result := rx.Exec(exp);
  rx.Free;
 end;

Чтобы правильно работать с разделителем дробной части, на пишем функцию, Trans которая будет все приводить в порядок:

 // Заменяет десятичный разделитель на точку и обратно
 // Localize: True - на "родную", False - на точку
 function TExParser.Trans(exp: string; Localize: Boolean): string;
 begin
  if not Localize then
  begin
    exp := StringReplace(exp,DecimalSeparator,'.',[rfReplaceAll]);
  end
  else
  begin
    exp := StringReplace(exp,'.',DecimalSeparator,[rfReplaceAll]);
  end;
  Result := exp;
 end;

Ну, теперь приступим к главной функции - ParseExp. Она будет разбирать выражение, не содержащее скобки.

 // Внутренняя функция, разбирающая выражение без скобок
 function TExParser.ParseExp(exp: string): string;
 var
  rx : TRegExpr;
  a1, a2, act,res: string;
 begin
  // Проверка на целесообразность разбора
  if IsSimple(exp) then
  begin
    Result := exp;
    Exit;
  end;
 
  rx := TRegExpr.Create;
  // ищем операции умножения и деления
  rx.Expression := num + mldv + num;
  while rx.Exec(exp) do
  begin
    // Определяем операнды и операцию
    // a1 - левый, a2 - правый, act - операция
    a1 := Trans(StringReplace(rx.Match[1],
   '#', '-',[rfReplaceAll]),True);
    a2 := Trans(StringReplace(rx.Match[4],
    '#', '-',[rfReplaceAll]),True);
    act := rx.Match[3];
    if act = '*' Then
      // вычисляем умножение
      res := FloatToStr(StrToFloat(a1) * StrToFloat(a2))
    else
    begin
      // вычисляем деление
      if StrToFloat(a2) = 0 Then
      begin
        // Если операнд в справа равен нулю
        Result := 'Деление_на_ноль';
        Exit;
      end;
      res := FloatToStr(StrToFloat(a1) / StrToFloat(a2));
    end;
    res := Trans(ReplaceUnarMinus(res),False);
    exp := StringReplace(exp, 
   rx.Match[0], res,[rfReplaceAll]);
  end;
 
  // ищем операции сложения и вычитания
  rx.Expression := num + plms + num;  
  while rx.Exec(exp) do
  begin
    a1 := Trans(StringReplace(rx.Match[1],
   '#', '-',[rfReplaceAll]),True);
    a2 := Trans(StringReplace(rx.Match[4], 
   '#', '-',[rfReplaceAll]),True);
    act := rx.Match[3];
    if act = '+' Then
      res := FloatToStr(StrToFloat(a1) + StrToFloat(a2))
    else
    begin
      res := FloatToStr(StrToFloat(a1) - StrToFloat(a2));
    end;
    res := Trans(ReplaceUnarMinus(res),False);
    exp := StringReplace(exp, 
   rx.Match[0], res,[rfReplaceAll]);
  end;
  //возвращаем выражение
  Result := exp;
 end;

Для начала мы будем определять с помощью уже написанной функции IsSimple целесообразность разбора. Убедившись в том, что разбор необходим начинаем искать произведение и деление с помощью регулярных выражений. Выражения составлены так, чтобы можно было сразу выделить операнды и операцию. Затем с помощью стандартных функций StrToFloat получаем аргументы и выполняем соответствующее действие. Затем просто заменяем произведение (деление) полученным результатом, не забывая про унарный минус. Замена производится по средствам функции StringReplace с флагом rfReplaceAll, что позволяет нам не производить одни и те же вычисления. К примеру, если у нас выражение 2+2*3+12-2*3, то после вычисления первого произведения 2*3=6, получим строку 2+6+12-6. Таким образом, у нас получается своеобразная оптимизация. Точно также поступаем с оставшимися операциями.

Теперь нужно сделать так, чтобы наш парсер понимал скобки. Для этого мы пишем функцию, которая из нашего входящего выражения будет извлекать вложенные выражения и передавать их в порядке очереди в функцию ParseExp. Полученные результаты подставляем в место скобок всё той же функцией StringReplace с флагом rfReplaceAll. Функция будет объявлена в секции public и будет называться Parse:

 var
  rx : TRegExpr;
  res: string;
 
 begin
  // Заменяем знак минуса в начале на #
  // и удаляем пробелы и табуляции
  // А также десятичный знак разделения заменяем на точку (.)
  exp := Trans(ReplaceUnarMinus(RemoveSpaces(exp)),False);
  rx := TRegExpr.Create;
  // Ищем выражение, заключенное в скобки,
  // но не содержащее других скобок
  rx.Expression := brc;
  while rx.Exec(exp) do
  begin
    // в Match[1] содержится выражение без скобок,
  // которое можно разобрать
    res := ParseExp(rx.Match[1]);
 
    //теперь заменяем выражение, 
  //заключенное в скобки, результатом
    exp := StringReplace(exp, rx.Match[0], res,[rfReplaceAll]);
  end;
 
  //Разбираем оставшееся выражение (без скобок)
  exp := ParseExp(exp);
  // Восстанавливаем минус, если требуется
  Result := Trans(StringReplace(exp, '#', '-',
   [rfReplaceAll]),True);
 end;

На этом конструирование нашего парсера заканчивается. Теперь для его использования достаточно создать экземпляр класса TExParser и вызвать его метод Parse. Можно в процессе разбора строить объектную модель, по которой можно будет производить быстрые вычисления, с использованием подстановки, но это уже совсем другая... идея!