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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 72, средняя оценка - 4.78
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
#1

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

12.03.2011, 02:03. Просмотров 10233. Ответов 33

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

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

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

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

Бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой - C++
Дано бинарное дерево. Удалить из дерева часть вершин так, чтобы оставшееся дерево стало пирамидой.

Дано дерево. Распечатать дерево по уровням - C++
Дано дерево. Распечатать дерево по уровням.

Ошибка в функции разбора уравнения - C++
часть программы. функция принимает от пользователя уравнение формата 1x + 2x + 3x = 5 ну, там дальше она должна будет брать коэффициенты...

Получить переменные из строки путём её разбора - C++
Во время работы программы функция задается в виде строки, что имеет формат "axx + bx + c", включая числа, арифметические операции,...

Программа разбора и вычисления значения арифметического выражения - C++
Написать программу разбора и вычисления значения арифметического выражения. На входе программы — строка, содержащая числа, скобки «(» и...

Исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру - C++
Помогите, не могу понять!( Нужно исходное бинарное дерево превратить в бинарное дерево поиска, при этом сохранив его структуру. вот...

33
alex_x_x
бжни
2449 / 1654 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
12.03.2011, 02:19 #2
Лучший ответ Сообщение было отмечено автором темы, экспертом или модератором как ответ
ForEveR, ты с грамматиками знаком, или это не связано с курсом построения трансляторов?
в основе всех подобных задач, как и задач заложенных в компиляторы всех языков программирования лежит построение синтаксического дерева, получение дерева - конечная цель, по нему уже можно считать выражения, генерировать машинный код, выполнять байт код итп
к языку программирования строят грамматики - которые определяют все возможные программы на соответствующем языке (для выражения это все возможные выражения)
методы разбора грамматики позволяют из листинга (цепочки языка) получить дерево

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

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

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

(x&y&z)|t

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

пс построение компиляторов все равно рулит)
1
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
12.03.2011, 02:32  [ТС] #5
alex_x_x, Тогда попробую распросить по сути...

Получается, у нас должна быть некоторая структура Token (при этом у каждого токена есть некий приоритет), мы должны найти операцию, которая будет выполнена позже всего - закинуть ее в корень дерева, дальше уже разбираться с остальным выражением, верно? Пока вопрос лишь один, как определить некий приоритет у операции (насколько я помню у | и & в логике одинаковый приоритет), но т.к. для начала я буду тренироваться на калькуляторе для обычных чисел - вопрос существенен. + как найти некую операцию, которая будет выполняться последней ну и т.д.?
Про приор : я так понимаю, у меня должно быть некое перечисление приоритет, у каждого токена - поле, при конструкции токена - установка приоритета, да?
0
alex_x_x
бжни
2449 / 1654 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
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
чето в таком духе, вроде ничего непреодалимого
если при разборе будет чтото не так значит выражение невалидное
2
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
12.03.2011, 02:58  [ТС] #7
alex_x_x, Красиво. Буду разбираться спасибо.
В итоге при работе с входной строкой получаем алгоритм потипу.

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

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

Цитата Сообщение от ForEveR Посмотреть сообщение
Да, кстати, стоит-ли сначала проверить на валидность расстановки скобок, путем простого прохода по строке выражения, добавляя '(' в стек и удаляя из стека при встрече ')', если размер стека после прохода - ноль - скобки расставлены верно или нет резона и выяснить это лучше при непосредственном обходе?
а хз, скобки тут собсно большую сложность представляют мне кажется
1
HIMen
4144 / 1393 / 39
Регистрация: 12.04.2009
Сообщений: 2,346
12.03.2011, 03:08 #9
ForEveR, если тебе только для вычисления выражений, то польская обратная запись проще и быстрее
1
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
12.03.2011, 03:11  [ТС] #10
HIMen, В том-то и проблема, что не для вычисления. Иначе я бы просто формальную грамматику реализовал, как для калькулятора...
Задания в курсовом вроде : найти кнф, найти днф и т.п.
0
alex_x_x
бжни
2449 / 1654 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
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
ух чет понесло
2
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 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;
}
3
ForEveR
В астрале
Эксперт С++
7979 / 4738 / 321
Регистрация: 24.06.2010
Сообщений: 10,543
Завершенные тесты: 3
12.03.2011, 07:05  [ТС] #13
Скрин
1
Миниатюры
Дерево разбора  
silent_1991
Эксперт С++
4985 / 3042 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
12.03.2011, 13:26 #14
Возможно, вот это дело тоже поможет, давно хочу написать что-нибудь такое, да руки не доходят...

Добавлено через 3 минуты
Ну или вообще вот это, там можно на ссылочки потыкать, почитать про разные варианты.
1
alex_x_x
бжни
2449 / 1654 / 84
Регистрация: 14.05.2009
Сообщений: 7,162
12.03.2011, 13:37 #15
silent_1991, это уже полноценный разбор грамматики
0
12.03.2011, 13:37
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.03.2011, 13:37
Привет! Вот еще темы с ответами:

Что вернет стековая функция разбора пар скобок? - C++
Что вернет функция, если она принимает как параметр такую строку: (5*(x/(y*5))*z)+((1/7)*z*2)-x С точки зрения логики стека.

Процедура разбора полного пути к файлу, представленного строкой - C++
Разработать процедуру (и вспомогательную программу) разбора заданной текстовой строки (задается переменной окружения или параметром...

Что вернет стековая функция разбора пар скобок? - C++
Что вернет функция, проверяющая баланс скобок, если она принимает как параметр такую строку: ((х-((1/х)+у-4)*(z/4+(2-x*3)) Рассмотреть...

Напишите программу, которая бы читала дерево в формате (а) и затем печатала бы это дерево в формате (б). - C++
Представление дерева: а) Д (Б (А, Ф (В,)), Е (,З (Ж, И))) б) Д Б А Ф ...


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru