#include <iostream>
#include <conio.h>
#include <string>
using namespace std;
#define COUNT 15

struct TNode
{
	char data;
	TNode* left;
	TNode* right;
};

typedef TNode* PNode;

PNode root = NULL;

string erase(string msg)
{
	int n = msg.length();
	for (int i = 0; i < n; i++)
	{
		if (msg[i] == ' ')
		{
			msg.erase(i, 1);
			n--;
		}
	}
	return msg;
}

// correct_paranthesis - проверка на баланс строка в левой и правой частях
bool correct_paranthesis(string s)
{
	int am = 0;
	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] == '(')
			am++;
		if (s[i] == '(')
			am--;
		if (am < 0)
			return false;
	}
	return (am == 0);
}


// parse - сама реализация парсинга, посредством рекурсии
PNode parse(string str)
{
	// Наши операторы
	char operators[4] = { '+' , '-' , '*' , '/' };

	// Длина строки
	size_t strLenght = str.length();

	// Уровень
	int* symbolDepth = new int[strLenght];


	// До следующего For'a просто подсчитываем уровень всей строки
	if (str[0] == '(')
		symbolDepth[0] = 1;
	else
		symbolDepth[0] = 0;
	for (size_t i = 1; i < strLenght; i++)
	{
		symbolDepth[i] = symbolDepth[i - 1];
		if (str[i] == '(')
		{
			symbolDepth[i]++;
		}
 		else if (str[i] == ')')
		{
			symbolDepth[i]--;
		}
	}

	// Взяв j знак(умнож/дел и т.п.) ищем позицию этого знака в строке, если он конечно есть
	for (int j = 0; j < 4; j++)
	{
		int position = -1;
		for (int i = 0; i < strLenght; i++)
		{
			if (str[i] == operators[j] && symbolDepth[i] == 0 && position == -1)
			{
				position = i;
				break;
			}
		}

		// Если нашёлся знак, то
		if (position != -1)
		{
			string left = str.substr(0, position);	// Делим на левую часть
			string right = str.substr(position + 1, strLenght - position - 1); // И правую ( от знака ) 2+3 = 2 и 3

			if (correct_paranthesis(left) && correct_paranthesis(right)) // Если все скобки в правой и левой частях закрыты, то продолжаем
			{
				PNode result = new TNode;	// Выделяем память под результат

				result->data = operators[j];	// Запоминаем знак
				result->left = parse(left);		// И говорим, что то, что отправится в парсинг будет нашей левой
				result->right = parse(right);	// и правой частями соответственно
				return result;	// После выполнения рекурсий для left и right просто возвращаем наш созданный узел со знаком и левой и правыми частями, которые мы уже пропарсили
			}
		}
	}

	// Если знака не нашлось, то проверяем, закрыта ли у нас целиком строчка с двух сторон скобками, если да, то очищаем и отправляем в парс её
	if (str[0] == '(' && str[strLenght - 1] == ')')
	{
		string clean = str.substr(1, strLenght - 2);
		return parse(clean);
	}

	// Если нет (Не нашлось ни знаков, ни скообок, то это число)

	PNode result = new TNode;
	result->data = str[0];	// Поскольку числа <10 , то лишь один символ останется
	result->left = NULL;	// Это край, поэтому зануляем концы
	result->right = NULL;
	return result;
}

// print - вывод дерева
void print(PNode root, int space)
{
	if (root == NULL)
		return;

	space += COUNT;

	print(root->right, space);

	cout << endl;
	for (int i = COUNT; i < space; i++)
		cout << " ";
	cout << root->data << "\n";

	print(root->left, space);
}

int main()
{
	setlocale(LC_CTYPE, "Russian");

	string s;
	cout << "Введите выражение: ";

	getline(cin, s);

	string p = erase(s);

	root = parse(p);

	print(root, 0);

	system("pause");
	return 0;
}