Дерево разбора

@ForEveR · Регистрация: 24.06.2010

Студворк — интернет-сервис помощи студентам

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

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

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

Ну и так, далее. Я правильно уловил суть? Вопрос, как расставить так приоритеты, но мне не нужен код, просто некое небольшое объяснение и мысли по этому поводу. Заранее спасибо)

@ForEveR · 12.03.2011, 15: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 · 12.03.2011, 16:14

Сообщение от ForEveR

При приоритетах соответственно число - 1, + - 2, * - 3...

какие у тебя приоритеты не пойму..

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

Добавлено через 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 · 12.03.2011, 19:42 **[ТС]**

М... Вот что вышло.

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

Не по теме:

Сообщение от alex_x_x

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

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

@ForEveR · 13.03.2011, 01:34 **[ТС]**

Кстати, еще вопрос. Под парсинг разных вещей нужно будет переделывать код? Универсальность некая впринципе возможна?
Допустим парсим выражения +-*/ или же &| - отличия минимальные?

silent_1991 · 13.03.2011, 01:35

В принципе, я думаю, да, ведь как-никак & - эквивалент *, а | - эквивалент +.

@alex_x_x · 13.03.2011, 01:50

Не по теме:

Сообщение от Iron Bug

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

честно не пробовал, пока еще руки не доходили .. =)

Сообщение от ForEveR

Кстати, еще вопрос. Под парсинг разных вещей нужно будет переделывать код? Универсальность некая впринципе возможна?
Допустим парсим выражения +-*/ или же &| - отличия минимальные?

серьезный вопрос, если языки построены на одних грамматиках, то один прием пойдет
эти можно сказать эквивалентные (если + - только оставить), но не эквивалентные грамматике с++ например)
вообще прикольно было бы тему по грамматикам замутить

silent_1991 · 13.03.2011, 01:53

Не по теме:

Сообщение от alex_x_x

вообще прикольно было бы тему по грамматикам замутить

Вот я и говорю, давно хотел что-нибудь подобное написать, но руки пока не доходят)))

@ForEveR · 13.03.2011, 02:00 **[ТС]**

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

Не по теме:

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

@alex_x_x · 13.03.2011, 02:04

Сообщение от ForEveR

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

ну это был не очень полноценный язык с одним одним типом данных, но поддерживал процедуры, ввод-вывод, условия, циклы итп))
и стековую машину к нему
это было небольшой курсовой

была тема пишем интерпретатор, но она кажись не была заточена под теорию

@ForEveR · 13.03.2011, 04:11 **[ТС]**

alex_x_x, Ну да... Надо модерам клик кинуть будет... fasked-у например.

@Iron Bug · 13.03.2011, 11:31

Сообщение от alex_x_x

была тема пишем интерпретатор, но она кажись не была заточена под теорию

а теория там, кстати, не такая сложная. сложнее реализацию соорудить. потому что там уже нужны "алгоритмы с памятью", а не просто конечные автоматы.
я про это дофига всего прочитала в своё время. для работы использую ANTLR и про него много знаю. но посматриваю в сторону bison и yacc. будет время - поковыряю и их. ANTLR - это LL-парсер (строит дерево сверху вниз), а бизон и як - LR (строят его снизу вверх). а так, я использовала и спирит, и экспрессив. но это уже медленнее и более ограниченно, чем специализированные генераторы парсеров вроде ANTLR, бизона или яка. бустовские библиотеки хороши для парсинга строк и строковых выражений. а вот для алгоритмов с возвратом они тормозят, а иногда и вовсе невозможно что-то реализовать.

@Ma3a · 13.03.2011, 16:04

Если уж заговорили про генераторы, то стоит еще упомянуть еще о двух генераторах парсеров: Accent, генерирующий парсеры Эрли(правда, генерирует не слишком-то оптимальный код, но вроде как работает, да и проект уже давно затух вроде бы) и Elkhound , использующий GLR( обобщенный LR ) алгоритм, работающий хоть и за O(n^3) в худшем случае, как и Эрли, но зато для однозначных грамматик выходит на O(n), где канонический вариант Эрли справляется за O(n^2), что довольно-таки хорошо в плане производительности.

@ForEveR · 14.03.2011, 03:26 **[ТС]**

Разобрал проект на файлы + разбил нормально функции по классам, чтобы было удобнее разбираться впоследствии.
Код под катом.

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;
}

@bodya__ · 19.03.2022, 21:48

ForEveR,Привет, спасибо полезно очень, как раз сейчас пишу по такой же теме.

Новые блоги и статьи Все статьи Все блоги /
[golang] Breadth-First Search alhaos 19.05.2026 BFS (Breadth-First Search) — это базовый алгоритм обхода графа в ширину, который поуровнево исследует все связанные вершины. Он начинает с выбранной точки и проверяет всех соседей, прежде чем. . .	[golang] Алгоритм «Хак Госпера» alhaos 17.05.2026 Алгоритм «Хак Госпера» Хак Госпера (Gosper's Hack) — алгоритм нахождения следующего по величине числа с тем же количеством установленных бит. Придуман Биллом Госпером в 1970-х, опубликован в. . .	Рисование бинарного древа до 6-го колена на js, svg. russiannick 17.05.2026 <svg width="335" height="240" viewBox="0 0 335 240" fill="#e5e1bb"> <style> <!]> </ style> <g id="bush"> </ g> </ svg> function fn(){ let rost;/ / высота древа let xx=165,yy=210,w=256;	FSharp: interface of module DevAlt 16.05.2026 Интерфейс модуля F# позволяет управлять доступностью членов, содержащихся в реализации модуля. По-умолчанию все члены модуля доступны: module Foo let x = 10 let boo () = printfn "boo" . . .
Хитросплетение родственных связей пантеона греческих богов. russiannick 14.05.2026 Однооконник, позволяющий узреть и изучить отдельных героев древней Греции. <!DOCTYPE html> <html lang="ru"> <head> <meta charset="UTF-8"> <meta http-equiv="X-UA-Compatible". . .	[golang] Угол между стрелками часов alhaos 12.05.2026 По заданным значениям часа и минуты необходимо определить значение меньшего угла между стрелками аналогового циферблата часов. import "math" func angleClock(hour int, minutes int) float64 { . . .	Debian 13: Установка Lazarus QT5 ВитГо 09.05.2026 Эта инструкция моя компиляция инструкций volvo https:/ / www. cyberforum. ru/ blogs/ 203668/ 10753. html и его же старой инструкции по установке Lazarus с gtk2. . .	Нейросеть на алгоритме "эстафета хвоста" как перспектива. Hrethgir 06.05.2026 На десерт, когда запущу сервер. Статья тут https:/ / habr. com/ ru/ articles/ 1030914/ . Автор я сам, нейросеть только помогает в вопросах которые мне не известны - не знаю людей которые знали-бы. . .

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562

	Дерево разбора 12.03.2011, 02:03. Показов 32894. Ответов 34 Метки дерево (Все метки) Вообщем суть - нужно уметь распарсить любую логическую формулу и затем сделать с ней нечто по заданию (курсовик). Спросили у препода как лучше, он сказал, что лучше через дерево... Ну с деревом вопросов нет... Но вот как распарсить и расставить приоритет у формул - вопрос. Допустим есть некая формула (x&y&z)\|t Получается дерево должно выглядеть как. корень - \| лево - (x&y&z) право - t Ну и так, далее. Я правильно уловил суть? Вопрос, как расставить так приоритеты, но мне не нужен код, просто некое небольшое объяснение и мысли по этому поводу. Заранее спасибо) 1

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	13.03.2011, 01:34 [ТС]
	Кстати, еще вопрос. Под парсинг разных вещей нужно будет переделывать код? Универсальность некая впринципе возможна? Допустим парсим выражения +-*/ или же &\| - отличия минимальные? 0

silent_1991 5058 / 3118 / 271 Регистрация: 11.11.2009 Сообщений: 7,044
	13.03.2011, 01:35
	В принципе, я думаю, да, ведь как-никак & - эквивалент *, а \| - эквивалент +. 1

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	13.03.2011, 02:00 [ТС]
	alex_x_x, Вообщем лучше все же переписывать я так понимаю, чем пытаться найти корректное и удобное обобщение, быстрее получится переписать... Про тему по грамматикам - да, было бы очень интересно посмотреть как реализуются разного вида парсеры и создается разного вида грамматика. Не по теме: ЗЫ ты меня про компиляторы позавчера спрашивал, а сам ты пробовал их писать кстати? Просто интересно стало. 0

@ForEveR В астрале 8049 / 4806 / 655 Регистрация: 24.06.2010 Сообщений: 10,562
	13.03.2011, 04:11 [ТС]
	alex_x_x, Ну да... Надо модерам клик кинуть будет... fasked-у например. 0

@Ma3a 623 / 467 / 57 Регистрация: 28.01.2011 Сообщений: 605
	13.03.2011, 16:04
	Если уж заговорили про генераторы, то стоит еще упомянуть еще о двух генераторах парсеров: Accent, генерирующий парсеры Эрли(правда, генерирует не слишком-то оптимальный код, но вроде как работает, да и проект уже давно затух вроде бы) и Elkhound , использующий GLR( обобщенный LR ) алгоритм, работающий хоть и за O(n^3) в худшем случае, как и Эрли, но зато для однозначных грамматик выходит на O(n), где канонический вариант Эрли справляется за O(n^2), что довольно-таки хорошо в плане производительности. 1

@bodya__ 0 / 0 / 0 Регистрация: 06.11.2020 Сообщений: 4
	19.03.2022, 21:48
	ForEveR,Привет, спасибо полезно очень, как раз сейчас пишу по такой же теме. 0