Форум программистов, компьютерный форум 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++ Дерево дерево, странное дерево
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
12.03.2011, 15:21  [ТС]     Дерево разбора #21
Нашел ошибочку...

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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() && str.find('(') != std::string::npos)
        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);
}
Так, все работает нормально, ранее он вызывал и вторую функцию... Теперь все верно...

Только остается 1 вопрос, который я решить никак не могу... Ну допустим у нас есть дерево и функция insert в нем выглядит след. образом.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void tree_node::insert_h(T val_)
{
    if(left && val_ <= val)
       left->insert_h(val_);
    else if(!left && val_ <= val)
       left=new tree_node(val_);
    else if(right && val_ > val)
       right->insert_h(val_);
    else
       right=new tree_node(val_);
}
 
void tree::insert(T val_)
{
    !curr ? curr=new tree_node(val_) : curr->insert_h(val_);
}
Допустим есть структура Token с приоритетами.
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
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;
};
У каждого токена есть приоритет... Если оператор сравнения делать по приоритету, т.е.
C++
1
2
3
4
5
6
7
8
bool operator <(const Token& f, const Token& s)
{
    return f.GetPrior() < s.GetPrior();
}
bool operator <=(const Token& f, const Token& s)
{
    return f.GetPrior() <= s.GetPrior();
}
Допустим есть выражение
3+4*7-5
Имеем при такой вставке
__________+
_____3 ______*
___5____-
__4
_7

При приоритетах соответственно число - 1, + - 2, * - 3...
Следовательно не вариант... Вообщем я немного в ступоре...

Что можете подсказать по этому поводу?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
12.03.2011, 16:14     Дерево разбора #22
Цитата Сообщение от ForEveR Посмотреть сообщение
При приоритетах соответственно число - 1, + - 2, * - 3...
какие у тебя приоритеты не пойму..

Добавлено через 4 минуты
если разбор идет слева направо дерево должно получится таким
Bash
1
2
3
4
      +
  3        -
        *       5
     4    7
Добавлено через 2 минуты
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
#include <string>
#include <iostream>
#include <sstream>
#include <cassert>
 
enum Type{PLUS,MUL,VAL};
 
struct Node;
 
struct Node
{ 
   Type type;
   Node* left, *right;
   int data;
   bool reverse; 
};
 
void recurs( std::string str, Node* node )
{
  
   int i, c; 
   bool reverse; 
   std::cout << str << std::endl; 
   static const std::string c_str = "+-*/()"; 
   for( unsigned t = PLUS; t < VAL; ++t )
      for( i=0, c=0;i<str.size();++i )
      {
          size_t pos = c_str.find( str[i] ); 
          if( pos == 4 )
            ++c;
          else if( pos == 5 )
            --c;
          else if( !c && pos < (t==PLUS?2:4) )
          {
            node->left = new Node;
            node->right = new Node; 
            node->type = static_cast<Type>( t ); 
            node->reverse = pos % 2;
            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 ) + (node->reverse ? 
                                    - recurs( node->right ) :
                                    + recurs( node->right ) )  ;
      break; 
    case MUL:
      val = recurs( node->left ) * (node->reverse ? 
                                     1.0/recurs( node->right ) :
                                     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 = "3+4*7-5";
   Node* node = new Node;;
   recurs( str, node );
   std::cout << "result = " << recurs( node );  
}
добавил -/
унарный минус за бортом
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
12.03.2011, 19:42  [ТС]     Дерево разбора #23
М... Вот что вышло.

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
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
#include <iostream>
#include <string>
#include <algorithm>
#include <sstream>
#include <stack>
 
template<class T>
class Tree
{
public:
    struct Node
    {
        Node(T elem_):elem(elem_), left(0), right(0)
        {
        }
        Node* left;
        Node* right;
        T elem;
        void in_order_print_helper()
        {
            if(left)
            {
                std::cout<<'\t';
                left->in_order_print_helper();
            }
            std::cout<<'\t'<<elem<<'\n';
            if(right)
            {
                std::cout<<'\t';
                right->in_order_print_helper();
            }
        }
        int in_order_count_helper()
        {
            int val=0;
            switch(elem.GetKind())
            {
            case '+':
                {
                    val=left->in_order_count_helper() + 
                        right->in_order_count_helper();
                }
                break;
            case '-':
                {
                    val=left->in_order_count_helper() -
                        right->in_order_count_helper();
                }
                break;
            case '*':
                {
                    val=left->in_order_count_helper() *
                        right->in_order_count_helper();
                }
                break;
            case Token::number:
                {
                    val=elem.GetNumb();
                }
            }
            return val;
        }
    };
    Tree():curr(0)
    {
    }
    Node* curr;
    void in_order_print()
    {
        curr->in_order_print_helper();
    }
    int in_order_count()
    {
        return curr->in_order_count_helper();
    }
};
 
class Token
{
public:
        enum Type {add='+', multi='*', sub='-', div='/',
            number='8', No};
        Token(Type type_=No, int t_=0):
          type(type_), t(t_)
        {
        }
        const Type GetKind() const
        {
                return type;
        }
        const int GetNumb() const
        {
                return t;
        }
private:
        int t;
        Type type;
};
 
std::ostream& operator <<(std::ostream& os, const Token& tok)
{
    if(tok.GetKind() != Token::number)
        os<<static_cast<char>(tok.GetKind());
    else
        os<<tok.GetNumb();
    return os;
}
 
class Parser
{
public:
        Parser():sem_tree(Tree<Token>())
        {
        }
        void create_tree(Tree<Token>::Node** s_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(Tree<Token>::Node** s_tree, 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);
}
 
int toInt(const std::string& some)
{
    int one;
    std::stringstream ss(some);
    ss>>one;
    return one;
}
 
template<class TernaryFunction>
std::pair<std::string, std::string> Parser::create_tree_helper(Tree<Token>::Node** s_tree, 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];
                        *s_tree=new Tree<Token>::Node(Token(static_cast<Token::Type>(c), 0));
                        left.resize(left.size()-1);
                }
                std::cout<<c<<'\n'<<left<<'\n'<<right<<'\n';
                std::cout<<'\n';
                if(isNumeric(left))
                {
                    (*s_tree)->left=new Tree<Token>::Node(Token(Token::number, toInt(left)));
                    left.clear();
                }
                if(isNumeric(right))
                {
                    (*s_tree)->right=new Tree<Token>::Node(Token(Token::number, toInt(right)));
                    right.clear();
                }
                state=true;
                break;
        }
        else
                continue;
        }
        return std::make_pair(left, right);
}
 
void Parser::create_tree(Tree<Token>::Node** s_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(s_tree, str, find_first_without_brakes);
        if(left_right.first.empty() && left_right.second.empty() && str.find('(') != std::string::npos)
            left_right=create_tree_helper(s_tree, str, find_first_in_brakes);
        left=left_right.first;
        right=left_right.second;
        if(!left.empty())
                create_tree(&(*s_tree)->left, left);
        if(!right.empty())
                create_tree(&(*s_tree)->right, 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(&one.sem_tree.curr, std::string("(10+1)*(5+6*(3+1))+4*(3+1)"));
        one.sem_tree.in_order_print();
        std::cout<<one.sem_tree.in_order_count()<<'\n';
        return 0;
}
Считает верно. Собственно вот такой полубыдлокод) Буду усовершенствовать... Стоит думаю сделать производный класс от бинарного дерева (дерево разбора) - и работать с ним соответственно. Ну а пока как-то так.
Iron Bug
12.03.2011, 20:49
  #24

Не по теме:

Цитата Сообщение от alex_x_x Посмотреть сообщение
про него говорят, что он либо не нужен, потому что слишком сложен для задачи, либо не нужен потому что становится слишком тормозным для нее
вообщем не вижу смысла в учебной программе использовать черноящиковые алгоритмы разбора
boost::spirit действительно довольно медленный,хотя ничуть не сложный. хорошая замена spirit'у - boost::expressive.
вообще, существует много генераторов парсеров и LL, и LR, в том числе очень, очень быстрых. но для учебной работы это не годится, соглашусь

ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
13.03.2011, 01:34  [ТС]     Дерево разбора #25
Кстати, еще вопрос. Под парсинг разных вещей нужно будет переделывать код? Универсальность некая впринципе возможна?
Допустим парсим выражения +-*/ или же &| - отличия минимальные?
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
13.03.2011, 01:35     Дерево разбора #26
В принципе, я думаю, да, ведь как-никак & - эквивалент *, а | - эквивалент +.
alex_x_x
бжни
 Аватар для alex_x_x
2441 / 1646 / 84
Регистрация: 14.05.2009
Сообщений: 7,163
13.03.2011, 01:50     Дерево разбора #27

Не по теме:

Цитата Сообщение от Iron Bug Посмотреть сообщение
boost::spirit действительно довольно медленный,хотя ничуть не сложный. хорошая замена spirit'у - boost::expressive.
вообще, существует много генераторов парсеров и LL, и LR, в том числе очень, очень быстрых. но для учебной работы это не годится, соглашусь
честно не пробовал, пока еще руки не доходили .. =)


Цитата Сообщение от ForEveR Посмотреть сообщение
Кстати, еще вопрос. Под парсинг разных вещей нужно будет переделывать код? Универсальность некая впринципе возможна?
Допустим парсим выражения +-*/ или же &| - отличия минимальные?
серьезный вопрос, если языки построены на одних грамматиках, то один прием пойдет
эти можно сказать эквивалентные (если + - только оставить), но не эквивалентные грамматике с++ например)
вообще прикольно было бы тему по грамматикам замутить
silent_1991
13.03.2011, 01:53
  #28

Не по теме:

Цитата Сообщение от alex_x_x Посмотреть сообщение
вообще прикольно было бы тему по грамматикам замутить
Вот я и говорю, давно хотел что-нибудь подобное написать, но руки пока не доходят)))

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

Не по теме:

ЗЫ ты меня про компиляторы позавчера спрашивал, а сам ты пробовал их писать кстати? Просто интересно стало.

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

была тема пишем интерпретатор, но она кажись не была заточена под теорию
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
13.03.2011, 04:11  [ТС]     Дерево разбора #31
alex_x_x, Ну да... Надо модерам клик кинуть будет... fasked-у например.
Iron Bug
22 / 22 / 0
Регистрация: 06.12.2010
Сообщений: 125
13.03.2011, 11:31     Дерево разбора #32
Цитата Сообщение от alex_x_x Посмотреть сообщение
была тема пишем интерпретатор, но она кажись не была заточена под теорию
а теория там, кстати, не такая сложная. сложнее реализацию соорудить. потому что там уже нужны "алгоритмы с памятью", а не просто конечные автоматы.
я про это дофига всего прочитала в своё время. для работы использую ANTLR и про него много знаю. но посматриваю в сторону bison и yacc. будет время - поковыряю и их. ANTLR - это LL-парсер (строит дерево сверху вниз), а бизон и як - LR (строят его снизу вверх). а так, я использовала и спирит, и экспрессив. но это уже медленнее и более ограниченно, чем специализированные генераторы парсеров вроде ANTLR, бизона или яка. бустовские библиотеки хороши для парсинга строк и строковых выражений. а вот для алгоритмов с возвратом они тормозят, а иногда и вовсе невозможно что-то реализовать.
Ma3a
Эксперт C++
612 / 456 / 31
Регистрация: 28.01.2011
Сообщений: 605
13.03.2011, 16:04     Дерево разбора #33
Если уж заговорили про генераторы, то стоит еще упомянуть еще о двух генераторах парсеров: Accent, генерирующий парсеры Эрли(правда, генерирует не слишком-то оптимальный код, но вроде как работает, да и проект уже давно затух вроде бы) и Elkhound , использующий GLR( обобщенный LR ) алгоритм, работающий хоть и за O(n^3) в худшем случае, как и Эрли, но зато для однозначных грамматик выходит на O(n), где канонический вариант Эрли справляется за O(n^2), что довольно-таки хорошо в плане производительности.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
14.03.2011, 03:26     Дерево разбора
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
14.03.2011, 03:26  [ТС]     Дерево разбора #34
Разобрал проект на файлы + разбил нормально функции по классам, чтобы было удобнее разбираться впоследствии.
Код под катом.

Tree.h
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
#include <iostream>
 
#ifndef _TREE_GUARD_
#define _TREE_GUARD_
 
template<class T>
class Tree
{
protected:
      struct Node
      {
    Node(T elem_):elem(elem_), _left(0), _right(0)
    {
    }
    Node* _left;
    Node* _right;
    T elem;
 
             void in_order_print_helper(std::ostream& os)
             {
         if(_left)
        _left->in_order_print_helper(os);
        os<<elem<<'\n';
         if(_right)
        _right->in_order_print_helper(os);
    }
 
    void delete_helper()
    {
        if(_left)
           _left->delete_helper();
        if(_right)
           _right->delete_helper();
           delete this;
    }
 
             void insert_helper(T val)
             {
                 if(val <= elem && left)
                    _left->insert_helper(val);
                 else if(val <= elem && !left)
                    _left=new Node(val);
                 else if(val > elem && right)
                    _right->insert_helper(val);
                 else
                    _right=new Node(val);
              }
};
public:
    Tree():curr(0)
    {
    }
   ~Tree()
   {
    curr->delete_helper();
    }
    void print_in_order(std::ostream& os)
    {
    curr->in_order_print_helper(os);
    }
    void insert(T val)
    {
        !curr ? curr=new Node(val) : curr->insert_helper(val);
    }
protected:
    Node* curr;
};
 
#endif /*_TREE_GUARD_*/


Token.h
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
#include <string>
#include <utility>
 
#ifndef _TOKEN_GUARD_
#define _TOKEN_GUARD_
 
class Token
{
public:
       enum Type {add='+', multi='*', sub='-', div='/',
        number='8', No};
        Token(Type type_=No, double t_=0.0):
          type(type_), t(t_)
        {
        }
        const Type GetKind() const
        {
            return type;
        }
        const double GetNumb() const
        {
            return t;
        }
 
        friend std::ostream& operator <<(std::ostream&, const Token&);
private:
        double t;
        Type type;
};
 
class Parser
{
public:
        static bool lays_check(const std::string& str);
        static std::string::iterator find_first_in_brakes_helper
            (std::string& some, const char symb);
        static std::pair<std::pair<std::string, std::string>, bool> find_first_in_brakes
            (std::string& some, const char symb);
        static std::string::const_iterator find_first_without_brakes_helper
            (const std::string& some, const char symb);
        static std::pair<std::pair<std::string,std::string>, bool> find_first_without_brakes
            (const std::string& some, const char symb);
};
 
class For_calc
{
public:
    static bool isNumeric(const std::string& some);
    static double toDouble(const std::string& some);
};
 
#endif /*_TOKEN_GUARD_*/


Token.cpp
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
#include "Token.h"
#include "Tree.h"
 
#include <sstream>
#include <algorithm>
#include <stack>
 
std::ostream& operator <<(std::ostream& os, const Token& tok)
{
    if(tok.GetKind() != Token::number)
        os<<static_cast<char>(tok.GetKind());
    else
        os<<tok.GetNumb();
    return os;
}
 
bool For_calc::isNumeric(const std::string& some)
{
        double 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); 
}
 
double For_calc::toDouble(const std::string& some)
{
    double one;
    std::stringstream ss(some);
    ss>>one;
    return one;
}
 
std::string::iterator 
Parser::find_first_in_brakes_helper(std::string& some, const char symb)
{
        std::string::iterator iter;
        size_t idx=0;
        if(*some.begin() == '(' && *(some.begin()+1) == '(')
                iter=std::find(some.rbegin(), some.rend(), symb).base();
        else
                iter=std::find(some.begin(), some.end(), symb);
        if(iter != some.end())
        {
                some.erase(std::find(some.begin(), some.end(), '('));
                some.erase(std::find(some.begin(), some.end(), ')'));
                iter-=1;
        }
        return iter;
}
 
std::pair<std::pair<std::string, std::string>, bool> 
Parser::find_first_in_brakes(std::string& some, const char symb)
{
        if(For_calc::isNumeric(some))
                return std::make_pair(std::make_pair(some, ""), true);
        std::string::iterator iter=find_first_in_brakes_helper(some, symb);
        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 
Parser::find_first_without_brakes_helper
    (const std::string& some, const char symb)
{
        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 == symb)
                {
                        return iter;
                }
        }
        return some.end();
}
 
std::pair<std::pair<std::string,std::string>, bool> 
Parser::find_first_without_brakes
    (const std::string& some, const char symb)
{
        if(For_calc::isNumeric(some))
                return std::make_pair(std::make_pair(some, ""), true);
        std::string::const_iterator iter=find_first_without_brakes_helper(some, symb);
        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);
}
 
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();
}


Sem_Tree.h
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
#include <string>
 
#include "Tree.h"
#include "Token.h"
 
#ifndef _SEM_TREE_GUARD_
#define _SEM_TREE_GUARD_
 
class Sem_Tree:protected Tree<Token>
{
public:
    Sem_Tree():Tree()
    {
    }
    void create_tree(std::string& str)
    {
        create_tree(str, &curr);
    }
    double count()
    {
       return count_helper(curr);
    }
    void print(std::ostream& os)
    {
        print_in_order(os);
    }
private:
    void create_tree(std::string& str, Node** tree_node);
    template<class Function>
    std::pair<std::string, std::string> 
        create_tree_helper(std::string& str, Node** tree_node,
        TernaryFunction foo);
    double count_helper(Node* tree_node);
};
 
#endif /*_SEM_TREE_GUARD_*/


Sem_Tree.cpp
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
#include "Sem_Tree.h"
 
template<class Function>
std::pair<std::string, std::string> 
Sem_Tree::create_tree_helper(std::string &str, Sem_Tree::Node** tree_node, Function 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)
        {
        std::pair<std::pair<std::string, std::string>, bool> pair;
        pair=foo(str, *iter);
        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];
               *tree_node=new Tree<Token>::Node(Token(static_cast<Token::Type>(c), 0));
                        left.resize(left.size()-1);
                }
                std::cout<<c<<'\n'<<left<<'\n'<<right<<'\n';
                std::cout<<'\n';
                if(For_calc::isNumeric(left))
       {
                    (*tree_node)->_left=new Tree<Token>::Node(Token(Token::number, For_calc::toDouble(left)));
           left.clear();
       }
                if(For_calc::isNumeric(right))
       {
                    (*tree_node)->_right=new Tree<Token>::Node(Token(Token::number, For_calc::toDouble(right)));
                    right.clear();
       }
                state=true;
                break;
        }
        else
                continue;
        }
        return std::make_pair(left, right);
}
 
void Sem_Tree::create_tree(std::string& str, Sem_Tree::Node** tree_node)
{
        if(!Parser::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, tree_node,
            Parser::find_first_without_brakes);
        if(left_right.first.empty() && left_right.second.empty() && str.find('(') != std::string::npos)
            left_right=create_tree_helper(str, tree_node, Parser::find_first_in_brakes);
        left=left_right.first;
        right=left_right.second;
        if(!left.empty())
            create_tree(left, &(*tree_node)->_left);
        if(!right.empty())
            create_tree(right, &(*tree_node)->_right);
}
 
double Sem_Tree::count_helper(Node *tree_node)
{
    double val=0.0;
    switch(tree_node->elem.GetKind())
    {
    case Token::add:
        {
            val=count_helper(tree_node->_left) +
                 count_helper(tree_node->_right);
        }
        break;
    case Token::sub:
        {
            val=count_helper(tree_node->_left) -
                 count_helper(tree_node->_right);
        }
        break;
    case Token::multi:
        {
            val=count_helper(tree_node->_left) *
                 count_helper(tree_node->_right);
        }
        break;
    case Token::div:
        {
            val=count_helper(tree_node->_left) /
                 count_helper(tree_node->_right);
        }
        break;
    case Token::number:
        {
            val=tree_node->elem.GetNumb();
        }
        break;
    default:
        throw std::runtime_error("Unexpected token");
    }
    return val;
}
Yandex
Объявления
14.03.2011, 03:26     Дерево разбора
Ответ Создать тему

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

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