#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* Структура для хранения элемента бинарного дерева */
struct element
{
	int number;             /* Хранимое число */
	char operation;         /* Код операции, которую необходимо выполнить что бы получить
                                   из дочерних элементов число */
	struct element *left;   /* Указатель на левое поддерево */
	struct element *right;  /* Указатель на правое поддерево */
};

/* Функция для определения в строке позиции операции с наименьшим приоритетом (с учетом скобок) */
/* На входе - массив символов в котором хранится строка, количество символов в строке */
/* Примечание - при обработке строки не учитывается концевой 0-маркер, поэтому функция может обрабатывать
   отдельные части строки */
int findLastOperation(char str[], int count)
{
int current = 0, pri, i, number, minimal = -1;

	for(i = 0; i < count; i++) /* Обработка всех символов строки */
	{
		switch(str[i]) /* Действия в зависимости от кода текущего символа */
		{
			case '(':
				current += 2; /* Скобка открывается. Увеличиваем базовый приоритет. */
				break;
			case ')':
				current -= 2; /* Скобка закрывается. Уменьшаем базовый приоритет. */
				break;
			case '*':
			case '/': /* Умножение и деление - приоритетные операции,
                                     к базовому приоритету прибавляем 1 и проверяем, не является
                                     ли приоритет текущей операции минимальным из уже просмотренных,
                                     если да - обновляем указатель на минимальный и значение приоритет */
				pri = current + 1;
				if(((minimal >= 0) && (pri < minimal)) || (minimal < 0))
				{
					number = i;
					minimal = pri;
				}
				break;
			case '+':
			case '-':
                                /* Действия аналогичны умножению и делению, но приоритет не увеличивается на 1 */
				pri = current;
				if(pri == 0) /* Если приоритет текущей операции 0 - то он заранее минимален, */
					return i; /* поэтому можно не продолжать дальнейший поиск */
				if(((minimal >= 0) && (pri < minimal)) || (minimal < 0))
				{
					number = i;
					minimal = pri;
				}
				break;
			default: /* Если символ - не операция */
				break;
		}
	}
	if(minimal >= 0) 
		return number; /* Возвращаем номер позиции */
	else
		return -1; /* Если minimal=-1 - то не было найдено ни одно операции */
}

/* Функция преобразования строки в целое число */
/* Учитывает возможность наличия открывающейся в начале или закрывающейся в конце скобки */
int stringtoi(char str[], int count)
{
char tmp[count + 1]; /* Временный буфер для строки */
	while(str[0] == '(') /* Убираем все скобки в начале */
		str++, count--;
	while(str[count - 1] == ')')  /* Убираем все скобки в конце */
		count--;

	strncpy(tmp, str, count); /* Копируем получившуюся после обрезки строку во временный буфер tmp */
	tmp[count] = '\0'; /* Ставим концевой 0-маркер после строки в буфере, что бы получить стандартную C-строку */

	return atoi(tmp); /* Возвращаем результат преобразования стандартной C-строки в целое число */
}

/* Рекурсивная функция построяния дерева */
/* На входе - обрабатываемая строка (возможно без 0-маркера), количество символов в строке */
struct element *build(char str[], int count)
{
struct element *el = (struct element *)malloc(sizeof(struct element)); /* Создаем новый элемент и выделяем под него память */
int n = findLastOperation(str, count); /* Ищем операцию с минимальным приоритетом - по ней будем производить разбивку */

	if(n == -1) /* Если операция не найдена - значит переданная строка это просто число */
	{
		el->operation = 0; /* Операции нет - следовательно записываем в код операции 0 */
		el->number = stringtoi(str, count); /* Записываем число */
	} else /* Если операция найдена - нужно производить дальнейшую разбивку */
	{
		el->operation = str[n]; /* Записываем в код операции код найденного символа операции */
		el->left = build(str, n); /* Вызываем функцию построения левого поддерева из левой части строки */
		el->right = build(str + n + 1, count - n - 1); /* Вызываем функцию построения правого поддерева из правой части строки */
	}
	return el; /* Возвращаем получившийся результат */
}

/* Рекурсивная функция для вывода бинарного дерева на экран */
/* На входе - указатель на начало поддерева, смещение при печати */
void printTree(struct element *el, int n)
{
int i;
	for(i = 0; i < n; i++) /* Печатаем пробелы для смещения*/
		putchar(' ');
	putchar('|');
		
	if(el->operation == 0) /* Если код операции не записан - значит это просто число, выводим его */
	{
		
		printf("%d\n", el->number);
	} else /* Если код операции записан - значит, выводим этот код на экран и запускаем обработку левого
                 и правого поддеревьев с большим смещением чем текущее */
	{
		
		printf("%c\n", el->operation);
		printTree(el->left, n + 1);
		printTree(el->right, n + 1);
	}
}

int main()
{
char str[] = "(2+3)*4"; /* Задаем обрабатываемую строку, обязательно без пробелов*/
struct element *tree = build(str, strlen(str)); /* Строим дерево по заданной строке */

	printTree(tree, 0); /* Выводим дерево на экран */

	return 0;
}