KrivoeDerevo

//#include <conio.h>
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <ctime>
#include <stdlib.h>
#include <locale.h>

using namespace std;
struct B_tree {
    B_tree* left;
    B_tree* right;
    double value = 0;
    char per[100];
};
void print_menu() {
    puts("0-выход");
    puts("1-произвольное выражение");
    puts("2-выражение из варианта (7/(a+3))/(4-(1+3b))");
}
//приоритет операций : приоритет 1 для сложения и вычитания; 2 для умножения и деления
int priority(char c) {
    switch (c) {
        case '+':
        case '-':
            return 1;
        case '*':
        case '/':
            return 2;
    }
    return 100; // это не оперция, пропускаем ее
}
//bool is_space(char c) {
//return (c == ' ') || (c == '\t');
//}

//bool is_digit(char c) {
//    return  ((c >= '0') && (c <= '9') || (c == '.') || (c == ','));
//}

bool is_alpha(char c) {
    return (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
}

bool is_bracket(char c) {
    return (c == '(' || c == ')');
}

bool is_operation(char c) {
    return (c == '+' || c == '-' || c == '*' || c == '/');
}

//cоздание дерева
B_tree * AddTree(char term[][50], int left, int right)
{
    B_tree* MyTree = new B_tree;

    if (left == right) {
        strcpy(MyTree->per, term[left]);
        MyTree->left = NULL;
        MyTree->right = NULL;
        return MyTree;
    }
    int MinPtr = 100;
    int k = 0;
    int nest = 0;//счетчик вложенных скобок

    for (int i = left; i <= right; i++) {
        char c = term[i][0];
        if (c == '(') {
            nest++;
            continue;
        }
        if (c == ')') {
            nest--;
            continue;
        }
        if (nest > 0) {
            continue;
        }
        int ptr = priority(c);
        if (ptr <= MinPtr) {
            MinPtr = ptr;
            k = i;
        }

    }
    if (MinPtr == 100 && term[left][0] == '('&&term[right][0] == ')') {
        return AddTree(term, left + 1, right - 1);
    }

    strcpy(MyTree->per, term[k]);
    MyTree->left = AddTree(term, left, k - 1);
    MyTree->right = AddTree(term, k + 1, right);

    return MyTree;
}
//печать дерева
void Print_Tree(B_tree *MyTree, int lev) {
    if (MyTree) {
        Print_Tree(MyTree->left, lev + 1);
        for (int i = 0; i < lev; i++)
            cout << "";
        cout << MyTree->per << endl;
        Print_Tree(MyTree->right, lev + 1);
    }
}
//печать прямого обхода
void Print_Premoi_obhod(B_tree * MyTree) {
    if (MyTree != NULL) {
        cout << MyTree->per;
        Print_Premoi_obhod(MyTree->left);
        Print_Premoi_obhod(MyTree->right);
    }
}
//печать симметричного обхода
void Print_Simmetr_obhod(B_tree *MyTree) //рекурсивная функция печати бинарного дерева
{
    if (MyTree != NULL) //пока не встретится пустой узел
    {
        Print_Simmetr_obhod(MyTree->left); //рекурсивный вызов функции для левого поддерева
        cout << MyTree->per; //печать узла дерева
        Print_Simmetr_obhod(MyTree->right); // рекурсивный вызов функции для правого поддерева
    }
}
//печать обратного обхода
void Print_Obrat_obhod(B_tree *MyTree) {
    if (MyTree != NULL) {
        Print_Obrat_obhod(MyTree->left);
        Print_Obrat_obhod(MyTree->right);
        cout << MyTree->per;
    }
}
void Print(B_tree *MyTree) {
    cout << endl << "Prymoi obhod" << endl<<endl;
    Print_Premoi_obhod(MyTree);
    cout << endl << "Simmetrichnyi obhod" << endl<<endl;
    Print_Simmetr_obhod(MyTree);
    cout << endl << "Obratnyi obhod" << endl<<endl;
    Print_Obrat_obhod(MyTree);
    cout << endl;
}

//освобождение памяти выделенное под бинарное дерево
void del_tree(B_tree **MyTree){ // очистка памяти
    B_tree *current;
    current = *MyTree;
    if (*MyTree != NULL) {
        del_tree(&(*MyTree)->left);
        del_tree(&(*MyTree)->right);
        delete *MyTree;
    }
}
bool Proverka(char *str) {

    int left=0,right = 0;
    for (int i = 0; i < strlen(str); i++) {
        if (str[i] == '(') left++;
        if (str[i] == ')') right++;
        if (left < right) return false;
        if (!isdigit(str[i]) && !is_alpha(str[i]) && !is_operation(str[i]) && !is_bracket(str[i])) {
            return false;
        }
    }
    return right == left;

}
//унарные операции
void Un_operas (char *str){
    char un_plus[] = "0+";
    char un_minus[] = "0-";
    char simvol[] = "0123456789.";
    char *tmp = new char[150];
    int k_op = 0;
    if (*str == '+') {
        strcpy(tmp, str + 1);
        *str = '\0';
        strcat(str, un_plus);
        strcat(str, tmp);
    }
    if (*str == '-') {
        strcpy(tmp, str + 1);
        *str = '\0';
        strcat(str, un_minus);
        strcat(str, tmp);
    }
    for (int i = 0; i < strlen(str); i++) {
        if ((str[i - 1] == '(') ) {
            if (str[i] == '-') {
                strcpy(tmp, str + i + 1);
                *(str + i) = '\0';
                strcat(str, un_minus);
                strcat(str, tmp);
            }
            if (str[i] == '+') {
                strcpy(tmp, str + i + 1);
                *(str + i) = '\0';
                strcat(str, un_plus);
                strcat(str, tmp);
            }
        }
    }
}
int IsNumber(B_tree* MyTree) {
    int i = 0;
    if (!MyTree)
        return 0;
    while (MyTree->per[i])
        if (!strchr("0123456789", MyTree->per[i++]))
            return 0;
    return 1;
}
//вычисление
double Calculate(B_tree * MyTree) {
    double a, b, c=0;
    // можно ли вычислить
    if (!MyTree || !IsNumber(MyTree->left) || !IsNumber(MyTree->right))
        return 0;
    //получить данные от сыновей
    a = Calculate(MyTree->left);
    std::cout<<a<<endl;
    b = Calculate(MyTree->right);
    //выполнить операцию
    switch (MyTree->per[0])
    {
        case'+':
        {
            c = a + b;
            return c;
            break;
        }
        case'-':
        {
            c = a - b;
            return c;
            break;
        }
        case'*':
        {
            c = a * b;
            return c;
            break;
        }
        case'/':
            if (MyTree->right->per == "0")
                throw ("Деление на 0!");
            c = a / b;
            return c;
            break;
    }
    //удалить ненужные вершины
    delete MyTree->left;
    delete MyTree->right;
    //обновить вершину
    //MyTree = c;
    //itoa(c,MyTree->per,10);
    MyTree->left = nullptr;
    MyTree->right = nullptr;
}
//massivv
void tw_mas(char term[][50],char* str, int* p_long) {
    *p_long = 0;
    int k = 0;
    for (k = 0; k < strlen(str);) {
        int j = 0;
        if (isalpha(str[j + k])) {
            while (((j + k) < strlen(str)) && isalpha(str[j + k])) {
                term[*p_long][j] = str[j + k];
                j++;
            }
            term[*p_long][j] = '\0';
            (*p_long)++;
            k += j;
        }
        else
        if (str[k] == '(' || str[k] == ')' || str[k] == '+' || str[j + k] == '-' || str[j + k] == '*' || str[j + k] == '/') {
            term[*p_long][j] = str[k];
            term[*p_long][++j] = '\0';
            (*p_long)++;
            k++;
        }
        else
        if (isdigit(str[j + k])/*||str[k]=='.'||str[k]==','*/)
        {
            while (((j + k) < strlen(str)) && (isdigit(str[j + k])) /*|| str[k] == '.' || str[k] == ',')*/) {
                term[*p_long][j] = str[j + k];
                j++;
            }
            term[*p_long][j] = '\0';
            (*p_long)++;
            k += j;
        }
        else
            j = 0;
    }
}
//

bool findstr(char matr[][100], char* stroka, int p_longal) {
    int h = 0;
    int m_dlin = 0;
    for (int i = 0; i < p_longal; i++) {
        if (strcmp(matr[i], stroka) == 0) {
            return true;
        }
    }
    return false;
}

void mas_alpha(char str1[][100], char term[][50], int p_long, int *p_longal) {
    *p_longal = 0;

    for (int i = 0; i < p_long; i++)
        if (isalpha(term[i][0]) && findstr(str1, term[i], *p_longal)) {
            strcpy(str1[*p_longal], term[i]);//kuda ->
            (*p_longal)++;
        }
}

void finds(char* str1[][100], char num[][100], int p_longal) {

    for (int k = 0; k < p_longal; k++) {
        cout << "vvedite chislo " << str1[k] << endl;
        cin >> num[k];
    }
}
//
void swaps(B_tree *MyTree, char(&str1)[][100], char (&num)[][100], int p_longal) {
    if (MyTree != nullptr) {
        Print_Obrat_obhod(MyTree->left);
        Print_Obrat_obhod(MyTree->right);
        cout << MyTree->per;
        if (isalpha(MyTree->per[0])) {
            for (int i = 0; i < p_longal; i++) {
                strcpy(str1[i], MyTree->per);
                strcpy(MyTree->per, num[i]);
            }
        }
    }
}

int main() {
    setlocale(0, "russian");
    char str[100];
    int q=1;
    print_menu();
    while (q != 0) {
        cin >> q;
        switch (q)
        {
            case 0:
            {
                break;
            }
            case 1:
            {
                puts("введите выражения с числами, переменными и операциями *,/,+,-");
                cin>>str;
//                gets_s(str, 100);
                if (strlen(str) == 0) {
                    puts("пустая строка");
                    cout << endl << endl;
                    print_menu();
                    break;
                }
                puts("исходное выражение: ");
                puts(str);
                if (!Proverka(str)) {
                    puts("Неверный ввод");
                    puts("0-выход");
                    puts("1-рандомное выражение");
                    puts("2-исходное выражение (7/(a+3))/(4-(1+3*b))");
                    break;
                }
                //cout << str;
                Un_operas(str);
                char term[50][50];
                int p_long = 0; // длина масива term
                tw_mas(term, str, &p_long);
                //cout<<endl << "Terms : " << p_long << endl;//это все разбиение на термы
                //for (int i = 0; i < p_long; i++)
                //cout << term[i] << endl;
                //cout << str;
                B_tree* MyTree = AddTree(term, 0,p_long-1);
                cout << "Tree" << endl;
                int lev = 0;
                Print_Tree(MyTree, lev);
                Print(MyTree);
                //find_sim(str);
                char* str1[100][100];
                int p_longal = 0;
                char num[100][100];
                finds(str1, num, p_longal);
                cout << endl << "выражение с числами\n" << endl;
                cout << str;
                //swaps(MyTree, str1, num, p_longal);
                cout << "Res=" << endl;
                Calculate(MyTree);
                break;
            }
            case 2:
            {
                strcpy(str, "(7/(a+3))/(4-(1+3*b))");
                puts("\nIshodnoe viragenie:  ");
                puts(str);
                //find_sim(str);
                Un_operas(str);
                //cout << endl << "Выражение с числами" << endl;;
                cout << str;
                char term[50][50];
                int p_long = 0; // длина масива term
                tw_mas(term, str, &p_long);
                B_tree* MyTree = AddTree(term, 0, p_long - 1);
                Print(MyTree);
                break;
            }
            default:
            {
                cout << "Повторите выбор" << endl;
                print_menu();
                continue;
            }
        }
        //del_tree(MyTree);
        print_menu();
    }
    system("pause");
    return 0;
}
/*
// присваивает значение в строке
void swap(char* str, char* p_nam, int* p_value) {
	int k_bukv = strlen(p_nam);
	char* ishod_str;
	char* tmp = new char[100];
	char* num = new char[10];
	for (int i = 0; i < k_bukv; i++) {
		ishod_str = strchr(str, p_nam[i]);
		while (ishod_str)
		{
			strcpy(tmp, ishod_str + 1);
			for (int j = strlen(ishod_str); j >= 0; j--)
				ishod_str[j] = '\0';
				sprintf(num, "%d", p_value[i]);
				strcat(str, num);
				strcat(str, tmp);
				ishod_str = strchr(str, p_nam[i]);

		}
	}
	delete[] tmp;
	delete[] num;
}
//найти одинаковые буквы ил нет, и присвоить им значение
void find_sim(char *str) {
	int k_bukv = 0;
	for (int i = 0; i < strlen(str); i++) {
		if (isalpha(str[i])) {
			k_bukv++;
		}
	}
		if (k_bukv != 0) {
			int* p_value = new int[k_bukv];
			char* p_nam = new char[k_bukv];
			*p_nam = '\0';
			k_bukv = 0;
			for (int i = 0; i < strlen(str); i++)
				if (isalpha(str[i]) && !strchr(p_nam, str[i])) //если у нас буква и это  первое вхождение в строку
				{
					//присоединяет не более n символов s2 к s1, завершает строку символом '\0', возвращает s1
					strncat(p_nam, str+i, 1);//vse simvols
					p_nam[k_bukv + 1] = '\0';
					k_bukv++;
					i++;
					while (isalpha(str[i])) {
						strncat(p_nam, str + i, 1);//vse simvols
						p_nam[k_bukv + 1] = '\0';
						k_bukv++;
						i++;
					}
				}
				cout << endl;
				for (int i = 0; i < strlen(p_nam); i++) {

					cout << "введите число" << endl << p_nam[i] << " = ";
					cin >> p_value[i];
					cout << endl;
				}

			swap(str, p_nam, p_value);
		}

}
*/