//lab24.cpp////////////////////////////////////////////////////////////////////
/* Author: Denis Oleshkevich
 *   Mail: qravf@byrfuxrivpu.eh (use rot13)
 *    ICQ: 240077001
 */
#include <list>
#include <stack>
#include <fstream>
#include <iostream>

using namespace std;

#include "tree.cpp"

#define EVER ;;


int main()
{
    char str[100];
    for (EVER) {
	cout << "Enter valid arithmetic expression: ";
	cin >> str;
	ExprBinTree tree(str);
	if (tree.valid) {
	    cout << "\nInitial Expression:" << endl;
            tree.print();
	    if (tree.is_only_numbers()) {
		cout << "\nSimplistic Expression:" << endl;
		tree.simplify();
		tree.print();
	    } else {
		cout << "\nExpression after multiplication:" << endl;
		tree.task();
		tree.print();
	    }
	    cout << "\n\n";
	} else {
	    cout << "Bad expression, try more=))\n";
	}
    }
}


  

  
//tree.cpp///////////////////////////////////////////////////////////////////////////
/* Author: Denis Oleshkevich
 *   Mail: denis@oleshkevich.ru
 *    ICQ: 240077001
 */
#define PLUS '+'
#define MINUS '-'
#define MULTI '*'
#define DIV '/'

#define OPEN_BRACKET '('
#define CLOSE_BRACKET ')'


//если символ оператор то возвращаем тру
bool is_operator(char symbol)
{
    return (symbol == PLUS)
	|| (symbol == MINUS)
	|| (symbol == MULTI)
	|| (symbol == DIV);
}


bool is_digit(char symbol)
{
    return (symbol >= '0')
	&& (symbol <= '9');

}

//если символ скобка то возвращаем тру
bool is_bracket(char symbol)
{
    return (symbol == OPEN_BRACKET)
	|| (symbol == CLOSE_BRACKET);
}


//если символ буква или цифра то возвращаем тру
bool is_symbol(char symbol)
{
    return ((symbol >= 'a') && (symbol <= 'z'));


}


int get_priority(char var)
{
    if (var == PLUS || var == MINUS)
	return 1;
    if (var == MULTI || var == DIV)
	return 2;
    if (var == OPEN_BRACKET)
	return 3;
    if (var == CLOSE_BRACKET)
	return -1;
    return 0;
}







enum { VARIABLE, NUMBER, OPERATOR, BRACKET };


class ExprData {
    char var;
    double value;
    int what;

  public:

     ExprData(char a_var) {
	Set(a_var);
    } ExprData(double a_value) {
	Set(a_value);
    }

    ExprData(ExprData * data) {
	if (data->is_oper())
	    Set(data->getVar());
	else
	    Set(data->getValue());
    }

    void Set(char a_var) {
	var = a_var;
	value = 0;
	what = (is_operator(a_var) ? OPERATOR : is_bracket(a_var) ? BRACKET : VARIABLE);
    }

    void Set(double a_value) {
	var = 0;
	value = a_value;
	what = NUMBER;
    }

    char getVar() {
	return var;
    }

    double getValue() {
	return value;
    }

    bool is_brack() {
	return (what == BRACKET);
    }


    bool is_oper() {
	return (what == OPERATOR);
    }

    bool is_num() {
	return (what == NUMBER);
    }

    bool is_var() {
	return (what == VARIABLE);
    }

    int get_priority() {
	if (var == PLUS || var == MINUS)
	    return 1;
	if (var == MULTI || var == DIV)
	    return 2;
	if (var == OPEN_BRACKET)
	    return 3;
	if (var == CLOSE_BRACKET)
	    return -1;
	return 0;
    }

//если символ плюс или минус то возвращаем тру
    bool is_plus() {
	return (var == PLUS);
    }

    bool is_minus() {
	return (var == MINUS);
    }


//если символ умножить или разделить то возвращаем тру
    bool is_multi() {
	return (var == MULTI);
    }


    bool is_div() {
	return (var == DIV);
    }

    bool is_summ() {
	return is_plus() || is_minus();
    }

    bool is_produce() {
	return is_multi() || is_div();
    }

    friend ostream & operator<<(ostream & stream, ExprData data);

};

ostream & operator<<(ostream & stream, ExprData data)
{
    switch (data.what) {
    case NUMBER:
	stream << data.value;
	break;
    default:
	stream << data.var;
    }
}


struct ExprBinNode {
    ExprData *value;

    ExprBinNode *left;
    ExprBinNode *right;

     ExprBinNode(ExprData * a_value, ExprBinNode * a_right, ExprBinNode * a_left) {
	value = a_value;
	left = a_left;
	right = a_right;
    } ExprBinNode(ExprData * a_value, ExprBinNode * a_left) {
	value = a_value;
	left = a_left;
	right = NULL;
    }

    ExprBinNode(ExprData * a_value) {
	value = a_value;
	left = NULL;
	right = NULL;
    }
};


//функция для печати стека на символе
void printStack(stack < ExprData * >s)
{
    stack < ExprData * >s1 = s;

    while (s1.size()) {
	cout << *(s1.top());
	s1.pop();
    }


}



class ExprBinTree {
    ExprBinNode *root;		//указатель на корневую вершину дерева
     stack < ExprData * >expression;	//стек с выражением
    bool only_numbers;
  public:
     bool valid;		//указывает верное ли выражение ввел пользователь

  private:

    //проверка на верность выражений
     bool isValidExpression(char *expression) {
	int len = strlen(expression);
	int b = 0;
	if (is_operator(expression[0]))
	     return false;

	if (is_operator(expression[len - 1]))
	     return false;

	for (int i = 0; i < len; i++) {
	    //рядом нет двух операторов
	    if (is_operator(expression[i]) && is_operator(expression[i + 1]))
		return false;

	    //в начале строки или после открывающейся скобки не стоит оператор (ВНИМАНИЕ!!! тут неправильно обрабываются унарные минусы)
	    if (is_operator(expression[i]) && (i == 0 || expression[i - 1] == OPEN_BRACKET))
		return false;

	    //рядом нет двух символов
	    if (is_symbol(expression[i]) && is_symbol(expression[i + 1]))
		return false;

	    if (i && i < len - 1 && expression[i] == '.') {
		if (!is_digit(expression[i - 1]) || !is_digit(expression[i + 1]))
		    return false;
	    }




	    if (expression[i] == OPEN_BRACKET) {
		//после открывающейся скобки не следует закрывающаяся
		if (expression[i + 1] == CLOSE_BRACKET)
		    return false;

		//перед открывающейся скобкой не стоит символ
		if (i > 0 && is_symbol(expression[i - 1])) {
		    return false;
		}
		b++;		//увеличиваем счетчик открытых скобок
	    }

	    if (expression[i] == CLOSE_BRACKET) {
		//закрывающаяся скобка не должна быть в начале строки
		if (i == 0)
		    return false;

		//после закрывающейся скобки не должна следовать открывающаяся
		if (expression[i + 1] == OPEN_BRACKET)
		    return false;

		//счетчик открытых скобок должен быть положительным
		if (b == 0)
		    return false;

		b--;		//уменьшаем счетчик открытых скобок
	    }

	}
	return !b;
    }



    stack < ExprData * >getPolskaStack(char *expression) {
	stack < ExprData * >temp;	//храним операторы и открывающиеся скобки
	stack < ExprData * >result;	//результирующий стек, в него сразу сбрасываем все переменные и числа

	double temp_value;
	char temp_str[100];
	bool is_num = false;
	int j = 0;
	int i = 0;
	int len = strlen(expression);

	while (i < len) {

	    j = i;
	    is_num = false;
	    while (is_digit(expression[i]) || expression[i] == '.') {
		is_num = true;
		temp_str[i - j] = expression[i];
		i++;

	    }

	    if (is_num) {
		temp_str[i - j] = 0;
		result.push(new ExprData(atof(temp_str)));
		continue;
	    }

	    ExprData *current = new ExprData(expression[i]);
	    ExprData *prev;


	    if (temp.size())
		prev = temp.top();
	    else
		prev = NULL;



	    if (current->is_brack() || current->is_oper()) {
		if (!prev || current->get_priority() > prev->get_priority()) {
		    //еcли приоритет вставляемой операции больше предыдущей
		    //во временном стеке, то вставляем ее во временный
		    temp.push(current);
		} else {
		    //если вставляемый элемент закр. скобка, то переносим часть стека до 
		    //открывающейся скобки в результирующий стек. переносим в обратном порядке
		    if (current->getVar() == CLOSE_BRACKET) {
			while (!temp.top()->is_brack()) {
			    result.push(temp.top());
			    temp.pop();
			}
			temp.pop();
		    } else {
			//если операция не скобка, то сразу предыдущую операцию помещаем
			//в результурующий стек, а текущую - во временный 
			if (!(prev->is_brack())) {
			    result.push(prev);
			    temp.pop();
			}
			temp.push(current);
		    }
		}
	    } else {
		result.push(current);
	    }

	    i++;
	}


	//в конце выражения переносим временный стек в результирующий 
	while (temp.size()) {
	    if (!(temp.top()->is_brack()))
		result.push(temp.top());
	    temp.pop();
	}


	return result;

    }

  public:



    //строим дерево по стеку
    ExprBinNode * buildTree() {
	ExprData *data = expression.top();
	expression.pop();

	if (data->is_var())
	    only_numbers = false;

	//если оператор
	if (data->is_oper()) {
	    //тут необходимо поменять порядок установки левого и правого поддерева,
	    //они устанавливаются в обратном порядке
	    return new ExprBinNode(data, buildTree(), buildTree());
	}
	return new ExprBinNode(data);

    }

    //конструктор, получает строку-выражение 
    ExprBinTree(char *a_expression) {

	if (isValidExpression(a_expression)) {
	    only_numbers = true;
	    valid = true;
	    expression = getPolskaStack(a_expression);
	    root = buildTree();
	} else {
	    valid = false;
	    only_numbers = false;
	}
    }

    bool is_only_numbers() {
	return only_numbers;
    }

    //возращает ссылку на корневой узел
    ExprBinNode *getRoot() {
	return root;
    }

    //печатает дерево
    void printTree(ExprBinNode * what, int level) {
	if (what == NULL)
	    return;

	for (int i = 0; i < level; i++)
	    cout << "  ";

	cout << what->value << "\n";

	if (what->left != NULL)
	    printTree(what->left, level + 1);

	if (what->right != NULL)
	    printTree(what->right, level + 1);


    }

    void printTree() {
	printTree(getRoot(), 0);
    }

    void printTree(ExprBinNode * what) {
	printTree(what, 0);
    }

    //вывод выражения
    void print(ExprBinNode * what) {
	if (what == NULL)
	    return;
	bool print_brackets = false;

	//в общем случае печатаем скобки, когда один из операндов-операция, 
	//с приоритетом меньше чем у текущей операции

	if (what->left != NULL) {
	    print_brackets = (print_brackets || what->left->value->is_oper() && what->left->value->get_priority() < what->value->get_priority());

	    if (print_brackets)
		cout << "(";
	    print(what->left);
	    if (print_brackets)
		cout << ")";
	}
	print_brackets = false;
	cout << *(what->value);

	if (what->right != NULL) {
	    //если текущий оператор минус или делить и справа стоит оператор - или +
	    if ((what->value->is_minus() || what->value->is_div()) && what->right->value->is_oper())
		print_brackets = true;


	    print_brackets = (print_brackets || what->right->value->is_oper() && what->right->value->get_priority() < what->value->get_priority());

	    if (print_brackets)
		cout << "(";
	    print(what->right);
	    if (print_brackets)
		cout << ")";
	}

    }

    void print() {
	print(getRoot());
	cout << endl;
    }



    ExprData *getCopy(ExprData * data) {
	return new ExprData(*data);
    }

    ExprBinNode *getCopy(ExprBinNode * node) {
	if (node->value->is_oper()) {
	    return new ExprBinNode(getCopy(node->value), getCopy(node->right), getCopy(node->left));
	}
	return new ExprBinNode(getCopy(node->value));
    }


    //умножаем поддерево на какое-то поддерево
    void multiplicationTree(ExprBinNode * node, ExprBinNode * mult) {
	bool dont_multi = false;	//указывает что мы если мы умножает произвдение,
	//то достаточно умножить только одну ветвь
	if (node == mult)
	    return;


	if (node->value->is_oper()) {
	    if (node->left != NULL) {
		multiplicationTree(node->left, mult);
		dont_multi = node->value->is_produce();
	    }

	    if (node->right != NULL) {
		if (!dont_multi)
		    multiplicationTree(node->right, mult);
	    }
	} else {
	    //если значение не оператор, устанавливаем новое значение, и ставим ветви
	    node->right = getCopy(mult);
	    node->left = new ExprBinNode(getCopy(node->value));
	    node->value->Set(MULTI);
	}

    }

    //передаем место где ищем и ссылку на предка
    void task(ExprBinNode * node, ExprBinNode * parent) {
	//флаги указывающие что левый/правый оператор это сложение/вычитание
	bool left_node = false;
	bool right_node = false;

	if (node->value->is_oper()) {
	    if (node->left != NULL && node->left->value->is_oper()) {
		task(node->left, node);
		if (node->left->value->is_summ())
		    left_node = true;
	    }

	    if (node->right != NULL && node->right->value->is_oper()) {
		task(node->right, node);
		if (node->right->value->is_summ())
		    right_node = true;
	    }

	    if (node->value->is_multi() && node->right != NULL && node->left != NULL && (left_node || right_node)) {

		//выбираем рабочее дерево
		ExprBinNode *workTree = (right_node ? node->right : node->left);
		//выбираем поддерево для умножения
		ExprBinNode *mult = (right_node ? node->left : node->right);

		//запускаем процедеру умножения поддерева

		multiplicationTree(workTree, mult);

		//      до              обработка            окончание
		//      *                  *                     +     
		//     / \                / \                  /   \   
		//    a   +    =>        a    +      =>       *     *  
		//       / \                /   \            / \   / \ 
		//      b   c              *     *          a   b a   c
		//                        / \   / \
		//                       a   b a   c


		//узел - корень, то заменяем корень на текущую вершину
		if (node == root) {
		    root = workTree;
		}
		//если умножение слева - то заменяем левого сына
		else if (parent->left->value->is_multi()) {
		    delete(parent->left);
		    parent->left = workTree;
		}
		//правого...
		else if (parent->right->value->is_multi()) {
		    delete(parent->right);
		    parent->right = workTree;

		}
		task(workTree, parent);
	    }
	}

    }


    void task() {
	task(getRoot(), getRoot());
    }

    void simplify(ExprBinNode * node) {
	if (!node)
	    return;


	if (node->value->is_oper()) {
	    if (node->left->value->is_oper())
		simplify(node->left);
	    if (node->right->value->is_oper())
		simplify(node->right);
	}

	if (node->value->is_oper()) {
	    if (node->left->value->is_num() && node->right->value->is_num()) {
		double a = node->left->value->getValue();
		double b = node->right->value->getValue();
		double result = 0;

		switch (node->value->getVar()) {
		case MULTI:
		    result = a * b;
		    break;
		case PLUS:
		    result = a + b;
		    break;
		case MINUS:
		    result = a - b;
		    break;
		case DIV:
		    result = a / b;
		    break;

		}


		node->value->Set(result);
		delete(node->left);
		delete(node->right);

		node->left = NULL;
		node->right = NULL;

	    }


	}



    }


    void simplify() {
	simplify(getRoot());


    }

};