| vvoid |
| Отправлено: 29.11.2004, 17:36 |
|
Машинист паровоза
Группа: Участник
Сообщений: 171
|
Всем приветы!
Есть такая, достаточно интересная задачка, — упростить элементарное арифметическое выражение. Выражение может содержать только строчные латинские буквы (a..z) и знаки "+", "(" и ")".
Вот и всё. Задача сводится к тому, чтобы получить из выражения:
a(b+d)(c+d) выражение:
abc+abd+adc+add
Рассматриваются любые теории.
Заранее спасибо!!!
|
|
| Asher |
| Отправлено: 29.11.2004, 18:08 |
|
Мастер участка
Группа: Модератор
Сообщений: 550
|
Привет.
а по-моему со скобками проще.
всего два сложения и два умножения.
после раскрытия становится
8 умножений и 3 сложения.
|
|
| vvoid |
| Отправлено: 29.11.2004, 18:14 |
|
Машинист паровоза
Группа: Участник
Сообщений: 171
|
Дело в том, что задача не ориентирована на практическое применение (по крайней мере пока ;-)) и для меня имеет ярко выраженый, так сказать, спортивный интерес. 
Буду признателен за помощь!
|
|
| Георгий |
| Отправлено: 29.11.2004, 22:59 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
значит так:
1. идем по строке
2. складируем символы и знаки '+' в "другую" строку пока не наткнёмся на скобку
3. рекурсивно идём на пункт 1
4. определяем символы которые были перед только что найденной скобой
5. подписываем символы полученные в пункте 4 перед каждой последовательностью символов полученных из пункта 3 результат пишем в "другую" строку
6. продолжаем сканирование с места на котором запнулся пункт 3
6. если наткнулись на закрывающуюся скобу или конец строки, то возврат "другой" строки и позиции исходной строки на которой запнулись
ну как? похоже на алгоритм?
|
|
| Георгий |
| Отправлено: 30.11.2004, 03:01 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
похоже я ЭТО сделал| CODE | class Result
{
public:
Result(void):pos(0){};
Result(const Result& r):str(r.str),pos(r.pos){};
Result& operator=(const Result& r)
{
this->str=r.str;
this->pos=r.pos;
return *this;
};
~Result(void){};
AnsiString str; //обработанный результат
int pos; //позиция останова
};
AnsiString GetToken(const AnsiString& str, int &pos)
{
AnsiString token;
for(pos;pos<=str.Length();++pos)
{
if ( str[pos] == '+' ) break;
token+=str[pos];
};
return token;
};
AnsiString MulTwoString(const AnsiString& str1, const AnsiString& str2)
{
AnsiString first, second, res;
int fPos=1;
//ищем элемент первой строки
while( fPos<=str1.Length() )
{
first = GetToken( str1, fPos );
++fPos;
int sPos=1;
while( sPos<=str2.Length() )
{
second = GetToken( str2, sPos );
++sPos;
res+=first+second+"+";
};
};
//откидываем лишний '+'
return res.SubString(1,res.Length()-1);
};
Result Proceed(const AnsiString& source)
{
Result ret;
AnsiString preString;
const int len = source.Length();
//локальные переобозначения
int &i = ret.pos;
AnsiString &anotherString=ret.str;
//сканирование
for(i=0;i<len;++i)
{
//блок анализа
const char Symbol = source[i+1];
const bool isAlpha = isalpha(Symbol);
const bool isAction= (Symbol == '+');
const bool isClose = (Symbol == ')');
const bool isOpen = (Symbol == '(');
//блок принятия решения
const bool add = isAlpha || isAction;
const bool enter=isOpen;
const bool leave=isClose;
//исполнение
if ( add )
{
preString+=Symbol;
if ( isAction )
{
anotherString+=preString;
preString="";
};
Form1->Memo1->Lines->Add(AnsiString("Add symbol '")+Symbol+"'");
}
else if ( enter )
{//вход в рекурсию
Form1->Memo1->Lines->Add(AnsiString(" сформировано '")+anotherString+"'");
Form1->Memo1->Lines->Add(AnsiString(" множитель '")+preString+"'");
++i;//проскакиваем открывающуюся скобку
AnsiString sub = source.SubString(i+1,source.Length());
Form1->Memo1->Lines->Add(AnsiString(" рекурсия '")+sub);
Result r = Proceed( sub );
i+=r.pos;//проскакиваем обработанные символы
Form1->Memo1->Lines->Add(AnsiString(" результат pos=")+IntToStr(r.pos)+" str='"+r.str+"'" );
//формируем новый множитель
if ( !preString.IsEmpty() )
preString=MulTwoString(preString,r.str);
else preString=r.str;
Form1->Memo1->Lines->Add(AnsiString(" новый множитель '")+preString+("'"));
}
else if ( leave )
{
break;
};
};
anotherString+=preString;
return ret;
};
void __fastcall TForm1::Button1Click(TObject *Sender)
{
Result r = Proceed( this->Edit1->Text );
this->Edit2->Text=r.str;
} |
проектик прилагается
PS. за некрасивасть и низкую эффективность кода не пинайте — в 3 часа ночи ничего лучше получиться не могло
|
|
| vvoid |
| Отправлено: 30.11.2004, 17:08 |
|
Машинист паровоза
Группа: Участник
Сообщений: 171
|
Я тут пишу свою реализацию, но решил попутно протетсти реализацию уважаемого Георгия. Программа сбоит при таком тесте:
(a+d)c
Желаю удачи!!!
Отредактировано vvoid — 30/11/2004, 18:11
|
|
| Rius |
| Отправлено: 30.11.2004, 20:08 |
|
Мастер участка
Группа: Участник
Сообщений: 321
|
А вот моя реализация. Только разбор приводящий к вычислению выражения. Писал ещё на третьем курсе в курсовом по мат. статистике, так что не судите строго, хоть маленько и не по теме.
Отредактировано Rius — 30/11/2004, 23:14
|
|
| Георгий |
| Отправлено: 30.11.2004, 20:18 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
действительно глючит. спасибо.
неверно было опрелено действие добавление символа. надо вот так:| CODE | if ( add )
{
if ( isAction )
{
anotherString+=preString+Symbol;
preString="";
}
else {
if ( !preString.IsEmpty() )
preString=MulTwoString(preString,Symbol);
else preString=Symbol;
};
Form1->Memo1->Lines->Add(AnsiString("Add symbol '")+Symbol+"'");
} |
ещё на чем то сбой даёт?
|
|
| vvoid |
| Отправлено: 30.11.2004, 20:34 |
|
Машинист паровоза
Группа: Участник
Сообщений: 171
|
2Георгий
С исправленным вариантом других глюков пока не обнаружил.
Я тут пытаюсь выкрутиться без использования рекурсии. Уже кучу кода наваял а в едино ещё не связал. 
Отредактировано vvoid — 30/11/2004, 21:37
|
|
| Георгий |
| Отправлено: 30.11.2004, 21:32 |
|
Почетный железнодорожник
Группа: Модератор
Сообщений: 874
|
| QUOTE (vvoid @ 30/11/2004, 21:36) | 2Георгий
Я тут пытаюсь выкрутиться без использования рекурсии. Уже кучу кода наваял а в едино ещё не связал. |
на мой взглюд овчинка выделки не стоит |
|
