Помощь - Поиск - Пользователи - Календарь
Полная версия: э-э-э .. просто скобки.
Форум «Всё о Паскале» > Современный Паскаль и другие языки > Ада и другие языки
Тёмный Эльф
Хочу написать прогу, которая разбирает выражения со скобками, например, если
(6[0)888]{99} значит, прога выводит
(6[0)
[0)888]
{99}
возникла проблема с алгоритмом. Предположим, выражение представлено ввиде строки. Тогда я ищу первую открывающуюся скобку с начала строки, а затем соответствующую ей закрывающуюся скобку с конца строки и вывожу все ,что между ними, затем ищу вторую открывающуюся скобку ит.д. НО если я введу такое выражение [6(7]8[9]), то если действовать по этому алгоритму выведется совсем не то, что надо, а именно,
[6(7]8[9]
(7]8[9])
[9]
а ведь должно быть
[6(7]
(7]8[9])
[9]
Подскажите, как быть в такой ситуации?
Michael_Rybak
Вообще не очень понятно, чего именно ты хочешь, но если я угадал, то тебе надо идти не с конца - влево, а от той скобки, для которой ищешь пару - вправо.
klem4
Цитата
значит, прога выводит


А то что баланс скобок не соблюден это нормально ?
Тёмный Эльф
Не-е баланс скобок обязателен конечно. Это я сглючила..
Michael_Rybak
В таком случае посмотри обратную польскую запись.
Тёмный Эльф
Пожалуйста помогите разобраться с прогой, всё не могу довести её до ума.
Сейчас она корректно вроде разбирается с выражением, где каждый вид скобок ('(', '[', '{', '<') встречается лишь однажды. Например, если вводим (ma)[pa]<da>, то выводится
(ma)
[pa]
<da>
а если вводим (ma[pa]da)<ya> , то программа выдаст
(ma[pa]da)
[pa]
<ya>
То есть найдя с начала строки скобку, ищем такую же с конца. Потом запоминаем место ,где нашли первую скобку, идем в рекурсию, и так до конца строки.
Но например если вводим (ma)(ma)[pa], то уже возникают проблемы, надо
(ma)
(ma)
[pa], а прога естественно выводит
(ma)(ma)
[pa], потому что ищет такую же скобку с конца! Нет, можно было бы конечно, искатбь закрывающуюся скобку с начала строки, но тогда еси мы введем такое выражение (ma)(ma){pa{pa}da} получится
(ma)
(ma)
{pa{pa}
{pa}
неправильно же! надо
(ma)
(ma)
{pa{pa}da}
{pa}
В-общем, я совсем запуталась..есть ли у кого-нибудь идеи?


#include <stdio.h>
#include <string.h>
#include <conio.h>
int dlina_stroki;
char stroka[80];

void f1 (char s1[80],int i)
{
int n,k; char ch;
while (s1[i]!= '(' && s1[i] != '[' && s1[i] != '{' && s1[i] != '<') {i=i+1;}

switch (s1[i])
{
case '(': {ch=')'; break;}
case '[': {ch=']'; break;}
case '<': {ch='>'; break;}
case '{': {ch='}'; break;}
}
n=i;
i=dlina_stroki;
while (s1[i] != ch) {i=i-1;}
k=i;
for (i=n; i<=k; i++)
printf("%c",s1[i]);
i=n+1;
if (i<dlina_stroki) { printf("\n%c",' '); f1(s1,i);}
}

void main(void)
{ int i;
clrscr();
printf("Enter the string please\n");
gets(stroka);
dlina_stroki=strlen(stroka);
i=0;
f1(stroka,i);
}

Malice
Цитата(Тёмный Эльф @ 26.04.2007 22:16) *

То есть найдя с начала строки скобку, ищем такую же с конца

А надо не с конца искать, а продолжать от скобки вперед. т.е. нашел скобку "(", идешь вперед и ищещь соответствующую закрывающую (Заводишь счетчик, к нему +1, если попадалась открывающая, -1 -закрывающая - на нужной закрывающей счетчик будет = 0).
Тёмный Эльф
Цитата
А надо не с конца искать, а продолжать от скобки вперед. т.е. нашел скобку "(", идешь вперед и ищещь соответствующую закрывающую


но если мы будем продолжать от скобки вперед ,то например, такое выражение
(ma(da)ma) прога выведет как
(ma(da)
(da)ma), а надо:
(ma(da)ma)
(da)
или все дело в счетчике? я не совсем поняла его роль , можно пожалуйста поподробнее?
volvo
(ma(da)ma)
первая открывающаяся скобка - счетчик присвоим 1...
- пропускаем
вторая открывающаяся - увеличим счетчик ( = 2 )
da - пропустили
одна скобка закрылась, уменьшить счетчик ( = 1 )

... продолжать до тех пор, пока счетчик не будет равен 0... А случится это на второй закрывающей скобке... Это и будет скобка, закрывающая первую открытую...
Тёмный Эльф
ну наконец то дошло..спасибо! буду реализовать.. =)
Тёмный Эльф
Хм.. я что-то делаю не так? Не понимаю ,где ошибка. Вроде все цивильно. вроде.

#include <stdio.h>
#include <string.h>
#include <conio.h>
int dlina_stroki;
char stroka[80];

void f1 (char s1[80],int i)
{
int n,k,kok; char ch,ch_1;
while (s1[i]!= '(' && s1[i] != '[' && s1[i] != '{' && s1[i] != '<') {i=i+1;}

switch (s1[i])
{
case '(': {ch=')'; ch_1='(';break;}
case '[': {ch=']'; ch_1='[';break;}
case '<': {ch='>'; ch_1='<';break;}
case '{': {ch='}'; ch_1='{';break;}
}
n=i;
i=n+1;
kok=1;
do
{if (s1[i]=ch_1) kok=kok+1;
if (s1[i]=ch) kok=kok-1;
i=i+1;
} while (kok != 0 & i<=dlina_stroki);
k=i;

for (i=n; i<=k; i++)
printf("%c",s1[i]);
i=n+1;
if (i<dlina_stroki) { printf("\n%c",' '); f1(s1,i);}
}

void main(void)
{ int i;
clrscr();
printf("Enter the string please\n");
gets(stroka);
dlina_stroki=strlen(stroka);
i=0;
f1(stroka,i);
}


Ошибки как таковой нет ,но выдаёт программа полный бред. мой бред.
volvo
Цитата
Вроде все цивильно
С точки зрения синтаксиса (в логике - не разбирался, поздно уже smile.gif ) - не совсем...

if (s1[i]=ch_1) kok=kok+1; // <--- Это что, сравнение?
if (s1[i]=ch) kok=kok-1; // и это тоже?
Только в С/С++ сравнение - это двойной знак равенства...
Тёмный Эльф
Цитата
С точки зрения синтаксиса (в логике - не разбирался, поздно уже smile.gif ) - не совсем...


да равенство неверно было записано.. но там не из-за этого бред выходит.. в логике дело.
Тёмный Эльф
Все равно не понимаю, где ошибка!
Вот в мэйн я присваиваю i=0, после вызываю процедуру
f1(stroka,i);
В процедуре происходит вот что:
сначала мы пробегаем по всей строке в поисках открывающейся скобки

while (s1[i]!= '(' && s1[i] != '[' && s1[i] != '{' && s1[i] != '<') {i=i+1;}. Можно было бы добавить еще сюда условие пока i!=dlina_stroki на случай если открывающейся скобки ниразу не встретилось, тогда в этом случае можно сразу реализовать выход из процедуры с сообщением об ошибке. Ну это ладно. Дальше что.
Предположим нашли мы эту скобку, а дальше я ее определяю, чтобы была известн как открывающаяся скобка, так и закрывающаяся.

switch (s1[i])
{
case '(': {ch=')'; ch_1='(';break;}
case '[': {ch=']'; ch_1='[';break;}
case '<': {ch='>'; ch_1='<';break;}
case '{': {ch='}'; ch_1='{';break;}
}
И после этого идет присваение n=i, это значит положение открывающейся скобки, которую мы нашли.

После этого нужно найти закрывающуюся скобку.
i=n+1; (будем искать закрывающуся скобку начиная со следующего положения)
kok=1; (этот счетчик сколько скобок мы нашли. 1 уже есть потому что одна скобка уже найдена.)

а дальше цикл do-while

do
{if (s1[i]==ch_1) kok=kok+1; (если нашли такую же скобку открытую то прибавим к счетчику)
if (s1[i]==ch) kok=kok-1; (если нашли такую скобку но закрытую, то вычитаем)
i=i+1;
} while (kok != 0 & i<=dlina_stroki); (пока kok не равен нулю и i меньше длины строки! хм. а почему здесь "и" ? вроде же...вроде "или" должен стоять! или или. blink.gif потом проверю)

после этого мы находим положение закрывающейся скобки и запоминаем его: k=i;

for (i=n; i<=k; i++)
printf("%c",s1[i]); //здесь мы печатаем от начальной скобки до конечной найденной.

потом..а здесь я смещаю положение, типа первая скобка была на i=n, а дальше мы прибавляем единичку и начинам проделывать тоже самое, тоесть идем в рекурсию, только уже i будет равно не 0, как изначально, а прибавленная на 1. n будет соответственно каждый раз разное, когда-нибудь i достигнет значиения длины строки и произойдет выход из процедуры, а пока что printf("\n%c",' '); таким образом я пытаюсь перевести укзаатель на новую строчку и вызываем f1(s1,i); с новым значением i
i=n+1;
if (i<dlina_stroki) { printf("\n%c",' '); f1(s1,i);}

Вроде логично.. вот только & там должен стоять или && надо проверить dry.gif
volvo
Цитата
только & там должен стоять или && надо проверить
А чего ты гадаешь? smile.gif & - это побитовая операция, && - логическая... В твоем случае нужна именно логическая, значит &&
Тёмный Эльф
Цитата(volvo @ 30.04.2007 20:28) *

А чего ты гадаешь? smile.gif & - это побитовая операция, && - логическая... В твоем случае нужна именно логическая, значит &&

smile.gif

Добавлено через 15 мин.
Кое-что исправила. & на && заменила, но на каждый мой запрос прога выводила какие-то таинственные "(nu" заменила здесь
for (i=n; i<=k; i++)
printf("%c",s1[i]);
i<=k на i<k,
НО теперь в конце прога выводит не "(nu", а "(n". Откуда это вообще здесь берется?? blink.gif
volvo
Ты упустила еще одно:
while (i <= dlina_stroki && s1[i]!= '(' && s1[i] != '[' && s1[i] != '{' && s1[i] != '<') { i=i+1; }

Обрати внимание на первую части условия - это надо контролировать всегда...
Тёмный Эльф
точно. спасибо.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.