#1 02.03.07 17:44
Помощь по с++
Задана строка. Проверить, удовлетворяет ли её структура следующему определению:
<текст> = <элемент> | <элемент> <текст>
<элемент> = а | b | ..| z | (<текст>) | [<текст>] | {<текст>}
другими словами проверит корректность поставленных скобок и чтобы кроме них были только буквы от a до z.
Как мне сделать это используя рекурсию? может кто подкинет идейку. Я уже кучу разных вариантов перепробывал и каждый раз получается, что не 100% проверка идет, ошибки возникают. Помогите пожалуйста.
Offline
#4 02.03.07 19:44
Re: Помощь по с++
Фактически у тебя(как я понял) надо проверить удовлетворяет ли строка регулярному выражению или нет, что как правильно заметил Muxa - эквиваленто проверке является ли выражение корректным для некого конечного автомата. детерминированный конечный автомат - это связанный граф, который имеет точку начала и некие конечные состояния, причем из одной вершины одному условию может соответствовать одна дуга, если больше одной - это недетерминированный. используй детерминированный - ДКА :).
как это выглядит: предположим у тебя есть строка "acdbba" и ДКА - сначала ты находишься в начальной вершине графа, потом идешь по дуге соответствующей первой букве - а, потом по дуге "с" и так далее до конца строки. если ты оказался в вершине соответствующей конечному состоянию - то строка верна, если нет - то неверна.
Соответственно сначала придумай ДКА(на листочке нарисуй) - а потом нетрудно его закодить. Удачи!
Offline
#8 04.03.07 18:51
Re: Помощь по с++
Вот тебе простой рекурсивный алгоритм -
пусть у тебя есть строка, к примеру - "bc(bb{d[qw]})"
перебираешь все символы с начала пока не доходишь до первой закрывающей скобки - дальше смотришь есть ли соответствующая открывающая скобка слева и если есть, то удаляешь фрагмент. если нет - строка не верна. то есть строка "bc(bb{d[qw]})" - превращается в "bc(bb{d})" удалением фрагмента "[qw]". дальше исследуешь строку "bc(bb{d})" - ну и так далее пока скобки не кончатся - строка без скобок - верна. всё - удачи.
Offline
#10 05.03.07 00:21
#11 05.03.07 12:19
#12 05.03.07 17:57
#13 05.03.07 23:41
Re: Помощь по с++
поищи метод рекурсивного спуска
смысл следующий: каждому нетерминалу грамматики ставится в соответствие программная единица (то бишь функция), ну и вызываются они в соответствии с порядком символов в заданной строке, причем вызываются рекурсивно (так как <текст> может содержать <текст>)
типа того
Offline
#14 18.03.07 10:54
Re: Помощь по с++
Если кому интересно, то готовый вариант стал таким:
Код::
#include <stdio.h>
#include <conio.h>
#define maxlength 100
int balance(char str[], int &pos, char simb);
void main()
{
int position=0;
char string[maxlength];
puts("Testing string.");
puts("Enter string:");
gets(string);
if(balance(string, position, ' ')==1)
puts("Yes!");
else
puts("No!");
getch();
}
int balance(char str[], int &i, char simb)
{
while(str[i]!='\0')
{
switch(str[i])
{
case '{' : i++; if(balance(str, i, '{')) break;
return 0;
case '(' : i++; if(balance(str, i, '(')) break;
return 0;
case '[' : i++; if(balance(str, i, '[')) break;
return 0;
case '}' : if(simb=='{') return 1;
return 0;
case ')' : if(simb=='(') return 1;
return 0;
case ']' : if(simb=='[') return 1;
return 0;
}
i++;
}
if(simb==' ') return 1;
return 0;
}Offline
#15 18.03.07 14:15
Re: Помощь по с++
Дональдак, Если ты имеешь ввиду вот эту задачу:
Вводится строка. Определить, является ли эта строка правильной записью «формулы»:
< формула > = < терм > | (< терм >) | (< формула > < знак > < формула >)
< знак > = + | - | * | /
< терм > = < имя > | < целое >
< имя > = < буква > | < имя > < буква > | < имя > < целое >
< целое > = < цифра > | < целое > < цифра >
< буква > = a | b | c | …| z | A | B | C | … | Z
< цифра > = 0 | 1 | 2| . . . | 9.
Например: (28+k*x3)*(exp(x)–sqrt(number1))–abs(z) является правильной записью, а 6x+val*3 – нет.
то ее код:
#include<conio.h>
#include<ctype.h>
#include<stdio.h>
#include<string.h>
int Is_Formula(char skobka)
{
char simvol;
do
{
simvol=getchar();
if(isalpha(simvol))
while(isalpha(simvol=getchar()));
if(isdigit(simvol))
{
while(isdigit(simvol=getchar()));
if(isalpha(simvol))
return 0;
}
switch(simvol)
{
case '+':
case '-':
case '*':
case '/': simvol=getchar();
if((simvol=='+')||(simvol=='-')||
(simvol=='*')||(simvol=='/')||(simvol==')'))
return 0;
}
if(simvol==')') if(skobka==simvol) return 1;
else return 0;
if(simvol=='(') if((Is_Formula(')'))!=1) return 0;
}
while(simvol!='.');
if(skobka==' ') return 1;
return 0;
}
void main()
{
clrscr();
printf("\nVvedite formuly:\n");
if(Is_Formula(' ')==1)
printf("Vernaya formula");
else printf("Formula ne vernaya");
getch();
}
Offline
