Помощь - Поиск - Пользователи - Календарь
Полная версия: Стек
Форум «Всё о Паскале» > Pascal, Object Pascal > Задачи
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
А нельзя сделать так, чтобы из стека ничего не удалять??
Артемий
Цитата
А нельзя сделать так, чтобы из стека ничего не удалять??

Допустим заносим открывшуюся скобку в стэк - если след. закрывающая совподает,то идем дальше, пока не наткнемся на неправильный вариант -- сразу выдаем ошибку,все, строка левая.А если все гладко - то значит она правильная.может так?
мисс_граффити
Артемий, реализуем твой алгоритм.
строка:
(----{---}---)
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
Цитата(volvo @ 15.04.2007 20:27) *

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


Спасибо за совет, и правда есть. smile.gif
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...

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

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
Цитата(мисс_граффити @ 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
Ну во первых ты память забываешь освободить, стек ведь в конце программы не всегда пустой, а вот мой вариант:

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


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