//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());
}
};