э-э-э .. просто скобки., разбор выражений со скобками Опции

[Тёмный Эльф]

Хочу написать прогу, которая разбирает выражения со скобками, например, если
(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]
Подскажите, как быть в такой ситуации?

Сообщение отредактировано: Тёмный Эльф - 19.04.2007 23:43

[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]

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

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

[Тёмный Эльф]

А надо не с конца искать, а продолжать от скобки вперед. т.е. нашел скобку "(", идешь вперед и ищещь соответствующую закрывающую

но если мы будем продолжать от скобки вперед ,то например, такое выражение
(ma(da)ma) прога выведет как
(ma(da)
(da)ma), а надо:
(ma(da)ma)
(da)
или все дело в счетчике? я не совсем поняла его роль , можно пожалуйста поподробнее?

[volvo]

(ma(da)ma)
первая открывающаяся скобка - счетчик присвоим 1...
mа - пропускаем
вторая открывающаяся - увеличим счетчик ( = 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]

Вроде все цивильно

С точки зрения синтаксиса (в логике - не разбирался, поздно уже ) - не совсем...

if (s1[i]=ch_1) kok=kok+1; // <--- Это что, сравнение?
if (s1[i]=ch) kok=kok-1; // и это тоже?

Только в С/С++ сравнение - это двойной знак равенства...

[Тёмный Эльф]

С точки зрения синтаксиса (в логике - не разбирался, поздно уже ) - не совсем...

да равенство неверно было записано.. но там не из-за этого бред выходит.. в логике дело.

Сообщение отредактировано: Тёмный Эльф - 30.04.2007 18:59

[Тёмный Эльф]

Все равно не понимаю, где ошибка!
Вот в мэйн я присваиваю 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 меньше длины строки! хм. а почему здесь "и" ? вроде же...вроде "или" должен стоять! или или. потом проверю)

после этого мы находим положение закрывающейся скобки и запоминаем его: 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);}

Вроде логично.. вот только & там должен стоять или && надо проверить

Сообщение отредактировано: Тёмный Эльф - 30.04.2007 19:23

[volvo]

только & там должен стоять или && надо проверить

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

[Тёмный Эльф]

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

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

[volvo]

Ты упустила еще одно:

while (i <= dlina_stroki && s1[i]!= '(' && s1[i] != '[' && s1[i] != '{' && s1[i] != '<') { i=i+1; }

Обрати внимание на первую части условия - это надо контролировать всегда...

[Тёмный Эльф]

точно. спасибо.