Помощь - Поиск - Пользователи - Календарь
Полная версия: Стек
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
Neon6868
15.04.2007 17:35
Задание: С клавиатуры вводится текст, содержащий 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.
Артемий
15.04.2007 17:49
А можно поинтересоваться, что именно вызывает затруднения?Поиск скобок?Или запись скобки в стэк?
мисс_граффити
15.04.2007 17:55
я бы делала так: нашли открывающуюся скобку - засунули в стек.
нашли закрывающуюся - если последняя в стеке ей соответствует, то убрали ее из стека. не соответствует - значит, строка неправильная, проверять дальше нет смысла.
естественно, не забываем, что к моменту обнаружения закрывающейся стек может быть и пустым.

в конце: если стек пустой - все отлично.
Neon6868
15.04.2007 18:30
А нельзя сделать так, чтобы из стека ничего не удалять??
Артемий
15.04.2007 18:44
Цитата
А нельзя сделать так, чтобы из стека ничего не удалять??

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

Neon6868, а зачем так делать? кто нам мешает удалять? имхо, в этом и заключается преимущество использования стека на данной задаче (за счет FIFO. с очередью бы так не получилось)
Neon6868
15.04.2007 22:35
А как тогда искать скобки в тексте?
мисс_граффити
15.04.2007 22:59
const skobki=['(','{','['];
....

for i:=1 to length(s) do
  if s[i] in skobki then
...
volvo
15.04.2007 23:27
Цитата
Надо проверить, правильно ли расставлены скобки
А в поиске был? Когда-то по этой теме на форуме даже соревнование проводилось, так что как минимум 6 разных вариантов точно есть...
Neon6868
16.04.2007 3:30
Цитата(volvo @ 15.04.2007 20:27) *

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


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

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

Вот программа:
 
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
21.04.2007 2:53
Я вот сделал, посмотрите пожалуйста нельзя ли проще что-нибудь сделать??

Код

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.
мисс_граффити
21.04.2007 5:01
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...

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

3. 
    if net=false then

if not net then
Neon6868
21.04.2007 17:34
Вот переделал. Теперь нормально??

Код

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.
мисс_граффити
21.04.2007 20:29
моя ошибка...
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
21.04.2007 20:34
Цитата(мисс_граффити @ 21.04.2007 17:29) *

моя ошибка...
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
21.04.2007 22:05
Ну во первых ты память забываешь освободить, стек ведь в конце программы не всегда пустой, а вот мой вариант:

{$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.


Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.