Модели и структуры данных



         

Операции обработки списков - часть 5


  • cdr(l) = nil;
  • car(l) = 4;
  • cons(car(l),q) = (4,(2,3),1);
  • рекурсивный вызов ListRev(nil, (4,(2,3),1)):

    • поскольку исходный список пустой, вызов возвращает список: (4,(2,3),1);

  • вызов возвращает список: (4,(2,3),1);

  • вызов возвращает список: (4,(2,3),1);

  • вызов возвращает список: (4,(2,3),1).

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

    • вся арифметика - целочисленная;
    • программа не проверяет правильность исходной записи;
    • в выражении не допускается унарный минус.

    {==== Программный пример 5.13 ====} { Калькулятор. Вычисление арифметических выражений } program Calc; Uses ListWork; type cptr = ^char; iptr = ^ integer; const { цифровые символы } digits : set of char = ['0'..'9']; { знаки операций с высоким приоритетом } prty : set of char = ['*','/']; var s : string; { исходная строка } n : integer; { номер текущего символа в исх. строке } {*** Представление исходной строки в списочной форме } Function Creat_Lst : lpt; var lll : lpt; { указатель на начало текущего списка } s1 : char; { текущий символ строки } st : string; { накопитель строки-операнда } {* Создание атома для Integer } Procedure NewInt; var ip : iptr; cc : integer; begin if Length(st) > 0 then begin { если в st накоплено цифровое представление числа, оно переводится в тип integer, для него создается атом и записывается в конец списка } New(ip); Val(st,ip^,cc); lll:=Append(NewAtom(ip,'I'),lll); st:=''; { накопитель строки сбрасывается } end; end; { Procedure NewInt } Procedure NewChar; { Создание атома для Char } var cp : cptr; begin { выделяется память для 1 символа, в ней сохраняется значение s1, для него создается атом, записывается в конец списка} New(cp); cp^:=s1; lll:=Append(NewAtom(cp,'C'),lll); end; { Procedure NewChar } begin { Function Creat_Lst } { исходный список пустой, накопитель строки - пустой } lll:=nil; st:=''; while n nil do begin { до опустошения исходного списка } { выделение знака операции } op:=car(l); l:=cdr(l); { выделение 2-го операнда } op2:=car(l); l:=cdr(l); { если 2-й операнд - подсписок - обработка подсписка } if not atom(op2) then op2:=FormPrty(op2); if cptr(op^.down)^ in prty then { если знак операции приоритетный, то создается подсписок: 1-й операнд, знак, 2-й операнд, этот подсписок далее является 1-ым операндом } op1:=cons(op1,cons(op,cons(op2,nil))) else begin { если знак неприоритетный, 1-й операнд и знак записываются в выходной список, 2-й операнд далее является 1-ым операндом } l2:=Append(op,Append(op1,l2)); op1:=op2; end; end; FormPrty:=Append(op1,l2); { последний операнд добавляется в выходной список } end; { Function FormPrty } {*** Вычисление выражения } Function Eval(l : lpt) : integer; var op1, op, op2 : lpt; begin { выделение 1-го операнда } op1:=car(l); l:=cdr(l); { если 1-й операнд - подсписок - вычислить его выражение } if not atom(op1) then iptr(op1^.down)^:=Eval(op1); while l <> nil do begin { выделение знака операции } op:=car(l); l:=cdr(l); { выделение 2-го операнда } op2:=car(l); l:=cdr(l); { если 2-й операнд - подсписок - вычислить его выражение } if not atom(op2) then iptr(op2^.down)^:=Eval(op2); { выполнение операции, результат - в op1 } case cptr(op^.down)^ of '+' : iptr(op1^.down)^:=iptr(op1^.down)^+iptr(op2^.down)^; '-' : iptr(op1^.down)^:=iptr(op1^.down)^-iptr(op2^.down)^; '*' : iptr(op1^.down)^:=iptr(op1^.down)^*iptr(op2^.down)^; '/' : iptr(op1^.down)^:=iptr(op1^.down)^ div iptr(op2^.down)^; end; end; Eval:=iptr(op1^.down)^; { возврат последнего результата } end; { Function Eval } {*** Главная программа } var l : lpt; begin write('>'); readln(s); { ввод исходной строки } { формирование списка } n:=1; l:=Creat_Lst; { выделение приоритетных операций } l:=FormPrty(l); { вычисление и печать результата } writeln(s,'=',Eval(l)); END.




    Содержание  Назад  Вперед