C++ Builder
| Главная | Уроки | Статьи | FAQ | Форум | Downloads | Литература | Ссылки | RXLib | Диски |

 
Разбор строки, Разбор элементарного ариф. выражения
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



Дело в том, что задача не ориентирована на практическое применение (по крайней мере пока ;-)) и для меня имеет ярко выраженый, так сказать, спортивный интерес. biggrin.gif
Буду признателен за помощь!
Георгий
Отправлено: 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 часа ночи ничего лучше получиться не могло biggrin.gif


User Attached Image Скачать файл
testFormula.rar


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

User Attached Image Скачать файл
Chebyshev_2004.11.30_22_05.rar


Георгий
Отправлено: 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Георгий
С исправленным вариантом других глюков пока не обнаружил.
Я тут пытаюсь выкрутиться без использования рекурсии. Уже кучу кода наваял а в едино ещё не связал. sad.gif

Отредактировано vvoid — 30/11/2004, 21:37
Георгий
Отправлено: 30.11.2004, 21:32


Почетный железнодорожник

Группа: Модератор
Сообщений: 874



QUOTE (vvoid @ 30/11/2004, 21:36)
2Георгий
Я тут пытаюсь выкрутиться без использования рекурсии. Уже кучу кода наваял а в едино ещё не связал. sad.gif

на мой взглюд овчинка выделки не стоит

Вернуться в Вопросы программирования в C++Builder