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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Убрать рамку вокруг окна http://www.cyberforum.ru/cpp-beginners/thread412910.html
Как убрать рамку вокруг окна? Там, где кнопочки закрыть и тд?
C++ Построение графа Помогите пожалуйста написать программу вот задание:Построить копию заданного графа. граф произвольный на ваш выбор. Добавлено через 16 минут up... Добавлено через 49 минут up... http://www.cyberforum.ru/cpp-beginners/thread412901.html
C++ Работа с файлами
Здравствуйте,помогите пожалуйста с решением задачи, Каждая строка текстового файла содержит название города и число его жи-телей. Используя структуру для описания понятия «город», получить назва¬ние...
C++ Метод трапеций
Уважаемые товарищи программисты! Прошу помочь мне с решением данного задания, буду Вам очень признателен! F_1^2 (dx\(x^2+1)), f_3^(-2)cos5xdx, N=20, метод трапеций.
C++ Конструктор при наследовании (классы) http://www.cyberforum.ru/cpp-beginners/thread412886.html
Не могу понять, в чем ошибка, точнее она в конструкторе производного класса... #include <iostream> using namespace std; class MAN { public: MAN(char _name, double _age, char _pol, double...
C++ Дана целочисленная прямоугольная матрица )Дана целочисленная прямоугольная матрица. определить: 1) Количество отрицательных элементов в тех строках которые содержат хотябы один нулевой элемент. 2) номера строк и столбцов всех седловых... подробнее

Показать сообщение отдельно
Tokenzier
0 / 0 / 0
Регистрация: 20.01.2011
Сообщений: 15

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

20.12.2011, 20:28. Просмотров 1060. Ответов 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
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru