Задание: С клавиатуры вводится текст, содержащий 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.
А можно поинтересоваться, что именно вызывает затруднения?Поиск скобок?Или запись скобки в стэк?
я бы делала так: нашли открывающуюся скобку - засунули в стек.
нашли закрывающуюся - если последняя в стеке ей соответствует, то убрали ее из стека. не соответствует - значит, строка неправильная, проверять дальше нет смысла.
естественно, не забываем, что к моменту обнаружения закрывающейся стек может быть и пустым.
в конце: если стек пустой - все отлично.
А нельзя сделать так, чтобы из стека ничего не удалять??
Артемий, реализуем твой алгоритм.
строка:
(----{---}---)
1. стек пустой
2. в стеке (
3. в стеке ( {
4. закрывающаяся подходящая, идем дальше
5. ? ошибка?
Neon6868, а зачем так делать? кто нам мешает удалять? имхо, в этом и заключается преимущество использования стека на данной задаче (за счет FIFO. с очередью бы так не получилось)
А как тогда искать скобки в тексте?
const skobki=['(','{','['];
....
for i:=1 to length(s) do
if s[i] in skobki then
...
Помогите кто-нибудь исправить и переделать программу!Если в программе ввести скобки: ()) то должно быть выведено сообщение: "Стек пуст!", но этого не происходит, а выводится сообщение:"Скобки расставлены неправильно!"
И как переделать программу, чтобы в стек записывались все найденные открывающиеся скобки, а не закрывающиеся??
Вот программа:
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.
Я вот сделал, посмотрите пожалуйста нельзя ли проще что-нибудь сделать??
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]
case s[i] of
'(','{','<','[':begin
Push(sp,p,s[i]);
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;
if ((s[i]=')') and (ord(s[i])=ord(sp^.c)+1)) or ((s[i] in ['>','}',']']) and (ord(s[i])=ord(sp^.c)+1)) then...
if net=false then
if not net then
Вот переделал. Теперь нормально??
моя ошибка...
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='('))
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='('))
Ну во первых ты память забываешь освободить, стек ведь в конце программы не всегда пустой, а вот мой вариант:
{$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.