Стек, Помогите исправить программу Опции

[Neon6868]

Задание: С клавиатуры вводится текст, содержащий 4 вида скобок: (, {, [, <
Надо проверить, правильно ли расставлены скобки.Для этого, сначала надо проверить, чтобы после открывающейся скобки обязательно была закрывающаяся и чтобы соблюдались вложения скобок(т.е. например вот так (----{--)--} нельзя!). Если обнаружена скобка, то она записывается в стек.В конце програмы выводится сообщение, правильно или неправильно расставлены скобки.Если скобок в тексте нет, то вывести сообщение скобок нет.

Программа:

 
Program Stek;
  const
  n=1;
  type
    tes=1..n;
    stackl=^node;
    node=record
         data:tes;
         next:stackl
         end;
  var
    str:string;
  Function EmptyStack(var ST:stackl):boolean;
    Begin
      Emptystack:=st^.data=0
    End;
  Procedure PushSC(var STCL:stackl;x:TES);
  var
    P:stackl;
  Begin
    new(p);
    p^.data:=x;
    if emptyStack(STCL) then STCL:=p
      else p^.next:=stcl^.next;
    stcl^.next:=p;
  End;
  Begin
    writeln('Vvedite stroku:');
    readln(str);
    if str='(' or '{' or '[' or '<' then pushSC();
  End.
 

[Артемий]

А можно поинтересоваться, что именно вызывает затруднения?Поиск скобок?Или запись скобки в стэк?

[мисс_граффити]

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

в конце: если стек пустой - все отлично.

[Neon6868]

А нельзя сделать так, чтобы из стека ничего не удалять??

[Артемий]

А нельзя сделать так, чтобы из стека ничего не удалять??

Допустим заносим открывшуюся скобку в стэк - если след. закрывающая совподает,то идем дальше, пока не наткнемся на неправильный вариант -- сразу выдаем ошибку,все, строка левая.А если все гладко - то значит она правильная.может так?

Сообщение отредактировано: Артемий - 15.04.2007 18:44

[мисс_граффити]

Артемий, реализуем твой алгоритм.
строка:
(----{---}---)
1. стек пустой
2. в стеке (
3. в стеке ( {
4. закрывающаяся подходящая, идем дальше
5. ? ошибка?

Neon6868, а зачем так делать? кто нам мешает удалять? имхо, в этом и заключается преимущество использования стека на данной задаче (за счет FIFO. с очередью бы так не получилось)

[Neon6868]

А как тогда искать скобки в тексте?

[мисс_граффити]

const skobki=['(','{','['];
....

for i:=1 to length(s) do
  if s[i] in skobki then
... 

[volvo]

Надо проверить, правильно ли расставлены скобки

А в поиске был? Когда-то по этой теме на форуме даже соревнование проводилось, так что как минимум 6 разных вариантов точно есть...

[Neon6868]

А в поиске был? Когда-то по этой теме на форуме даже соревнование проводилось, так что как минимум 6 разных вариантов точно есть...

Спасибо за совет, и правда есть.

[Neon6868]

Помогите кто-нибудь исправить и переделать программу!Если в программе ввести скобки: ()) то должно быть выведено сообщение: "Стек пуст!", но этого не происходит, а выводится сообщение:"Скобки расставлены неправильно!"

И как переделать программу, чтобы в стек записывались все найденные открывающиеся скобки, а не закрывающиеся??

Вот программа:

 
Program Skobki;
type
  stackl=^node;
  node=record
       c:char;
       next:stackl;
       end;
var
  s:string;
  sp,p:stackl;
  i:integer;
  net:boolean;
Procedure Push(c:char);
begin
  new(p);
  p^.next:=sp;
  p^.c:=c;
  sp:=p;
end;
Function Emptystack(var SP:stackl):boolean;
  Begin
    Emptystack:=sp=nil;
  End;
Procedure POPSL(var SP:STACKL);
  var
  p:stackl;
  x:string;
  Begin
  if Emptystack(SP) then begin
    writeln('Stek pust!');
    exit;
  end;
  p:=SP;
  SP:=p^.next;
  x:=p^.c;
  dispose(p);
  End;
Begin
  writeln('Vvedite stroku:');
  readln(s);
  sp:=nil;
  net:=false;
  Push(chr(0));
  for i:=1 to Length(s) do
    case s[i] of
    '(':begin
          Push(')');
          net:=true;
        end;
    '[':begin
          Push(']');
          net:=true;
        end;
    '{':begin
          Push('}');
          net:=true;
        end;
    '<':begin
          Push('>');
          net:=true;
        end;
    ')',']','}','>':
      begin
      {  if (s[i]<>sp^.c) then
          begin
            Writeln('Skobki rasstavleni nepravilno!');
            exit;
          end; }
        net:=true;
        POPSL(SP);
      end;
      end;
    if net=false then
      begin
        writeln('Skobok v stroke net!');
        exit;
      end;
    if sp^.c=chr(0) then writeln('Skobki rasstavleni pravilno!');
end.

[Neon6868]

Я вот сделал, посмотрите пожалуйста нельзя ли проще что-нибудь сделать??

Код

Program Skobki;
type
  stackl=^node;
  node=record
       c:char;
       next:stackl;
       end;
var
  s:string;
  sp,p:stackl;
  i:integer;
  net:boolean;
Procedure Push(var sp,p:stackl;c:char);
begin
  new(p);
  p^.next:=sp;
  p^.c:=c;
  sp:=p;
end;
Function Emptystack(var SP:stackl):boolean;
  Begin
    Emptystack:=sp=nil;
  End;
Procedure POPSL(var SP:STACKL);
  var
  p:stackl;
  x:string;
  Begin
  p:=SP;
  SP:=p^.next;
  x:=p^.c;
  dispose(p);
  End;
Begin
  writeln('Vvedite stroku:');
  readln(s);
  sp:=nil;
  net:=false;
  for i:=1 to Length(s) do
    case s[i] of
    '(':begin
          Push(sp,p,'(');
          net:=true;
        end;
    '[':begin
          Push(sp,p,'[');
          net:=true;
        end;
    '{':begin
          Push(sp,p,'{');
          net:=true;
        end;
    '<':begin
          Push(sp,p,'<');
          net:=true;
        end;
    ']','}','>':
      begin
        if Emptystack(SP) then
          begin
            writeln('Stek pust! Znachit skobki rasstavleni nepravilno!');
            exit;
          end;
        if ord(s[i])=ord(sp^.c)+2 then
        begin
          net:=true;
          POPSL(SP);
        end
          else
          begin
            writeln('Skobki rasstavleni nepravilno!');
            exit;
          end;
      end;
        ')':
      begin
        if Emptystack(SP) then
          begin
            writeln('Stek pust! Znachit skobki rasstavleni nepravilno!');
            exit;
          end;
        if ord(s[i])=ord(sp^.c)+1 then
        begin
          net:=true;
          POPSL(SP);
        end
          else
          begin
            writeln('Skobki rasstavleni nepravilno!');
            exit;
          end;
      end;
      end;
    if net=false then
      begin
        writeln('Skobok v stroke net!');
        exit;
      end;
    if Emptystack(SP) then writeln('Skobki rasstavleni pravilno!')
      else writeln('Skobki rasstavleni nepravilno!')
end.

[мисс_граффити]

1.

    case s[i] of
    '(':begin
          Push(sp,p,'(');
          net:=true;
        end;
    '[':begin
          Push(sp,p,'[');
          net:=true;
        end;
    '{':begin
          Push(sp,p,'{');
          net:=true;
        end;
    '<':begin
          Push(sp,p,'<');
          net:=true;
        end; 

if s[i] in skobki then
  push(sp,p,s[i]

что такое skobki - см. сообщение 8

или

case s[i] of
    '(','{','<','[':begin
          Push(sp,p,s[i]);
          net:=true;
        end;

2.

    ']','}','>':
      begin
        if Emptystack(SP) then
          begin
            writeln('Stek pust! Znachit skobki rasstavleni nepravilno!');
            exit;
          end;
        if ord(s[i])=ord(sp^.c)+2 then
        begin
          net:=true;
          POPSL(SP);
        end
          else
          begin
            writeln('Skobki rasstavleni nepravilno!');
            exit;
          end;
      end;
        ')':
      begin
        if Emptystack(SP) then
          begin
            writeln('Stek pust! Znachit skobki rasstavleni nepravilno!');
            exit;
          end;
        if ord(s[i])=ord(sp^.c)+1 then
        begin
          net:=true;
          POPSL(SP);
        end
          else
          begin
            writeln('Skobki rasstavleni nepravilno!');
            exit;
          end;

и зачем дублировать такие огромные куски???
отличаются они одним условием.
вот его и трансформируй...

if ((s[i]=')') and (ord(s[i])=ord(sp^.c)+1)) or ((s[i] in ['>','}',']']) and (ord(s[i])=ord(sp^.c)+1)) then...

надеюсь, не запуталась сама в этой строке
но, думаю, идею ты понял...

3.

    if net=false then

if not net then

[Neon6868]

Вот переделал. Теперь нормально??

Код

Program Skobki;
type
  stackl=^node;
  node=record
       c:char;
       next:stackl;
       end;
var
  s:string;
  sp,p:stackl;
  i:integer;
  net:boolean;
Procedure Push(var sp,p:stackl;c:char);
begin
  new(p);
  p^.next:=sp;
  p^.c:=c;
  sp:=p;
end;
Function Emptystack(var SP:stackl):boolean;
  Begin
    Emptystack:=sp=nil;
  End;
Procedure POPSL(var SP:STACKL);
  var
  p:stackl;
  x:string;
  Begin
  p:=SP;
  SP:=p^.next;
  x:=p^.c;
  dispose(p);
  End;
Begin
  writeln('Vvedite stroku:');
  readln(s);
  sp:=nil;
  net:=false;
  for i:=1 to Length(s) do
    case s[i] of
      '(','[','{','<':
        begin
          Push(sp,p,s[i]);
          net:=true;
        end;
      ']','}','>',')':
        begin
          net:=true;
          if Emptystack(SP) then
            begin
              writeln('Stek pust! Znachit skobki rasstavleni nepravilno!');
              exit;
            end;
          if ((s[i] in [']','}','>']) and (ord(s[i])=ord(sp^.c)+2)) or
            ((s[i]=')') and (ord(s[i])=ord(sp^.c)+1)) then POPSL(SP);
        end;
    end;
    if net=false then
      begin
        writeln('Skobok v stroke net!');
        exit;
      end;
    if Emptystack(SP) then writeln('Skobki rasstavleni pravilno!')
      else writeln('Skobki rasstavleni nepravilno!')
end.

[мисс_граффити]

моя ошибка...

if ((s[i] in [']','}','>']) and (ord(s[i])=ord(sp^.c)+2)) or
            ((s[i]=')') and (ord(s[i])=ord(sp^.c)+1))

лучше так:

if ((s[i] in [']','}','>']) and (ord(s[i])=ord(sp^.c)+2)) or
            ((s[i]=')') and (sp^.c='('))

[Neon6868]

моя ошибка...

if ((s[i] in [']','}','>']) and (ord(s[i])=ord(sp^.c)+2)) or
            ((s[i]=')') and (ord(s[i])=ord(sp^.c)+1))

лучше так:

if ((s[i] in [']','}','>']) and (ord(s[i])=ord(sp^.c)+2)) or
            ((s[i]=')') and (sp^.c='('))

Спасибо, но я так оставлю!

[klem4]

Ну во первых ты память забываешь освободить, стек ведь в конце программы не всегда пустой, а вот мой вариант:

{$B-}
const
  close  = ')]}>';
  open   = '([{<';
type
  PTStack = ^TStack;
  TStack = Record
    _break: Char;
    next: PTStack;
  end;

procedure Push(var T: PTStack; const _break: Char);
var
  temp: PTStack;
begin
  New(temp);
  temp^._break := _break; temp^.next := nil;

  if T = nil then T := temp else begin
    temp^.next := T; T := temp;
  end;
end;

function Pop(var T: PTStack): Char;
var
  temp: PTStack;
begin
  Pop := T^._break; temp := T;
  T := T^.next; Dispose(temp);
end;

procedure Destroy(var T: PTStack);
var
  temp: PTStack;
begin
  while (T <> nil) do begin
    temp := T;
    T := T^.next;
    Dispose(T);
  end;
end;

var
  T: PTStack;
  S: String;
  i: Integer;
  stop: Boolean;
begin
  write('s = '); readln(s);

  T := nil; i := 1; stop := false;

  repeat
    if Pos(s[i], open) <> 0 then Push(T, close[pos(s[i], open)]);
    stop := (Pos(s[i], close) <> 0) and ((T = nil) or (s[i] <> Pop(T)));
    inc(i);
  until (i > Length(s)) or (stop);

  if not(stop) and (T = nil) then writeln('good') else writeln('bad');

  Destroy(T);
end.