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

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

Войти
Регистрация
Восстановить пароль
 
Tokenzier
0 / 0 / 0
Регистрация: 20.01.2011
Сообщений: 15
#1

Работа с деревьями - C++

20.12.2011, 20:28. Просмотров 1083. Ответов 0
Метки нет (Все метки)

Требуется напечатать дерево-формулу в виде формулы и проверить, является ли заданное двоичное дерево деревом-формулой. Проблема в проверке (Метод IsTree)


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
#include "stdafx.h"
#include <stdio.h>
#include <conio.h>
#include <iostream>
#include <string>
#include <fstream>
using namespace std;
 
//Описание структуры дерева - формулы
//-------------------------------------
struct Tree
{
    char symbol;
    Tree *left;
    Tree *right;
};
 
//Определяет является ли двоичное дерево деревом-формулой
bool IsTree(Tree *tree)
{
    bool flag = false, flagL, flagR;
    if (tree != 0)
    {
        flagL = IsTree(tree->left); 
        if ((tree->left == 0) && (tree->right == 0))
            if ((tree->left->symbol > 47) && (tree->left->symbol < 58) || (tree->left->symbol > 96) && (tree->left->symbol < 123))
                flag = true;
        else
            if ((tree->left->symbol == '+') || (tree->left->symbol ==  '-') || (tree->left->symbol == '/') || (tree->left->symbol == '*'))
                flag = true;
        flagR = IsTree(tree->right);
    }
    return (flag && flagL && flagR);
}
 
//Метод вывода дерева - формулы на экран
//-------------------------------------
void PrintTree(Tree *tree)
{
    if (tree != 0)
    {
        if ((tree->left != 0) && ((tree->left->symbol == '+') || (tree->left->symbol == '-')) && ((tree->symbol == '*') || (tree->symbol == '/')))
        {
            cout<<'(';
            PrintTree(tree->left);
            cout<<')';
        }
        else
        {
            PrintTree(tree->left);
        }
            cout<<tree->symbol;
        if ((tree->right != 0) && ((tree->right->symbol == '+') || (tree->right->symbol == '-')) && ((tree->symbol == '*') || (tree->symbol == '/')))
        {
            cout<<'(';
            PrintTree(tree->right);
            cout<<')';
        }
        else
        {
            PrintTree(tree->right);
        }
    }   
}
 
 
//Метод создания дерева - формулы из строки,
//основанный на поиске знака посследнего действия
//и рекурсивном использовании метода к
//левой и правой части строки
//(относительно найденного знака)
//-------------------------------------
Tree* InForm(char form[50])
{
    Tree * tree = new Tree;
    tree->left = 0;
    tree->right = 0;
    int k = 0, s = 0;
    char form1 [50], form2[50];
    bool flag1 = true, flag2 = true;
    
    while (form[s] != NULL)
    {
        s++;
    }
    if (s == 1)
        tree->symbol = form[0];
    else
    {
        for (int i = 0; i < s; i++)
        {
            if (form[i] == '(')
                k++;
            if (form[i] == ')')
                k--;
            if (((form[i] == '+') || (form[i] == '-')) && (k == 0))
            {
                form1[i] = NULL;
                tree->symbol = form[i];
                tree->left = InForm(form1);
                int j = i + 1;
                while (form [j] != NULL)
                {
                    form2[j-i-1] = form [j];
                    j++;
                }
                form2[j-i-1] = NULL;
                tree->right = InForm(form2);
                flag1 = false;
                break;
            }
            form1[i] = form[i];
        }
        if (flag1)
        {
            k = 0;
            for (int i = 0; i < s; i++)
            {
                if (form[i] == '(')
                    k++;
                if (form[i] == ')')
                    k--;
                if (((form[i] == '*') || (form[i] == '/')) && (k == 0))
                {
                    form1[i] = NULL;
                    tree->symbol = form[i];
                    tree->left = InForm(form1);
                    int j = i + 1;
                    while (form [j] != NULL)
                    {
                        form2[j-i-1] = form [j];
                        j++;
                    }
                    form2[j-i-1] = NULL;
                    tree->right = InForm(form2);
                    flag2 = false;
                    break;
                }
            }
        }
        if (flag1 && flag2)
        {
            for (int i = 0; i < (s - 2); i++)
                form[i] = form[i+1];
            form[s-2] = NULL;
            tree = InForm(form);
        }
    }
return tree;
}
 
 
 
void main()
{
    setlocale (LC_ALL, "Russian");
    Tree *tree = new Tree;
    string s;
    char c[] = "((a+c)*(c/b)-2)/a";
    cout<<"Программа вычисления значения формулы введённой из файла,\n при обусловленном массивом значении переменных"<<endl;
    s = "Formula";
    //tree = ReadFileForm(s);
    tree = InForm(c);
    cout<<"Дерево - формула, составленное из прочитанной из файла строки"<<endl;
    cout<<endl;
    PrintTree(tree);
    if (IsTree(tree))
        cout<<"tree - дерево"<<endl;
    else
        cout<<"no"<<endl;
    cout<<endl;
    getch();
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.12.2011, 20:28
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Работа с деревьями (C++):

Работа с деревьями - C++
RECORD * tree(int k) { RECORD *newnode; int nl,nr;//левое и правое поддерево if(k&lt;=0) newnode=0; else { nl = k/2; nr...

работа с нагруженными деревьями в С++ - C++
здравствуйте,собственно возникла ошибка в функции заполнения нагруженного дерева Суть задачи состоит в том,что у нас есть файл со...

Программа. Работа с деревьями. Ошибки КОМПИЛЯЦИИ - C++
Написал программу: #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; //Наша структура struct node { int info;...

Работа с деревьями (Найти все поддеревья, листья которых находятся в заданном диапазоне высот от корня поддерева) - C++
Есть задача: Дано N-дерево. Найти все поддеревья, листья которых находятся в заданном диапазоне высот от корня поддерева. Дайте...

Работа с деревьями - Prolog
Начали учить Пролог, ну как учить, все как всегда, задание дали и вперед... В общем нужна помощь... Буду благодарен. Хотел все задания...

Работа с деревьями - C#
Здравствуйте, помогите пожалуйста. 1. Описать функцию которая: a) печатает узлы непустого дерева при обходе слева направо; б) удаляет...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.12.2011, 20:28
Привет! Вот еще темы с ответами:

Работа с деревьями - Haskell
Дано дерево (необязательно бинарное). Определить путь максимальной длины от корня до листа. Кому не сложно, помогите с задачей

Работа с деревьями - Haskell
Добрый день! Дано бинарное дерево и номер уровня. Вывести список вершин на данном уровне. Кто-нибудь знает как это сделать на Хаскеле?

Работа с деревьями - Turbo Pascal
Написать программы вычисления высоты дерева с использованием представлений левых сыновей и правых братьев. :help:

Работа с деревьями - C#
Здравствуйте! Можете подсказать класс, с помощью которого можно работать с деревьями?


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

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

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