VPF::Парсинг строки со скобками - Форум программистов

tonchitos

Дата 2.8.2008, 17:20 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 447
Регистрация: 24.2.2007

Репутация: нет
Всего: 40

Люди, у меня есть логическое выражение
Бинарное дерево вычисляет результат этого логического выражения
В классе дерева же парсится строка с логическим выражением...

У меня со скобками проблемы, не соображу как их парсить...

Код


struct cNode
{
    //AssociationToType m_association1;
    //AssociationToType m_association2;
    CString        m_strName1; // Строковые операнды... Значение - любое имя
    CString        m_strName2;
    bool        m_bName1;  // Логические операнды - по ним и будет вычисляться дерево
    bool        m_bName2;
    // указатели на поддеревья
    cNode *        m_pLeft;
    cNode *        m_pRight;
    char        m_cSymbol;  // знак операции
};

класс дерева

Код


class cTreeCalc
{
public:
// construction\destruction
    cTreeCalc()
    {
        m_node = 0;
        m_visitorToIsExist = new myConstDefinitionVisitor(true, true);
        m_pModel = 0;
    }
    ~cTreeCalc()
    {
    }
//attributes

    // операнды
    // знак операции

//operations
    cNode * m_node;  // узел
    myConstDefinitionVisitor * m_visitorToIsExist;  // это не существенно
    Model * m_pModel;  // это указатель на фигню которая не важна щас

ф-ия вычисления по дереву
    bool treeResult(cNode * pNext)
    {   
        if (pNext->m_strName1.GetAt(0)=='!')
        {
            pNext->m_strName1.Delete(0,1);     // Если первый знак - логическое отрицание, то мы его удаляем
            pNext->m_bName1 = !m_visitorToIsExist->isExistType(*(m_pModel), pNext->m_strName1);  
//m_visitorToIsExist - ф-ия, кготорая в зависимости от значения строкового операнда возвращает либо ложь либо истину (объект с //таким именем существует) и логическому операнду присваивается значение... Это не очень важно, тк вычисление идет по //логическим операндам, просто их значение от строк зависит
        }
        if (pNext->m_strName2.GetAt(0)=='!')
        {
            pNext->m_strName2.Delete(0,1);    
            pNext->m_bName2 = !m_visitorToIsExist->isExistType(*(m_pModel), pNext->m_strName2);    
        }

        bool bName1;
        bool bName2;
        // Функция получает результат по дереву
        if (pNext->m_pLeft) 
            bName1 = treeResult(pNext->m_pLeft);
        else 
            bName1 = pNext->m_bName1;

        if (pNext->m_pRight) 
            bName2 = treeResult(pNext->m_pRight);
        else 
            bName2 = pNext->m_bName2;
        switch(pNext->m_cSymbol)
        {
            case '!':
                return (!bName1);
            case '*': 
                return (bName1 && bName2);
            case '+': 
                return (bName1 || bName2);
            case '^': 
                return(bName1 && !bName2);
            
        }
        return 0;
    }

    int getRang(char c)
    {
        if (c == '!')
            return 3;
        if (c == '*')
            return 2;
        if ((c == '+')||(c == '^'))
            return 1;
        else 
            return 0;
    }

    char * GetNameFromLine(char * strLine)
    {
// ф-ия получает имя операнда в строке
        char * str = new char;
        int i;
        int j = 0;

        for(i=0; ((!((strLine[i]=='!')&&(i!=0)))&&(strLine[i]!=NULL)&&(strLine[i]!='(')&&(strLine[i]!=')')&&(strLine[i]!='*')&&(strLine[i]!='+')&&(strLine[i]!='^')); i++)
        {
            str[j] = strLine[i];
            j++;
            
        }
        str[j] = NULL;
        return str;
        
    }
//ф-ия формирующая дерево по строке
    void FormTree(char *s, cNode *& pNext, Model * pModel) // По строке формирует бинарное дерево
    {
        int i=0, j;
        cNode *p;
        if (!m_pModel)
            m_pModel = pModel;
        char * str="*+^()"; // Строка со знаками операций

        while((j=(int)strcspn(s+i+1, str))!=strlen(s+i+1))  // Ищем знаки операций в строке
        {
            j+=(i+1);  // j - абсолютный индекс очередного знака операции в строке
            if (pNext==0) // Дерево пустое
            {
                p=new cNode;
                p->m_pLeft = p->m_pRight =0;
                p->m_strName1 = GetNameFromLine(s+i); //получить операнд перед оператором
                p->m_bName1 = m_visitorToIsExist->isExistType(*(pModel),p->m_strName1);
                p->m_strName2 = GetNameFromLine(s+j+1);//получить операнд после оператора
                p->m_bName2 = m_visitorToIsExist->isExistType(*(pModel),p->m_strName2);
                p->m_cSymbol=s[j]; // Знак
                pNext = p;
            }
            else // Дерево не пустое
            {
                p=new cNode;
                p->m_cSymbol=s[j]; // Знак операции для вершины дерева 
                p->m_strName2 = GetNameFromLine(s+j+1); //получить операнд после оператора
                p->m_bName2 = m_visitorToIsExist->isExistType(*(pModel),p->m_strName2);

                p->m_pRight = 0; // Правого поддерева нет
                if (getRang(s[j])>getRang(pNext->m_cSymbol)) // Если ранг операции выше чем у вершины
                { // Новый элемент добавляем вниз и справо от от вершины  
                    // Правое поддерево вершины становится левым поддеревом нового элемента
                    p->m_pLeft=pNext->m_pRight; 
                    p->m_strName1=pNext->m_strName2;
                    p->m_bName1 = m_visitorToIsExist->isExistType(*(pModel),p->m_strName1);

                    pNext->m_pRight=p; // Новый элемент становится правым поддеревом вершины 
                }
                else
                { // Ранг операции нового элемента не больше чем у вершина
                    // Новый элемент становится новой вершиной
                    // Старая вершина будет левым поддеревом нового элемента
                    p->m_pLeft=pNext;
                    pNext=p;
                }
            }
            i=j+1;
        }
    }
};

с бинарными операциями тут все ясно...
с унарной ! не очень, при вычислении проверяю, не стоит ли перед именем - !, но в случае со скобками не прокатывает походу

И совсем неясно со скобками
как с ними быть?

Помогите, и если дерево где-то некрасивое - скажите

--------------------

– Люди забыли эту истину, – сказал Лис, – но ты не забывай: ты навсегда в ответе за всех, кого приручил.

Mayk

Дата 2.8.2008, 18:52 (ссылка)

(нет голосов)

Загрузка ...

^аВаТаР^ сообщение>>

Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: 45
Всего: 134

Цитата(tonchitos @ 2.8.2008, 21:20

)

У меня со скобками проблемы, не соображу как их парсить...

Посмотри статью в вике про обратную польскую нотацию,
или посмотри работу Creenshaw (описанный им РекурсивныйНисходящийПарсер кстати более интуитивно понятен). В вике же уже дан пример RDP, если его обработать напильником(добавить построение дерева,выкинуть ненужное, заменить арифметические действия на логические) , то все пробелмы сразу решены.

--------------------

Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.

tonchitos

Дата 2.8.2008, 19:10 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 447
Регистрация: 24.2.2007

Репутация: нет
Всего: 40

ОПЗ еще надо как то переделать под парсинг логического выражения....

а вот с тем что у мя уже имеется ничего нельзя сделать?

--------------------

– Люди забыли эту истину, – сказал Лис, – но ты не забывай: ты навсегда в ответе за всех, кого приручил.

Mayk

Дата 2.8.2008, 19:32 (ссылка)

(нет голосов)

Загрузка ...

^аВаТаР^ сообщение>>

Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: 45
Всего: 134

Цитата(tonchitos @ 2.8.2008, 23:10

)

а вот с тем что у мя уже имеется ничего нельзя сделать?

можно конечно сделать костыли: вначале считать выражения в скобках (до поиска всех операторов) , потом каким-то образом преобразовывать строку так чтобы скобки убирались[вместо скобочного выражения ставить что-нить другое], но это очень мерзко и противно.

паресеры rdp или rpn гораздо легче реализовать,

Цитата(tonchitos @ 2.8.2008, 23:10

)

ОПЗ еще надо как то переделать под парсинг логического выражения....

с этим проблем меньше. а собственно какие?

--------------------

Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.

tonchitos

Дата 2.8.2008, 19:57 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 447
Регистрация: 24.2.2007

Репутация: нет
Всего: 40

Цитата(Mayk @ 2.8.2008, 19:32

)

А я так когда -то делала
Но в этот раз не буду

Цитата(Mayk @ 2.8.2008, 19:32

)

с этим проблем меньше. а собственно какие?

ммм....

ну вот к примеру реализация опз отсюда
http://www.interface.ru/home.asp?artId=1492

Код


class TStr2PPN {
 AnsiString instr, outstr; //input & output strings
 char curc; //the current character
 int iin; //the index of the input string

char nextChar(); //get the next character
void begin(); //handle plus & minus
void mult_div(); //handle multiplication & division
void symbol(); //handle characters & brackets

public:
TStr2PPN() { //constructor
iin = 1;
}

void convert(char *str); //convert to PPN
AnsiString get_outstr(); //get the output string
};


//get the next character
inline char TStr2PPN::nextChar() {
 if(iin <= instr.Length()) return curc = instr[iin++];
 return curc = '\0';
}

//get the output string
inline AnsiString TStr2PPN::get_outstr(){return outstr;}

//convert to PPN
void TStr2PPN::convert(char *str) {
try {
instr = str;
outstr.SetLength(0);
iin = 1;
nextChar();
//begin the convertation
begin();
if(iin != (instr.Length()+1) // curc != '\0') {
throw Exception("Syntax error");
}
if(!isalpha(instr[instr.Length()]) && instr[instr.Length()]!=')') {
throw Exception("Syntax error");
}
}
catch(...) {throw;}
}

//handle plus & minus
void TStr2PPN::begin() {
try {
mult_div();
while(curc=='+' // curc=='-') {
char temp = curc;
nextChar();
mult_div();
outstr += temp;
}
}
catch(...) {throw;}
}

//handle multiplication & division
void TStr2PPN::mult_div() {
try {
symbol();
while(curc=='*' // curc=='/') {
char temp = curc;
nextChar();
symbol();
outstr += temp;
}
}
catch(...) {throw;}
}

//handle characters
void TStr2PPN::symbol() {
try {
if(curc=='(') {
nextChar();
begin();
if(curc!=')') {
throw Exception("Error: wrong number of brackets");
}
else nextChar();
}
else
if(isalpha(curc)) {
outstr += curc;
nextChar();
}
else {throw Exception("Syntax error");}
}
catch(...) {throw;}
}

наверно это девид блейн написал, она скукоживает мой моск smile

--------------------

– Люди забыли эту истину, – сказал Лис, – но ты не забывай: ты навсегда в ответе за всех, кого приручил.

tonchitos

Дата 2.8.2008, 20:36 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 447
Регистрация: 24.2.2007

Репутация: нет
Всего: 40

Код


#include <stdio.h>
 #include <malloc.h>
 
 int sp = 0;
 int stack[1000];
 int pop(void) {
     if (sp > 0) {
          return stack[--sp];
     } else { 
          fprintf(stderr, "Невозможно выполнить POP для пустого стека.\n");
          return 0;
     }
 };
 void push(int a) {
     stack[sp++] = a;
 };
 int empty() {
     return (sp == 0);
 }
 
 int main() {
     int i;
     while (!feof(stdin)) {
         int c = getchar();
         int x;
         switch (c) {
             case '\n':
             case ' ' : break;
             case '=' : printf("Result = %d\n", s.pop()); break;
             case 27  : goto RESULT;
             case '+' : push(pop() + pop()); break;
             case '-' : push(-pop() + pop()); break;
             case '*' : push(pop() * pop()); break;
             default:
                 ungetc(c, stdin);
                 if (scanf("%d", &x) != 1) {
                     fprintf(stderr, "Can't read integer\n");
                     return -1;
                 } else {
                     s.push(x);
                 }
                 break;
          }
    }
 RESULT:
     i = 0;
     while ( !empty() ){
         printf("Stack[%d] = %d\n", i,  s.pop());
         i++;
     }
     return 0;
 }

вот простой пример...
но у меня операнды - строки... понимаете?
мне делать вместа массива интов массив строк?

--------------------

– Люди забыли эту истину, – сказал Лис, – но ты не забывай: ты навсегда в ответе за всех, кого приручил.

Mayk

Дата 2.8.2008, 20:39 (ссылка)

(нет голосов)

Загрузка ...

^аВаТаР^ сообщение>>

Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: 45
Всего: 134

Цитата(tonchitos @ 2.8.2008, 23:57

)

ну вот к примеру реализация опз отсюда

нет. это реализация рекурсивного спуска в ходе которого строится ОПЗ.
Собственно самого рекурсивного спуска достаточно для построения дерева.

Цитата(tonchitos @ 2.8.2008, 23:57

)

наверно это девид блейн написал, она скукоживает мой моск

почитай лучше Криншау или википедию - там лишнего мусора меньше.

--------------------

Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.

tonchitos

Дата 2.8.2008, 20:41 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 447
Регистрация: 24.2.2007

Репутация: нет
Всего: 40

прочитала что ппз хороша для реализации а не для компиляции )))

ну в общем если у кого будут соображения как мне быть - буду рада...
может как то с тем что есть по другому мона

Добавлено через 2 минуты и 54 секунды

Цитата(Mayk @ 2.8.2008, 20:39

)

а где мона почитать?

Цитата(Mayk @ 2.8.2008, 20:39

)

почитай лучше Криншау

буков много, кода мало, дядинька майк, попроще есть че нить?

Добавлено через 12 минут и 17 секунд
по идее по моему приекрасно можно присобачить разбор выражения со скобками к тому что у мя уже написано в первом посте...

По идее находится первые скобки, без вложенных внутри скобок... Выражение внутри - передается в ф-ию, по нему строится дерево, соответственно берем верхний узел этого дерева как операнд...
ток не соображу как реализовать

--------------------

– Люди забыли эту истину, – сказал Лис, – но ты не забывай: ты навсегда в ответе за всех, кого приручил.

tonchitos

Дата 2.8.2008, 21:03 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 447
Регистрация: 24.2.2007

Репутация: нет
Всего: 40

Наверно так

(a+b +(a*!b)+(a^b*c))*a+(c+!a)

сначала я беру первую скобку и отправляю реккурсивно на построение дерева вот енто
a+b +(a*!b)+(a^b*c)

потом следующая скобка и я вычисляю это a*!b

причем запоминаю индекс закрывающей скобки и после выхода из рекурсивного витка - вычисляю от него

--------------------

– Люди забыли эту истину, – сказал Лис, – но ты не забывай: ты навсегда в ответе за всех, кого приручил.

Mayk

Дата 4.8.2008, 05:34 (ссылка)

(нет голосов)

Загрузка ...

^аВаТаР^ сообщение>>

Профиль
Группа: Участник
Сообщений: 2616
Регистрация: 22.5.2005
Где: за границей разум а

Репутация: 45
Всего: 134

Цитата(tonchitos @ 3.8.2008, 00:41

)

а где мона почитать?

Цитата(tonchitos @ 3.8.2008, 00:41

)

буков много, кода мало, дядинька майк, попроще есть че нить?

почитай первые 2-3 главы. Этого достаточно. Тем более что он там нередко повторяется в стиле "помните что мы сделали прошлым летом? делаем ещё раз".

Цитата(tonchitos @ 3.8.2008, 00:36

)

мне делать вместа массива интов массив строк?

нет, массив node'ов (struct cNode).

Это сообщение отредактировал(а) Mayk - 4.8.2008, 05:35

--------------------

Здесь был кролик. Но его убили.
Человеки < кроликов, йа считаю.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »