//lab24.cpp//////////////////////////////////////////////////////////////////// /* Author: Denis Oleshkevich * Mail: qravf@byrfuxrivpu.eh (use rot13) * ICQ: 240077001 */ #include #include #include #include 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()); } };