| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Синтаксический анализатор [D7, WinXP]
Kisha © (2005-08-25 03:18:00)Дана формула:
<формула>::=<цифра>|(<формула><знак><формула>)
<цифра>- 0..9
<знак> - +,-,*
| - "логическое "или"
Требуется написать рекурсивную процедуру(функцию), которая вычислила бы результат данной формулы.
Например: ((5+3)*2)-1 = 15
Никак ничего в голову не приходит: как это организовать рекурсией?
TUser (2005-08-25 14:57:00) [21]Ошибка
var i: integer;
begin
i:=1;
writeln (inttostr(ReadExpression('(5*(1+2))',tkEqu,i)));
i:=1;
writeln (inttostr(ReadExpression('5*(1+2)',tkEqu,i)))
end.
TUser (2005-08-25 14:42:00) [22]Вот код, который точно решает поставленную задачу, а заодно демонстрирует недостатки приведенной грамматики (если, конечно, задача состоит в вычислении значений произвольных арифметических выражений).
program R;
{$apptype console}
uses SysUtils;
type
TToken = (tkNum, tkEqu);
function ReadExpression (const Input: string; ExpType: TToken; var Position: integer): integer;
procedure Error;
begin
raise Exception.Create('IllegalExpression');
halt;
end;
function ReadNum: integer;
begin
result:=ord(Input[Position])-ord('0');
if (result < 0) or (result > 9) then
Error;
inc (Position);
end;
var a, b: integer;
c: char;
begin
if Position >= length(Input) then
Error;
if ExpType = tkNum then
result:=ReadNum
else begin
if Input[Position] <> '(' then
result:=ReadExpression(Input,tkNum,Position)
else begin
Inc (Position);
a:=ReadExpression(Input,tkEqu,Position);
c:=Input[Position]; inc (Position);
b:=ReadExpression(Input,tkEqu,Position);
if Input[Position] <> ')' then
Error;
inc (Position);
case c of
'+': result:= a+b;
'-': result:= a-b;
'*': result:= a*b;
end;
end;
end;
end;
var i: integer;
begin
i:=1;
writeln (inttostr(ReadExpression('(5*(1+2))',tkEqu,i)));
writeln (inttostr(ReadExpression('5*(1+2)',tkEqu,i)))
end.
PS. Такую задачу лучше решать не с помощью рекурсий, али же автоматов, а с помощью алгоритма Дейкстры, который есть, например, на сайте http://algolist.manual.ru
Zeqfreed (2005-08-25 14:40:00) [23]Пожалуй и я поделюсь своими изысканиями в области разбора математических выражений =)
http://zeqfreed.k66.ru/files/math_parser_src.rar
(исходник класса с примером использования, 5 Кб)
http://zeqfreed.k66.ru/files/math_parser_bin.rar
(exe'шник примера использования, 192 Кб)
За основу кода был взят исходник парсера выражений из книги Герберта Шилдта "Полный справочник по C#". Насколько я помню, там нельзя было использовать ф-ции, в свою версию я добавил возможность использования ф-ций в выражениях.
Юрий Зотов (2005-08-25 14:39:00) [24]> TStas © (25.08.05 13:32) [3]
Проверьте, как Ваш модуль сработает, например, на таком выражении:
-2*(-3)
Думаю, тут же и убедитесь, что поделка - она поделка и есть.
Существует теория компиляторов, где такие вещи давным-давно отработаны - вот ею и надо пользоваться (см. ссылку на статью). Польская запись - это оттуда, но в данном случае можно обойтись и без нее.
TStas (2005-08-25 14:06:00) [25]Когда я писал этот модуль, мне нужны были иеммо целые числа, но без проблем они заменяются на числа с плавающей точкой и тогда добавляется деление. Модуль привел просто как пример. Вопрос вкедь был, как это сделать
Officeman (2005-08-25 14:04:00) [26]хм. кому нужен расчёт целых чисел? имхо неподходит!
идея я тя прикольная, но не додуманная.
кажется готовые компоненты есть. мне встречались кажется на сайте "сумасшедших бобров"
да и самому можно написать.
http://www.delphikingdom.com/asp/viewitem.asp?catalogid=10
хорошая статья
TStas (2005-08-25 14:01:00) [27]>Чапаев ©
>Перевести в обратную польскую запись для начала...
А что такое польская запись?
TStas (2005-08-25 14:00:00) [28]Неправильно ссылку написал, вот:
http://stas258.narod.ru/frame/download/simpleEvalUnit.pas
TStas (2005-08-25 13:57:00) [29]Вот сам модуль, там есть коментарии. Приоритет операций он учитывает, конечно, возведение в степень выполняет справа налево, деления в немнет, так как написан он для целых чисел.
http://stas258.narod.ru/frame.download/simpleEvalUnit.pas
Alexander Panov (2005-08-25 13:51:00) [30]Кроме вышеизложенного почитай про конечные автоматы.
Чапаев (2005-08-25 13:39:00) [31]Перевести в обратную польскую запись для начала...
ЗЫ. Учти, что в такой постановке задачи не учитывается приоритет операциё.
TStas (2005-08-25 13:32:00) [32]Я написал однажды модуль, который выполняет выражения со скобками. Полный текст приводить не буду, скажу идею саму. Просматривается исходная строка. Она в ней ищутся цифры и знаки действий. Найденные куски строки записываются с TList, элементы которого представляют собой или число, или знак действия или выражение со скобками.
list[9]:='2';
list[10]:='+';
list[11]:='10';
затем просматриваются все нечетные элементы списка, т.е. не знаки. Если это просто строка с числом, то выполняется IntToStr от нее, если выражениее со скобками, рекурсия. Получаем
list[9]:=2;
list[10]:='+';
list[11]:=10;
Написаны функция, которые могут выполнять простейшие выражения вида 2+3, например. Затем полученный TList просматривается в соответствии с приоритетом операторов, Вами установленным.
Если попадается, напрмимер
list[9]:=2;
list[10]:='+';
list[11]:=10;
понятно, что указатели на строки там находятся, вызывается функция подсчета выражения и стираются два элемента листа, получится
list[2]:=12;
Могу привести и весь модуль, но разбиретесь ли Вы в чужом коде.
Смысл такой конструкции в оптимизации, строка с исходными выражениями не просматривается по несколько раз и нет преобразования IntToStr - StrToINt. ИМХО это наиболее прямой способ
Юрий Зотов (2005-08-25 05:21:00) [33]http://www.delphikingdom.com/asp/viewitem.asp?catalogid=10
Fay (2005-08-25 03:23:00) [34]2 Kisha © (25.08.05 3:18)
Назовите, пожалуйста, ключевое слово вопроса
a) написать
b) рекурсивную
c) требуется
d) другое...
| |
Страницы: 