#include <stdio.h>
#include <math.h>
#include <locale.h>
#include <conio.h>
#include <stdlib.h>
#include "ctime"
#include "string.h"
#include "ctype.h"
using namespace std;
struct Tree
{
	char sym[10];
	Tree *Left;
	Tree *Right;
};

int Priority(char c)
{
	switch (c)
	{
	case '+':
	case '-':
		return 1;
	case '*':
	case '/':
		return 2;
	}
	return 100;
}
Tree *CreateTree(char **str, int first, int last)
{

	Tree *elka;
	char c;
	int skobka = 0, minPrt = 100, prt, k = first;
	for (int i = first; i < last; i++)
	{
		c = str[i][0];
		if (isdigit(c) == 0)
		{
			if (c == '(')
				skobka++;
			if (c == ')')
				skobka--;
			if (skobka == 0)
			{
				prt = Priority(c);
				if (prt <= minPrt)
				{
					minPrt = prt;
					k = i;
				}
			}
		}
	}
		if ((minPrt==100)&&(str[first][0] == '(') && (str[last][0] == ')'))
		return CreateTree(str, first + 1, last - 1);
	elka = new Tree;
	strcpy(elka->sym, str[k]);
	bool key = false;
	for (int i = first; i < last; i++)
		if (strchr("+/-*()", str[i][0]) != NULL)
			key = true;
	if (key == true)
	{
		elka->Left = CreateTree(str, first, k - 1);
		elka->Right = CreateTree(str, k + 1, last);
	}
	else
	{
		elka->Left = NULL;
		elka->Right = NULL;
	}
	return elka;
}
void viv(Tree *a, int level)
{
	if (a != NULL)
	{
		viv(a->Left, level + 1);
		for (int i = 0; i < level; i++)
			printf("   ");
		puts(a->sym);
		viv(a->Right, level + 1);
	}
}
char *vvod()
{
	int n;
	bool key;
	char *primer;
	do
	{
		primer = new char[100];
		puts("Введите пример");
		gets(primer);
		n = 0;
		for (int i = 0; i < strlen(primer); i++)
		{
			key = true;
			if (primer[i] == '(')
				n++;
			if (primer[i] == ')')
				n--;
			if (((primer[i] == '/') || (primer[i] == '*')) && ((i == 0) || (primer[i - 1] == '(')))
			{
				puts("Операции * и / не могут быть унарными");
				key = false;
			}
			if (strchr("1234567890qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM+-*/()", primer[i]) == NULL)
			{
				puts("Недопустимые символы");
				key = false;
			}
			if (((primer[i] == '/') || (primer[i] == '*') || (primer[i] == '+') || (primer[i] == '-')) && (primer[i + 1] == ')'))
			{
				puts("после операции должно быть число или переменная");
				key = false;
			}
			if (n < 0)
			{
				puts("неправильно проставленны скобки");
				key = false;
			}
			if ((primer[i + 1] == '(') && (strchr("QWERTYUIOPASDFGHJKLZXCVBNMqwertyuiopasdfghjklzxcvbnm1234567890", primer[i])))
			{
				puts("забыт знак перед скобками");
				key = false;
			}
		}
	} while ((n != 0) || (key == false));
	printf("Вы ввели: %s\n", primer);
	if (primer[0] == '-')
	{
		for (int i = strlen(primer) - 1; i >= 0; i--)
			primer[i + 1] = primer[i];
		primer[0] = '0';
	}
	if (primer[0] == '+')
		for (int i = 1; i < strlen(primer) + 1; i++)
			primer[i - 1] = primer[i];
	for (int i = 1; i < strlen(primer); i++)
	{
		if ((primer[i] == '-') && (primer[i - 1] == '('))
		{
			for (int j = strlen(primer); j >= i; j--)
				primer[j + 1] = primer[j];
			primer[i] = '0';
		}
		if ((primer[i] == '+') && (primer[i - 1] == '('))

			for (int j = i + 1; j < strlen(primer) + 1; j++)
				primer[j - 1] = primer[j];
	}

	return primer;
}
char *inttostr(int a)
{
	char s[10];
	int i = 1000, j = 0;
	while (a < i)
		i = i / 10;
	while (a > 0)
	{
		switch (a / i)
		{
		case 0:
			s[j] = '0';
			break;
		case 1:
			s[j] = '1';
			break;
		case 2:
			s[j] = '2';
			break;
		case 3:
			s[j] = '3';
			break;
		case 4:
			s[j] = '4';
			break;
		case 5:
			s[j] = '5';
			break;
		case 6:
			s[j] = '6';
			break;
		case 7:
			s[j] = '7';
			break;
		case 8:
			s[j] = '8';
			break;
		case 9:
			s[j] = '9';
		}
		while (a >= i)
			a -= i;
		i = i / 10;
		j++;
		s[j] = '\0';
	}
	return s;
}
int strtoint(char *a)
{
	int i = 0, j = 0;
	while (a[j] != '\0')
	{
		i *= 10;
		switch (a[j])
		{
		case '0':
			break;
		case '1':
			i += 1;
			break;
		case '2':
			i += 2;
			break;
		case '3':
			i += 3;
			break;
		case '4':
			i += 4;
			break;
		case '5':
			i += 5;
			break;
		case '6':
			i += 6;
			break;
		case '7':
			i += 7;
			break;
		case '8':
			i += 8;
			break;
		case '9':
			i += 9;
		}
		j++;
	}
	return i;
}
float calc(Tree *a)
{
	float l, r;
	if (((a->Left)->sym[0] == '+') || ((a->Left)->sym[0] == '-') || ((a->Left)->sym[0] == '*') || ((a->Left)->sym[0] == '/'))
		l = calc(a->Left);
	else
		l = strtoint((a->Left)->sym);
	if (((a->Right)->sym[0] == '+') || ((a->Right)->sym[0] == '-') || ((a->Right)->sym[0] == '*') || ((a->Right)->sym[0] == '/'))
		r = calc(a->Right);
	else
		r = strtoint((a->Right)->sym);
	switch (a->sym[0])
	{
	case '+':
		return l + r;
	case '-':
		return l - r;
	case '*':
		return l * r;
	case '/':
		return l * 1.0 / r;
	}
}
int main()
{
	srand(time(NULL));
	setlocale(0, "russian");
	char *primer, **str;
	int n;
	bool key;
	puts("введите 1 для ввода примера или 2 для использования готового:(3/f-7)*(4-2*(8*g+5))");
	scanf("%d",&n);
	getch();
	if (n==1)
	{
	primer = new char[100];
	strcpy(primer, vvod());
	}
	else
	primer="(3/f-7)*(4-2*(8*g+5))";
	n = 0;
	for (int j = 0; j < strlen(primer); j++)
	{
		n++;
		if (strchr("1234567890qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM", primer[j]) != NULL)
			while (strchr("1234567890qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM", primer[j + 1]) != NULL)
				j++;
	}

	str = new char *[n];
	for (int i = 0; i < n; i++)
		str[i] = new char[10];
	char *sim;
	int j = 0;
	int l;
	for (int i = 0; i < n; i++)
	{
		if ((primer[j] == '+') || (primer[j] == '-') || (primer[j] == '*') || (primer[j] == '/') || (primer[j] == '(') || (primer[j] == ')'))
		{
			str[i][0] = primer[j];
			j++;
		}
		else
		{
			sim = new char[10];

			l = 0;
			while ((primer[j] != '+') && (primer[j] != '-') && (primer[j] != '*') && (primer[j] != '/') && (primer[j] != '(') && (primer[j] != ')') && (primer[j] != '\0'))
			{
				sim[l] = primer[j];
				l++;
				j++;
			}
			sim[l] = '\0';
			strcpy(str[i], sim);
		}
	}
	int s;
	for (int i = 0; i < n; i++)
	{
		key = true;
		for (j = 0; j < strlen(str[i]); j++)
			if (strchr("QWERTYUIOPASDFGHJKLZXCVBNMqwertyuiopasdfghjklzxcvbnm", str[i][j]) != NULL)
				key = false;
		if (key == false)
		{
			sim = new char[10];
			printf("Введите значение переменной %s(любой другой символ - для задания случайно)", str[i]);
			gets(sim);
			key = true;
			for (j = 0; j < strlen(sim); j++)
				if (strchr("QWERTYUIOPASDFGHJKLZXCVBNMqwertyuiopasdfghjklzxcvbnm", sim[j]) != NULL)
					key = false;
			if (key == false)
				sim = inttostr(rand() % 1000);
			for (j = i + 1; j < n; j++)
			{
				if (strcmp(str[i], str[j]) == 0)
					strcpy(str[j], sim);
			}
			strcpy(str[i], sim);
		}
	}
	printf("Вы ввели(с учетом обработки):");
	for (int i = 0; i < n; i++)
		printf("%s", str[i]);
	puts("");
	Tree *head = CreateTree(str, 0, n - 1);
	puts("Бинарное дерево:");
	viv(head, 0);
	printf("Ответ: %f", calc(head));
	getch();
	return 0;
}