Реализовать алгоритм I-P

@Foxich · Регистрация: 25.12.2014

Доброго времени суток, нужна помощь с заданием:

1. Реализовать алгоритм I-P на языке программирования Pascal. Для работы со стеком
использовать связное распределение памяти и процедуры для:
- Создание пустого стека
- Добавление элемента на вершину стека
- Удаление элемента с вершины стека
2. Доработать алгоритм I-P, обеспечив обработку арифметических выражений,
содержащих скобки. Запрограммировать доработанный алгоритм на языке Паскаль.

Нужно подкорректировать. Буду благодарен за помощь.

Pascal

uses crt;
type
       pnode = ^node;
       node = record
        p : pnode;
        data : char;
       end;
var     top, temp : pnode;
       post, inf : string;
       symb, outdata: char;
       i : integer;
function push (top : pnode; data : char) : pnode;
var
       p : pnode;
begin
       new (p);
       p^.data := data;
       p^.p := top;
       push := p;
end;
function pop (top : pnode; var data : char) : pnode;
begin
       data := top^.data;
       pop := top^.p;
       dispose (top);
end;
function empty (top : pnode) : boolean;
begin
       if top = nil then empty := true
       else empty := false;
end;
function pred (oper1 : char; oper2 : char) : boolean;
begin
       pred := true;
       if (oper1 = '(') or (oper2 = '(') then pred := false;
       if oper2 = '^' then pred := false;
       if ((oper1 = '-') or (oper1 = '+'))
       and ((oper2 = '*') or (oper2 = '/')) then pred := false;
end;
begin
       clrscr;
       write ('Stroka v infiksnoi forme: '); readln (inf);
       inf := inf + ' ';
       post := '';
       top := nil;
       i := 1;
       repeat
               symb := inf[i];
               if (symb >= 'A') and (symb <= 'Z') then begin
                       post := post + symb;
                       inc (i);
               end
               else begin
                       while (empty (top) = false) and
                       (pred (top^.data, symb) = true) do begin
                               top := pop (top, outdata);
                               post := post + outdata;
                       end;
                       if (empty (top) = true) or (symb <> ')')
                       then top := push (top, symb)
                       else top := pop (top, outdata);
                       inc (i);
               end;
       until symb = ' ';
       while empty (top) = false do begin
               top := pop (top, outdata);
               post := post + outdata;
       end;
       writeln ('Stroka v postfiksnoi forme: ', post);
       readln;
end.

@bormant · 25.05.2015, 14:04

Не вдаваясь в суть самого алгоритма, поменял бы в части работы с памятью, имен функций и их прототипов на что-то вроде:

Pascal

type
  PNode = ^TNode;
  TNode = record
    next: PNode;
    data: char;
  end;
 
procedure push(var top: PNode; data: char);
var p: PNode;
begin
  new(p);
  p^.data:=data;
  p^.next:=top;
  top:=p;
end;
 
function IsEmpty(top: PNode): Boolean;
begin
  IsEmpty:=top=nil;
end;
 
function pop(var top: PNode): Char;
var p: PNode;
begin
  if IsEmpty(top) then RunError(201);
  pop:=top^.data;
  p:=top;
  top:=top^.next;
  Dispose(p);
end;
 
function pred(oper1, oper2: Char): Boolean;
begin
  pred:=not (
    (oper1='(') or (oper2='(') or (oper2='^') or
    (oper1 in ['-','+']) and (oper2 in ['*','/']));
end;
 
var
  top, t: PNode;
  post, inf: String;
  symb, outdata: Char;
  i: integer;
begin
  Write('Строка в инфиксной форме: '); ReadLn(inf);
  inf:=inf+' ';
  post:='';
  top:=nil;
  i:=1;
  repeat
    symb:=inf[i];
    if symb in ['A'..'Z'] then begin
      post:=post+symb;
      Inc(i);
    end else begin
      while not IsEmpty(top) and pred(top^.data,symb) do
        post:=post+pop(top);
      if IsEmpty(top) or (symb<>')') then
        push(top, symb)
      else
        pop(top);
      Inc(i);
    end;
  until symb=' ';
  while not IsEmpty(top) do post:=post+pop(top);
  WriteLn('Строка в постфиксной форме: ',post);
  ReadLn;
end.

Добавлено через 27 минут
С учетом того, что неплохо было бы разделять операнды и знаки операций, можно так:

Pascal

const
  symbs = ['0'..'9','A'..'Z','a'..'z'];
 
type
  PNode = ^TNode;
  TNode = record
    next: PNode;
    data: char;
  end;
 
procedure push(var top: PNode; data: char);
var p: PNode;
begin
  new(p);
  p^.data:=data;
  p^.next:=top;
  top:=p;
end;
 
function IsEmpty(top: PNode): Boolean;
begin
  IsEmpty:=top=nil;
end;
 
function pop(var top: PNode): Char;
var p: PNode;
begin
  if IsEmpty(top) then RunError(201);
  pop:=top^.data;
  p:=top;
  top:=top^.next;
  Dispose(p);
end;
 
function pred(oper1, oper2: Char): Boolean;
begin
  pred:=not (
    (oper1='(') or (oper2='(') or (oper2='^') or
    (oper1 in ['-','+']) and (oper2 in ['*','/']));
end;
 
var
  top: PNode;
  post, inf: String;
  symb: Char;
  i: integer;
begin
  Write('Строка в инфиксной форме: '); ReadLn(inf);
  inf:=inf+' ';
  post:='';
  top:=nil;
  for i:=1 to Length(inf)-1 do begin
    symb:=inf[i];
    if symb=' ' then Break;
    if symb in symbs then begin
      post:=post+symb;
      if not (inf[i+1] in symbs) then post:=post+' ';
    end else begin
      while not IsEmpty(top) and pred(top^.data,symb) do
        post:=post+pop(top)+' ';
      if IsEmpty(top) or (symb<>')') then
        push(top, symb)
      else
        pop(top);
    end;
  end;
  while not IsEmpty(top) do post:=post+' '+pop(top);
  WriteLn('Строка в постфиксной форме: ',post);
  ReadLn;
end.

Опции темы