IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Стек, Помогите исправить программу
сообщение
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 146
Пол: Мужской

Репутация: -  0  +


Задание: С клавиатуры вводится текст, содержащий 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.

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Помощник капитана
****

Группа: Пользователи
Сообщений: 601
Пол: Мужской
Реальное имя: Артем

Репутация: -  2  +


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


--------------------
Dum spiro spero!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


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

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


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Пионер
**

Группа: Пользователи
Сообщений: 146
Пол: Мужской

Репутация: -  0  +


А нельзя сделать так, чтобы из стека ничего не удалять??
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Помощник капитана
****

Группа: Пользователи
Сообщений: 601
Пол: Мужской
Реальное имя: Артем

Репутация: -  2  +


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

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

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


--------------------
Dum spiro spero!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


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

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


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Пионер
**

Группа: Пользователи
Сообщений: 146
Пол: Мужской

Репутация: -  0  +


А как тогда искать скобки в тексте?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


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

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


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






Цитата
Надо проверить, правильно ли расставлены скобки
А в поиске был? Когда-то по этой теме на форуме даже соревнование проводилось, так что как минимум 6 разных вариантов точно есть...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Пионер
**

Группа: Пользователи
Сообщений: 146
Пол: Мужской

Репутация: -  0  +


Цитата(volvo @ 15.04.2007 20:27) *

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


Спасибо за совет, и правда есть. smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Пионер
**

Группа: Пользователи
Сообщений: 146
Пол: Мужской

Репутация: -  0  +


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

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

Вот программа:
 
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.

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Пионер
**

Группа: Пользователи
Сообщений: 146
Пол: Мужской

Репутация: -  0  +


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

Код

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.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


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


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Пионер
**

Группа: Пользователи
Сообщений: 146
Пол: Мужской

Репутация: -  0  +


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

Код

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.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


моя ошибка...
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='('))


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Пионер
**

Группа: Пользователи
Сообщений: 146
Пол: Мужской

Репутация: -  0  +


Цитата(мисс_граффити @ 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='('))



Спасибо, но я так оставлю!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #17


Perl. Just code it!
******

Группа: Пользователи
Сообщений: 4 100
Пол: Мужской
Реальное имя: Андрей

Репутация: -  44  +


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

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




--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 28.03.2024 19:49
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name