Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 28.04.2024, 20:06   #1
Maxim0101
Новичок
Джуниор
 
Регистрация: 28.04.2024
Сообщений: 2
По умолчанию Решить выражение через структуру "бинарное дерево"

ПАМАГИТЕ уже больше 2 недель не могу сдать лабу. Как изменить код бинарного дерева чтобы он решал пример (3*c*d^x)/(k-1)*(k+c) также в него как-то надо добавить считывание с консоли числа как символ и преобразования его в число. Пример я должен вводить с консоли в виде (3*c*d^x)/(k-1)*(k+c)

что-то подобное я делал для стека, для примера (f+1)/(f-4)+(y+s^w)/(x-s):

#include <iostream>
#include <windows.h>
#include <math.h>
#include <cctype>
using namespace std;

struct Node {
double data; // в стеке/выходном char - нельзя преобразование
Node* next;
};
typedef Node* PNode;

struct Stack {
PNode head;
};

void push(Stack& S, double x)
{
PNode NewNode = new Node;
NewNode->data = x;
NewNode->next = S.head;
S.head = NewNode;
}

double pop(Stack& S)
{
PNode topNode = S.head;
double x;
if (!topNode)
return 0;
x = topNode->data;
S.head = topNode->next;
delete topNode;
return x;
}

int priority(char ch) { // Вычисление приоритета операции
switch (ch)
{
case '(': case ')': return 0;
case '+': case '-': return 1;
case '*': case '/': return 2;
case '^': return 3;
default: return -1;
}
}

string makePostFix(string sin)
{
string sout;
Stack s;
s.head = NULL;
char ch, temp;

for (unsigned int i = 0; i < sin.length(); i++)
{
ch = sin.at(i);
if (isdigit(ch))
{ // Если символ является числом
sout.push_back(ch);
continue;
}
if (ch >= 'a') { sout.push_back(ch); continue; }
if (s.head == NULL || ch == '(') { push(s, ch); continue; }
if (ch == ')')
{
do
{
temp = pop(s);
sout.push_back(temp);
} while (temp != '(');
sout.pop_back();
continue;
}
int pr = priority(ch);
while (s.head != NULL && priority(s.head->data) >= pr)
{
temp = pop(s);
sout.push_back(temp);
}
push(s, ch);
}
while (s.head != NULL) {
char temp = pop(s);
sout.push_back(temp);
}
return sout;
}

double calculate(string str, double* var)
{
Stack s;
s.head = NULL;
char ch;
double arg1, arg2;
for (unsigned int i = 0; i < str.length(); i++)
{
ch = str.at(i);
if (isdigit(ch)) { // Если символ является числом
push(s, ch - '0'); // Преобразуйте символ в число и добавьте его в стек
continue;
}
else if (isalpha(ch)) { // Если символ является буквой
int index = 0;
switch (ch)
{
case 'f': index = 0; break;
case 's': index = 1; break;
case 'w': index = 2; break;
case 'x': index = 3; break;
case 'y': index = 4; break;
}
push(s, var[index]);
continue;
}
arg2 = (double)pop(s);
arg1 = (double)pop(s);
switch (ch)
{
case '+': push(s, arg1 + arg2); break;
case '-': push(s, arg1 - arg2); break;
case '*': push(s, arg1 * arg2); break;
case '/': push(s, arg1 / arg2); break;
case '^': push(s, pow(arg1, arg2)); break;
}
}
return pop(s);
}

int main()
{
SetConsoleOutputCP(1251);

string sin, sout;
double var[5], res;

cout << "Введите f" << endl; cin >> var[0];
cout << "Введите s" << endl; cin >> var[1];
cout << "Введите w" << endl; cin >> var[2];
cout << "Введите x" << endl; cin >> var[3];
cout << "Введите y" << endl; cin >> var[4];
sin = "(f+1)/(f-4)+(y+s^w)/(x-s)";

sout = makePostFix(sin);
cout << endl << sout;

res = calculate(sout, var);
cout << endl << "Результат: " << res << endl;

return 0;
}

Но добавить это в бинарное дерево у меня никак не получается(





это главный исходник от которого я отталкивался:

#include <iostream>
#include <windows.h>
using namespace std;

struct Node {
char data;
Node* left, * right;
};
typedef Node* PNode;

int priority(char ch) // Вычисление приоритета операции
{
switch (ch)
{
case '+': case '-': return 1;
case '*': case '/': return 2;
default: return 0;
}
}
PNode makeTree(string expr, int first, int last)
{
if (expr.empty()) return NULL;
int minPrt, prt, i, k=0, brk = 0;
PNode Tree = new Node;
if (first == last)
{
Tree->data = expr[first];
Tree->left = NULL;
Tree->right = NULL;
return Tree;
}
minPrt = 10;

for (i = first; i <= last; i++)
{
if (expr[i] == '(') { brk++; continue; }
if (expr[i] == ')') { brk--; continue; }
if (brk > 0) continue;
prt = priority(expr[i]);
if (prt <= minPrt)
{
minPrt = prt;
k = i;
}
}

if (minPrt == 10 && expr[first] == '(' && expr[last] == ')')
{
delete Tree;
return makeTree(expr, first + 1, last - 1);
}
Tree->data = expr[k];
Tree->left = makeTree(expr, first, k - 1);
Tree->right = makeTree(expr, k + 1, last);
return Tree;
}

double calculate(PNode Tree, double* var)
{
double arg1, arg2;
if (!Tree->left)
return var[int(Tree->data) - 97];
arg1 = calculate(Tree->left, var);
arg2 = calculate(Tree->right, var);
switch(Tree->data) {
case '+' : return arg1 + arg2;
case '-' : return arg1 - arg2;
case '*' : return arg1 * arg2;
case '/' : return arg1 / arg2;
}
return 100500;
}

void printPostFix(PNode Tree)
{
if (!Tree)
return;
printPostFix(Tree->left);
printPostFix(Tree->right);
cout << Tree->data;
}

int main()
{
SetConsoleOutputCP(1251);
SetConsoleCP(1251);
string s;
double var[5], res;
cout << "Введите а" << endl; cin >> var[0];
cout << "Введите b" << endl; cin >> var[1];
cout << "Введите с" << endl; cin >> var[2];
cout << "Введите d" << endl; cin >> var[3];
cout << "Введите e" << endl; cin >> var[4];
cout << "Введите выражение (a, b, c, d, e): " << endl;
cin >> s;
PNode Tree = makeTree(s, 0, s.length() - 1);
printPostFix(Tree);
res = calculate(Tree, var);
cout << endl << "" << res << endl;
return 0;
}
Изображения
Тип файла: png Скриншот 28.04.24_13.52.26.png (5.6 Кб, 8 просмотров)
Maxim0101 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Создать структуру «бинарное дерево» из элементов файла из символов Аято Миязава C# (си шарп) 0 15.04.2020 20:22
Нужно пояснить/прокомментировать код программы, или коды функций "Добавить" "Удалить" "Обновить(редактировать" "Поиск" "Период") ZIRASS PHP 4 15.06.2016 14:23
Excel (решить задачу через "Поиск решения") pavel...3 Помощь студентам 0 02.06.2016 09:52
Составить программу, реализуя заданное "дерево" через левых и правых сыновей. В программе реализовать оператор RIGHT_SIBLING. NastyaShuvalova C# (си шарп) 0 16.02.2014 17:47