Простой парсер арифметических выражений
Однажды мне нужно было создать парсер математических выражений. Я взялся за этот труд и сразу же понял, что используя посимвольный разбор, я просто погрязну в большом количестве строк кода. Тогда на помощь пришел очень замечательный инструмент - регулярные выражения. Использовать регулярные выражения в Delphi или Builder'е стало легко возможным благодаря подключению модуля RegExpr.pas, созданного Андреем Сорокиным. Всё о регулярных выражениях Вы можете найти на его сайте: http://RegExpStudio.com/ Итак, приступим к созданию самого парсера.
Принцип работы
Нашему парсеру мы передаем выражение в виде строки, а он возвращает результат тоже в виде строки символов.
В первую очередь, нам нужно убрать все пробелы и табуляции из входящей строки. Затем, найти в ней самые внутренние скобки и рассматривать их как подвыражение, которое можно разобрать. Получившийся результат мы вставим вместо скобок и получим новое выражение, тождественно равное исходному.
Итак, теперь рассмотрим разбор выражения, не содержащего скобок. Для начала найдем операции умножения и деления. Выделим в них операнды и операцию, а затем вычислим и подставим результат вы наше выражение. После того как разберёмся со всем операциями умножения и деления, приступим к сложению и вычитанию, аналогичным путем.
Ну, а теперь на деле. Создадим класс TExParser, в который мы заключим все необходимые нам функции.
Принцип работы
Нашему парсеру мы передаем выражение в виде строки, а он возвращает результат тоже в виде строки символов.
В первую очередь, нам нужно убрать все пробелы и табуляции из входящей строки. Затем, найти в ней самые внутренние скобки и рассматривать их как подвыражение, которое можно разобрать. Получившийся результат мы вставим вместо скобок и получим новое выражение, тождественно равное исходному.
Итак, теперь рассмотрим разбор выражения, не содержащего скобок. Для начала найдем операции умножения и деления. Выделим в них операнды и операцию, а затем вычислим и подставим результат вы наше выражение. После того как разберёмся со всем операциями умножения и деления, приступим к сложению и вычитанию, аналогичным путем.
Ну, а теперь на деле. Создадим класс 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. Можно в процессе разбора строить объектную модель, по которой можно будет производить быстрые вычисления, с использованием подстановки, но это уже совсем другая... идея!
А как вызывать функции? )) Не могли бы Вы оставить пример этого парсинга в .pas или заархированным объектом
ОтветитьУдалитьРеализация данного парсера не поддерживает вызов каких-либо функций. Вообще, существует более элегантный способ разбора математических выражения, к примеру с использованием "обратной польской записью" (http://ru.wikipedia.org/wiki/%D0%9E%D0%B1%D1%80%D0%B0%D1%82%D0%BD%D0%B0%D1%8F_%D0%BF%D0%BE%D0%BB%D1%8C%D1%81%D0%BA%D0%B0%D1%8F_%D0%B7%D0%B0%D0%BF%D0%B8%D1%81%D1%8C). Кстати реализация такого парсера есть в генераторе отчетов FreeReport 2.34. Там есть открытые исходники.
ОтветитьУдалить