Форум программистов, компьютерный форум CyberForum.ru

Дерево разбора - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 72, средняя оценка - 4.78
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
12.03.2011, 02:03     Дерево разбора #1
Вообщем суть - нужно уметь распарсить любую логическую формулу и затем сделать с ней нечто по заданию (курсовик). Спросили у препода как лучше, он сказал, что лучше через дерево...
Ну с деревом вопросов нет...
Но вот как распарсить и расставить приоритет у формул - вопрос.

Допустим есть некая формула (x&y&z)|t

Получается дерево должно выглядеть как.
корень - |
лево - (x&y&z)
право - t

Ну и так, далее. Я правильно уловил суть? Вопрос, как расставить так приоритеты, но мне не нужен код, просто некое небольшое объяснение и мысли по этому поводу. Заранее спасибо)
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.03.2011, 02:03     Дерево разбора
Посмотрите здесь:

Напишите программу, которая бы читала дерево в формате (а) и затем печатала бы это дерево в формате (б). C++
C++ Программа разбора и вычисления значения арифметического выражения
C++ Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой
Процедура разбора полного пути к файлу, представленного строкой C++
C++ Дерево дерево, странное дерево
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
12.03.2011, 02:19     Дерево разбора #2
Сообщение было отмечено автором темы, экспертом или модератором как ответ
ForEveR, ты с грамматиками знаком, или это не связано с курсом построения трансляторов?
в основе всех подобных задач, как и задач заложенных в компиляторы всех языков программирования лежит построение синтаксического дерева, получение дерева - конечная цель, по нему уже можно считать выражения, генерировать машинный код, выполнять байт код итп
к языку программирования строят грамматики - которые определяют все возможные программы на соответствующем языке (для выражения это все возможные выражения)
методы разбора грамматики позволяют из листинга (цепочки языка) получить дерево

ну вообщем это если ты вдруг решишь знакомиться с суровой правдой построения трансляторов

ну теперь про дерево

Bash
1
2
3
4
5
                            |
 
          &                                 t
     x        &
            y    z
Добавлено через 9 минут
правда грамматика неоднозначная, те для одного выражения можно построить несколько равносильных деревьев
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
12.03.2011, 02:23  [ТС]     Дерево разбора #3
alex_x_x, Не связано совершенно. Курсовая за второй курс. Задачи вообщем-то по предмету мат. логика...
Посмотрев видео о разборе выражения - походу должно быть как-то так?

(x&y&z)|t

П.С. художник из меня плохой.
Миниатюры
Дерево разбора  
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
12.03.2011, 02:27     Дерево разбора #4
ага, варианты разные могут быть
я тут вспомнил этож задачи на бинарные деревья
но алгоритмов к ним я не помню
хотя вроде просто - находишь корень, левый правый лист, потом для каждого из них рекурсивно повторяешь
так проводишь рекурсивный спуск
а потом по дереву уже обсчитываешь, не очень сложно)

пс построение компиляторов все равно рулит)
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
12.03.2011, 02:32  [ТС]     Дерево разбора #5
alex_x_x, Тогда попробую распросить по сути...

Получается, у нас должна быть некоторая структура Token (при этом у каждого токена есть некий приоритет), мы должны найти операцию, которая будет выполнена позже всего - закинуть ее в корень дерева, дальше уже разбираться с остальным выражением, верно? Пока вопрос лишь один, как определить некий приоритет у операции (насколько я помню у | и & в логике одинаковый приоритет), но т.к. для начала я буду тренироваться на калькуляторе для обычных чисел - вопрос существенен. + как найти некую операцию, которая будет выполняться последней ну и т.д.?
Про приор : я так понимаю, у меня должно быть некое перечисление приоритет, у каждого токена - поле, при конструкции токена - установка приоритета, да?
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
12.03.2011, 02:47     Дерево разбора #6
все так, насчет приоритетов такие соображения

ну можно прикинуть
пускай дано
(10+1)*(5+6*(3+1))+4*(3+1)
есть операции
1) + - операции сложения, мы их в корень в первую очередь ставим
2) * / операции умножения, ставим если в выражении больше нет операций сложения
3) )( пока не достигнут баланс левых и правых скобок

1) ищем +, соблюдая баланс скобок
Bash
1
(10+1)*(5+6*(3+1))               +               4*(3+1)
рекурсия для левой ветви
плюсов не находим, поэтому берем первое умножение с учетом баланса скобок
Bash
1
(10+1)          *           (5+6*(3+1))
рекурсия
скобки выкидываем
берем первый плюс
Bash
1
10        +          1
получили ветвь


Bash
1
2
3
4
                                 +
                 *
       +
 10        1
чето в таком духе, вроде ничего непреодалимого
если при разборе будет чтото не так значит выражение невалидное
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
12.03.2011, 02:58  [ТС]     Дерево разбора #7
alex_x_x, Красиво. Буду разбираться спасибо.
В итоге при работе с входной строкой получаем алгоритм потипу.

Ищем первый плюс вне скобок (если плюса/минуса нет ищем умножение/деление) - если ничего нет - выход, выражение явно неверно.
Нашли - помещаем плюс в дерево, запускаем рекурсию для левой части строки (от знака) ну или не рекурсию, а просто записываем левую и правую части строки в новую строку ищем в левой части, ищем в правой части, по пути убирая скобки и проверяя на все время на корректность. Верно?
Да, кстати, стоит-ли сначала проверить на валидность расстановки скобок, путем простого прохода по строке выражения, добавляя '(' в стек и удаляя из стека при встрече ')', если размер стека после прохода - ноль - скобки расставлены верно или нет резона и выяснить это лучше при непосредственном обходе?
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
12.03.2011, 03:02     Дерево разбора #8
Цитата Сообщение от ForEveR Посмотреть сообщение
Ищем первый плюс вне скобок (если плюса/минуса нет ищем умножение/деление) - если ничего нет - выход, выражение явно неверно.
1*2*3*4 вполне валидно, если не нашли ищем первое умножение с учетом скобок

Цитата Сообщение от ForEveR Посмотреть сообщение
Нашли - помещаем плюс в дерево, запускаем рекурсию для левой части строки (от знака) ну или не рекурсию, а просто записываем левую и правую части строки в новую строку ищем в левой части, ищем в правой части, по пути убирая скобки и проверяя на все время на корректность. Верно?
да, но без рекурсии тут сложно будет

Цитата Сообщение от ForEveR Посмотреть сообщение
Да, кстати, стоит-ли сначала проверить на валидность расстановки скобок, путем простого прохода по строке выражения, добавляя '(' в стек и удаляя из стека при встрече ')', если размер стека после прохода - ноль - скобки расставлены верно или нет резона и выяснить это лучше при непосредственном обходе?
а хз, скобки тут собсно большую сложность представляют мне кажется
HIMen
 Аватар для HIMen
4104 / 1353 / 39
Регистрация: 12.04.2009
Сообщений: 2,346
12.03.2011, 03:08     Дерево разбора #9
ForEveR, если тебе только для вычисления выражений, то польская обратная запись проще и быстрее
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
12.03.2011, 03:11  [ТС]     Дерево разбора #10
HIMen, В том-то и проблема, что не для вычисления. Иначе я бы просто формальную грамматику реализовал, как для калькулятора...
Задания в курсовом вроде : найти кнф, найти днф и т.п.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
12.03.2011, 04:37     Дерево разбора #11
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include <string>
#include <iostream>
#include <sstream>
#include <cassert>
 
enum Type{PLUS,MUL,VAL};
 
struct Node;
 
struct Node
{ 
   Type type;
   Node* left, *right;
   int data;
};
 
void recurs( std::string str, Node* node )
{
  
   int i, c; 
  
   std::cout << str << std::endl; 
   for( unsigned t = PLUS; t < VAL; ++t )
      for( i=0, c=0;i<str.size();++i )
      {
          if( '(' == str[i] )
            ++c;
          else if( ')' == str[i] )
            --c;
          else if( (t == PLUS ? '+' : '*') == str[i] && !c )
          {
            node->left = new Node;
            node->right = new Node; 
            node->type = static_cast<Type>( t ); 
            std::cout << ( node->type == PLUS ? "+" : "*" ) << std::endl; 
            recurs( str.substr( 0, i ), node->left );
            recurs( str.substr( i+1, str.size() - i ), node->right ); 
            return; 
          }        
      } 
     
   if( str[0] == '(' && str[str.size()-1] == ')' )
   { 
      recurs( str.substr( 1, str.size() - 2 ), node ); 
      return; 
   } 
     
   node->type = VAL;
   std::stringstream istr( std::stringstream::in | std::stringstream::out );
   istr << str;
   istr >> node->data; 
}
 
int recurs( Node* node )
{
  std::cout << "<<" << std::endl;
  int val = 0; 
  switch( node->type )
  {
    case PLUS:  
      val = recurs( node->left ) + recurs( node->right );
      break; 
    case MUL:
      val = recurs( node->left ) * recurs( node->right );  
      break; 
    case VAL:
      val = node->data;
      std::cout << "(" << val << ")" << std::endl;
      break; 
    default:
      assert( 0 );  
      return -1;  
  }   
  delete node; 
  return val; 
} 
 
int main()
{
   std::string str = "(((10+1)*(5+6*(3+1))+4*(3+1)))";
   Node* node = new Node;;
   recurs( str, node );
   std::cout << "result = " << recurs( node );  
}
Bash
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
(((10+1)*(5+6*(3+1))+4*(3+1)))
((10+1)*(5+6*(3+1))+4*(3+1))
(10+1)*(5+6*(3+1))+4*(3+1)
+
(10+1)*(5+6*(3+1))
*
(10+1)
10+1
+
10
1
(5+6*(3+1))
5+6*(3+1)
+
5
6*(3+1)
*
6
(3+1)
3+1
+
3
1
4*(3+1)
*
4
(3+1)
3+1
+
3
1
<<
<<
<<
<<
(10)
<<
(1)
<<
<<
(5)
<<
<<
(6)
<<
<<
(3)
<<
(1)
<<
<<
(4)
<<
<<
(3)
<<
(1)
result = 335
ух чет понесло
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
12.03.2011, 07:01  [ТС]     Дерево разбора #12
Всю ночь сидел быдлокодил... Вот, что получилось. Парсит строки на ура, по всем правилам по идее. Осталось разобраться с запилом в дерево...

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
struct Prior
{
    enum Priority {one=1, two=2, three=3};
};
 
class Token
{
public:
    Token(char c_='0', int t_=0, Prior::Priority pr_=Prior::one):
      c(c_), t(t_), pr(pr_)
    {
    }
    const char GetKind() const
    {
        return c;
    }
    const int GetNumb() const
    {
        return t;
    }
    const Prior::Priority GetPrior() const
    {
        return pr;
    }
private:
    int t;
    char c;
    Prior::Priority pr;
};
 
class Parser
{
public:
    Parser():sem_tree(Tree<Token>())
    {
    }
    void create_tree(std::string& str);
    Tree<Token> sem_tree;
private:
    bool lays_check(const std::string& str);
    template<class TernaryFunction>
    std::pair<std::string, std::string> create_tree_helper(std::string& str, TernaryFunction foo);
};
 
bool isNumeric(const std::string& some)
{
    int one=0;
    std::stringstream ss(some);
    ss >> one;
    std::stringstream ss2;
    ss2<<one;
    return (one && some.find_first_not_of(ss2.str()) == std::string::npos); 
}
 
std::string::iterator find_first_in_brakes_helper(std::string& some, const char first, const char second)
{
    std::string tmp;
    tmp+=first;
    tmp+=second;
    std::string::iterator iter;
    size_t idx=0;
    if(*some.begin() == '(' && *(some.begin()+1) == '(')
        idx=some.find_last_of(tmp);
    else
        idx=some.find_first_of(tmp);
    if(idx != std::string::npos)
    {
        iter=some.begin()+idx;
        some.erase(std::find(some.begin(), some.end(), '('));
        some.erase(std::find(some.begin(), some.end(), ')'));
        iter-=1;
        return iter;
    }
    return some.end();
}
 
std::pair<std::pair<std::string, std::string>, bool> find_first_in_brakes(std::string& some, const char first, const char second)
{
    if(isNumeric(some))
        return std::make_pair(std::make_pair(some, ""), true);
    std::string::iterator iter=find_first_in_brakes_helper(some, first, second);
    if(iter == some.end())
        return std::make_pair(std::make_pair("",""), false);
    std::string begin;
    begin.assign(some.begin(), ++iter);
    std::string end;
    end.assign(iter, some.end());
    return std::make_pair(std::make_pair(begin, end), true);
}
 
std::string::const_iterator find_first_without_brakes_helper(const std::string& some, const char first, const char second)
{
    std::stack<char> lays;
    for(std::string::const_iterator iter=some.begin(); iter != some.end(); ++iter)
    {
        if(*iter == '(')
            lays.push(*iter);
        else if(*iter == ')')
            lays.pop();
        if(lays.empty() && (*iter == first || *iter == second))
        {
            return iter;
        }
    }
    return some.end();
}
 
std::pair<std::pair<std::string,std::string>, bool> find_first_without_brakes(const std::string& some, const char first, const char second)
{
    if(isNumeric(some))
        return std::make_pair(std::make_pair(some, ""), true);
    std::string::const_iterator iter=find_first_without_brakes_helper(some, first, second);
    if(iter == some.end())
        return std::make_pair(std::make_pair("", ""), false);
    std::string res;
    res.assign(some.begin(), ++iter);
    std::string end;
    end.assign(iter, some.end());
    return std::make_pair(std::make_pair(res, end), true);
}
 
template<class TernaryFunction>
std::pair<std::string, std::string> Parser::create_tree_helper(std::string &str, TernaryFunction foo)
{
    const std::string opers="+-*/";
    bool state=false;
    std::string left;
    std::string right;
    for(std::string::const_iterator iter=opers.begin(); iter != opers.end(); iter+=2)
    {
    std::pair<std::pair<std::string, std::string>, bool> pair;
    pair=foo(str, *iter, *(iter+1));
    if(pair.second == true)
    {
        left=pair.first.first;
        right=pair.first.second;
        char c='\n';
        if(opers.find(left[left.size()-1]) != std::string::npos && !left.empty())
        {
            c=left[left.size()-1];
            left.resize(left.size()-1);
        }
        str.clear();
        std::cout<<left<<'\n'<<c<<'\n'<<right<<'\n';
        std::cout<<'\n';
        if(isNumeric(left))
            left.clear();
        if(isNumeric(right))
            right.clear();
        state=true;
        break;
    }
    else
        continue;
    }
    return std::make_pair(left, right);
}
 
void Parser::create_tree(std::string& str)
{
    if(!lays_check(str))
        throw std::runtime_error("Expression is incorrect");
    std::string left;
    std::string right;
    std::pair<std::string, std::string> left_right=create_tree_helper(str, find_first_without_brakes);
    if(left_right.first.empty() && left_right.second.empty())
        left_right=create_tree_helper(str, find_first_in_brakes);
    left=left_right.first;
    right=left_right.second;
    if(!left.empty())
        create_tree(left);
    if(!right.empty())
        create_tree(right);
}
 
bool Parser::lays_check(const std::string& str)
{
    std::stack<char> stck;
    for(std::string::const_iterator iter=str.begin(); iter != str.end(); ++iter)
    {
        if(*iter == '(')
            stck.push(*iter);
        else if(*iter == ')')
            stck.pop();
    }
    return stck.empty();
}
 
int main()
{
    Parser one;
    one.create_tree(std::string("(10+1)*(5+6*(3+1))+4*(3+1)"));
    return 0;
}
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
12.03.2011, 07:05  [ТС]     Дерево разбора #13
Скрин
Миниатюры
Дерево разбора  
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
12.03.2011, 13:26     Дерево разбора #14
Возможно, вот это дело тоже поможет, давно хочу написать что-нибудь такое, да руки не доходят...

Добавлено через 3 минуты
Ну или вообще вот это, там можно на ссылочки потыкать, почитать про разные варианты.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
12.03.2011, 13:37     Дерево разбора #15
silent_1991, это уже полноценный разбор грамматики
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
12.03.2011, 13:39     Дерево разбора #16
alex_x_x, да, но что мешает сделать его для выражения?
Ma3a
Эксперт C++
612 / 456 / 31
Регистрация: 28.01.2011
Сообщений: 605
12.03.2011, 13:47     Дерево разбора #17
Вообще, обратная польская может здесь сработать, так как по сути она обозначает инверсный порядок обхода дерева, когда первым посещаются сыновья узла слева направо, и только потом уже родительский узел, так что запись вида " a b c * +" в принципе в дерево перевести не сложно, набираем операнды в стек, ну и при встрече оператора генерируем узел и цепляем к дереву.
А так я лично, если требуется разобрать что-нибудь маленькое, обычно обхожусь LL-анализом или алгоритмом Эрли (нерационально конечно малость, но зато писать легко), хоть и приходится целую грамматику определять ради этого.

Добавлено через 7 минут
И еще если есть больше желания получить работающий код, чем даже просто интерес к парсингу, чтобы всё от руки набивать, то я бы рекомендовал попробовать генераторы парсеров. К bison'у и flex'у у меня конечно отношение не очень, но вот boost::spirit рекомендовать могу, там грамматику забить не сложно, да и генерация дерева делается по сути очень просто, только позаботиться о рекурсивной обертке для дерева типа
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct Tree;
 
typedef boost::variant<
        boost::recursive_wrapper<Tree>
        , std::string
    > Tree_node;
 
struct Tree
    {
    std::string _operator;
    std::vector<Tree_node> children;
    };
 
BOOST_FUSION_ADAPT_STRUCT(
    Tree,
    (std::string,_operator)
    (std::vector<Tree_node>,children)
    )
Дабы основу для построения дерева обозначить, обозначить синтезируемые атрибуты у правил грамматики необходимые и, если хочется перевести это дерево в своё деревянное представление, то наследуете посещатель узлов дерева от boost::static_visitor и определяете те действия, что нужны.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
12.03.2011, 13:52     Дерево разбора #18
Цитата Сообщение от silent_1991 Посмотреть сообщение
alex_x_x, да, но что мешает сделать его для выражения?
нужно знать про цепочки, грамматики, синтаксические деревья итп отдельная тема
тут же тривиальный подход

Добавлено через 2 минуты
Цитата Сообщение от Ma3a Посмотреть сообщение
boost::spirit
про него говорят, что он либо не нужен, потому что слишком сложен для задачи, либо не нужен потому что становится слишком тормозным для нее
вообщем не вижу смысла в учебной программе использовать черноящиковые алгоритмы разбора
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
12.03.2011, 13:53     Дерево разбора #19
Ну, это же было только предложение глянуть пару ссылочек, а не подстрекательство немедленно писать анализатор и больше никого не слушать
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.03.2011, 13:59     Дерево разбора
Еще ссылки по теме:

Что вернет стековая функция разбора пар скобок? C++
Что вернет стековая функция разбора пар скобок? C++
C++ Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Ma3a
Эксперт C++
612 / 456 / 31
Регистрация: 28.01.2011
Сообщений: 605
12.03.2011, 13:59     Дерево разбора #20
alex_x_x, в данном случае я просто предложил, что можно сделать. Да, он не быстрый, писать много надо, да и вообще люди либо любят его, либо ненавидят, известный момент Я лично за польскую запись, а boost просто пришелся к слову, как вариант.
Yandex
Объявления
12.03.2011, 13:59     Дерево разбора
Ответ Создать тему

Метки
дерево
Опции темы

Текущее время: 13:36. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru