Dz2.3

/*построить дерево бинарного разбора выражения (f+1)*(6/(1+g)+4) */
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string.h>
#include <time.h>
#include <stdlib.h>
using namespace std;
int n = 0;
int step = 0;
struct Btree
{
	char data[100];
	Btree* left;
	Btree* right;
};

int priority(char c) //функция определяет приоритет операции или возвращает -1 если это число
{
	switch (c)
	{
	case'+':
	case'-':
		return 1;

	case'*':
	case'/':
		return 2;
	}
	return 100;
}

void PrintTree(Btree* tree, int space)
{
	const int COUNT = 5;
	if (tree != NULL)
	{
		space += COUNT;
		PrintTree(tree->right, space);
		for (int i = COUNT; i < space; i++)
			printf("%c", ' ');
		printf_s("%s\n", tree->data);
		PrintTree(tree->left, space);
	}
}
int its_a_number(Btree* tree)
{
	int i = 0;
	if (!tree) return 0;
	while (tree->data[i])
		if (!strchr("-0123456789", tree->data[i++]))
			return 0;
	return 1;
}
void calculate(Btree* tree)
{
	while (tree->left->left != NULL && tree->left != NULL)
		calculate(tree->left);
	while (tree->right->right != NULL && tree->right != NULL)
		calculate(tree->right);
	int a, b, c = 0;
	if (!tree || !its_a_number(tree->left) || !its_a_number(tree->right)) return;
	a = atoi(tree->left->data);
	b = atoi(tree->right->data);
	switch (tree->data[0])
	{
	case'+':c = a + b; break;
	case'-':c = a - b; break;
	case'*':c = a * b; break;
	case'/':c = a / b; break;
	}
	free(tree->left);
	free(tree->right);
	sprintf(tree->data, "%d", c);
	step++;
	cout << "result for step   " << step <<"   is   " << c << endl;
	tree->left = NULL;
	tree->right = NULL;
}
void inOrderTravers(Btree* root)
{
	if (root) {
		inOrderTravers(root->left);
		printf("%s ", root->data);
		inOrderTravers(root->right);
	}
}
char** transform(char* string)
{
	int j;
	int t = 0;
	int count = 0;
	int f = 0;
	while (string[f] != '\0') {
		if (!(string[f] > 47 && string[f] < 58 &&
			string[f - 1] > 47 && string[f - 1] < 58))
			n++;
		f++;
	}
	char** newstring = (char**)malloc(n * sizeof(char*));
	for (int i = 0; i < n; i++)
		newstring[i] = (char*)malloc(5 * sizeof(char*));
	while (count < strlen(string))
	{
		j = 0;
		if (isdigit(string[count]) > 0)
		{
			while (isdigit(string[count]) > 0)
			{
				newstring[t][j] = string[count];
				count++;
				j++;
				newstring[t][j] = '\0';
			}
			count--;
		}
		else
		{
			newstring[t][j] = string[count];
			newstring[t][1] = '\0';
		}
		t++;
		count++;
	}
	return(newstring);
}
Btree* let_it_tree(char** term, int first, int last)
{

	Btree* tree = (Btree*)malloc(sizeof(Btree));
	char c;
	int min, i, k, prt;
	int nest = 0;
	if (first == last)
	{
		strcpy(tree->data, term[first]);
		tree->left = NULL;
		tree->right = NULL;
		return tree;
	}
	min = 100;
	for (i = first; i <= last; i++)
	{
		c = term[i][0];
		if (c == '(') { nest++; continue; }
		if (c == ')') { nest--; continue; }
		if (nest > 0) continue;
		prt = priority(c);
		if (prt <= min)
		{
			min = prt;
			k = i;
		}
	}
	if (min == 100 && term[first][0] == '(' && term[last][0]== ')' )
		return let_it_tree(term, first + 1, last - 1);
	else
	{
		strcpy(tree->data, term[k]);
		tree->left = let_it_tree(term, first, k - 1);
		tree->right = let_it_tree(term, k + 1, last);
		return tree;
	}
}

void Tree2(Btree* r)//обратный
{
	int n;
	if (r != NULL)
	{
		Tree2(r->left);
		if (isalpha(r->data[0])>0)
		{
			cout << "Input value for " << r->data[0] << endl;
			cin >> n;
			sprintf(r->data, "%d", n);
		}
		Tree2(r->right);
	}
}
int main()
{

	char* input = (char*)malloc(30 * sizeof(char));
	char Key;
	while (1)
	{
		printf("\n Enter the number - the type of functiom:"
			"\n 1 - TASK FUNCTION ->(f+1)*(6/(1+g)+4)"
			"\n 2 - ANY INPUTTED FUNCTION"
			"\n 3 - EXIT\n");
		fflush(stdin);
		scanf("%c", &Key);
		switch (Key)
		{
		case '1':
		{
		Btree* tree = (Btree*)malloc(sizeof(Btree));
		strcpy(input, "(f+1)*(6/(1+g)+4)");
		char** term = transform(input);
		tree = let_it_tree(term, 0, n - 1);
		PrintTree(tree, 10);
		inOrderTravers(tree);
		cout << "   infix show" << endl;
		Tree2(tree);
		PrintTree(tree, 10);
		cout << "result is " << endl;
		calculate(tree);
		free(tree);
		n = 0;
		step = 0;
		system("pause");
		break;
		}
		case '2':
		{	Btree* tree = (Btree*)malloc(sizeof(Btree));
			cout << "Input your fucntion" << endl;
			cin >> input;
			char** term = transform(input);
			tree = let_it_tree(term, 0, n - 1);
			PrintTree(tree, 10);
			inOrderTravers(tree);
			cout << "   infix show" << endl;
			Tree2(tree);
			PrintTree(tree, 10);
			cout << "result is " << endl;
			calculate(tree);
			free(tree);
			n = 0;
			step = 0;
			system("pause");
			break;
		}
		case '3': return 0;

		default:
			printf("\nIncorrect input! Try again!!!");
			system("cls");
			break;
		}
	}
}