From c399b0875b94c8f9439e317fbcdb6fce5b8f0bcb Mon Sep 17 00:00:00 2001 From: HombreLaser Date: Sun, 24 Apr 2022 11:19:49 -0500 Subject: Añadido simplificador terminado MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- expression_base.cpp | 6 -- expressions.cpp | 41 +++++++++- include/expressions.hpp | 12 ++- include/simplifier.hpp | 36 ++++----- main.cpp | 8 +- makefile | 4 +- simplifier.cpp | 210 +++++++++++++++++++++++++++++++++++++++++++++--- 7 files changed, 273 insertions(+), 44 deletions(-) diff --git a/expression_base.cpp b/expression_base.cpp index 2aff278..3829715 100644 --- a/expression_base.cpp +++ b/expression_base.cpp @@ -4,7 +4,6 @@ #include #include "include/expressions.hpp" -#include "include/simplifier.hpp" #include "include/lexer.hpp" using std::string; @@ -16,11 +15,6 @@ Expression *Expression::getLeft() { return left; } -template -Expression *Expression::simplify(E *expr ,const Simplifier *s) { - return s->visit(expr); -} - Expression *Expression::getRight() { return right; } diff --git a/expressions.cpp b/expressions.cpp index 72e1e04..6046a9c 100644 --- a/expressions.cpp +++ b/expressions.cpp @@ -4,6 +4,7 @@ #include "include/lexer.hpp" #include "include/expressions.hpp" #include "include/differentiator.hpp" +#include "include/simplifier.hpp" using std::string, std::to_string; @@ -30,6 +31,10 @@ Expression *Literal::diff(const Differentiator *d) { return d->visit(this); } +Expression *Literal::simplify(const Simplifier *s) { + return s->visit(this); +} + Expression *Literal::copy() { return new Literal(value); } @@ -56,6 +61,10 @@ Expression *Function::diff(const Differentiator *d) { return d->visit(this); } +Expression *Function::simplify(const Simplifier *s) { + return s->visit(this); +} + void Function::delTree() { delete arg; } @@ -136,6 +145,10 @@ Expression *Variable::diff(const Differentiator *d) { return d->visit(this); } +Expression *Variable::simplify(const Simplifier *s) { + return s->visit(this); +} + Expression *Variable::copy() { return new Variable(name); } @@ -159,6 +172,10 @@ Expression *AddExpression::diff(const Differentiator *d) { return d->visit(this); } +Expression *AddExpression::simplify(const Simplifier *s) { + return s->visit(this); +} + Expression *AddExpression::copy() { return new AddExpression(left->copy(), right->copy()); } @@ -172,16 +189,20 @@ SubExpression::~SubExpression() { } float SubExpression::eval(int arg) { - float right_val = right->eval(arg); float left_val = left->eval(arg); + float right_val = right->eval(arg); - return right_val - left_val; + return left_val - right_val; } Expression *SubExpression::diff(const Differentiator *d) { return d->visit(this); } +Expression *SubExpression::simplify(const Simplifier *s) { + return s->visit(this); +} + Expression *SubExpression::copy() { return new SubExpression(left->copy(), right->copy()); } @@ -209,6 +230,10 @@ Expression *NegationExpression::diff(const Differentiator *d) { return d->visit(this); } +Expression *NegationExpression::simplify(const Simplifier *s) { + return s->visit(this); +} + Expression *NegationExpression::copy() { return new NegationExpression(right->copy()); } @@ -232,6 +257,10 @@ Expression *DivisionExpression::diff(const Differentiator *d) { return d->visit(this); } +Expression *DivisionExpression::simplify(const Simplifier *s) { + return s->visit(this); +} + Expression *DivisionExpression::copy() { return new DivisionExpression(left->copy(), right->copy()); } @@ -256,6 +285,10 @@ Expression *MultiplicationExpression::diff(const Differentiator *d) { return d->visit(this); } +Expression *MultiplicationExpression::simplify(const Simplifier *s) { + return s->visit(this); +} + Expression *MultiplicationExpression::copy() { return new MultiplicationExpression(left->copy(), right->copy()); } @@ -279,6 +312,10 @@ Expression *PowerExpression::diff(const Differentiator *d) { return d->visit(this); } +Expression *PowerExpression::simplify(const Simplifier *s) { + return s->visit(this); +} + Expression *PowerExpression::copy() { return new PowerExpression(left->copy(), right->copy()); } diff --git a/include/expressions.hpp b/include/expressions.hpp index 604801d..2dcf67c 100644 --- a/include/expressions.hpp +++ b/include/expressions.hpp @@ -32,8 +32,7 @@ public: virtual ~Expression() = default; std::string getRepr(); virtual Expression *diff(const Differentiator *d) = 0; - template - Expression *simplify(E *expr, const Simplifier *s); + virtual Expression *simplify(const Simplifier *s) = 0; Expression *getLeft(); Expression *getRight(); virtual float eval(int arg=0) = 0; @@ -55,6 +54,7 @@ public: ~Literal(); int getValue(); float eval(int arg=0) override; + Expression *simplify(const Simplifier *s) override; Expression *diff(const Differentiator *d) override; Expression *copy() override; protected: @@ -70,6 +70,7 @@ public: ~Function(); Expression *getArg(); float eval(int arg=0) override; + Expression *simplify(const Simplifier *s) override; Expression *diff(const Differentiator *d) override; trig_functions getFunctionName() const; Expression *copy() override; @@ -85,6 +86,7 @@ public: explicit Variable(char name); ~Variable(); float eval(int arg=0) override; + Expression *simplify(const Simplifier *s) override; Expression *diff(const Differentiator *d) override; Expression *copy() override; protected: @@ -97,6 +99,7 @@ public: ~AddExpression(); float eval(int arg=0) override; Expression *diff(const Differentiator *d) override; + Expression *simplify(const Simplifier *s) override; Expression *copy() override; }; @@ -107,6 +110,7 @@ public: float eval(int arg=0) override; Expression *copy() override; Expression *diff(const Differentiator *d) override; + Expression *simplify(const Simplifier *s) override; }; class NegationExpression : public Expression { @@ -116,6 +120,7 @@ public: float eval(int arg=0) override; Expression *copy() override; Expression *diff(const Differentiator *d) override; + Expression *simplify(const Simplifier *s) override; protected: void setRepr() override; }; @@ -127,6 +132,7 @@ public: float eval(int arg=0) override; Expression *copy() override; Expression *diff(const Differentiator *d) override; + Expression *simplify(const Simplifier *s) override; }; class MultiplicationExpression : public Expression { @@ -136,6 +142,7 @@ public: float eval(int arg=0) override; Expression *copy() override; Expression *diff(const Differentiator *d) override; + Expression *simplify(const Simplifier *s) override; }; class PowerExpression : public Expression { @@ -145,6 +152,7 @@ public: float eval(int arg=0) override; Expression *copy() override; Expression *diff(const Differentiator *d) override; + Expression *simplify(const Simplifier *s) override; }; #endif /* EXPRESSIONS_H */ diff --git a/include/simplifier.hpp b/include/simplifier.hpp index dcc3225..e08f951 100644 --- a/include/simplifier.hpp +++ b/include/simplifier.hpp @@ -8,25 +8,25 @@ class Simplifier { private: - void simplifyChildren(Expression *root, Expression *left, Expression *right); - Expression *ruleEval(Expression *expr); - Expression *ruleMultiplyByOne(MultiplicationExpression *expr); - Expression *ruleDivideByOne(DivisionExpression *expr); - Expression *ruleMultiplyByZero(MultiplicationExpression *expr); - Expression *ruleZeroDivision(DivisionExpression *expr); - Expression *ruleOnePower(PowerExpression *expr); - Expression *ruleZeroPower(PowerExpression *expr); - Expression *addZero(AddExpression *expr); + void simplifyChildren(Expression *root, Expression **left, Expression **right) const; + Expression *ruleEval(Expression *expr) const; + Expression *ruleMultiplyByOne(MultiplicationExpression *expr) const; + Expression *ruleDivideByOne(DivisionExpression *expr) const; + Expression *ruleMultiplyByZero(MultiplicationExpression *expr) const; + Expression *ruleZeroDivision(DivisionExpression *expr) const; + Expression *ruleOnePower(PowerExpression *expr) const; + Expression *ruleZeroPower(PowerExpression *expr) const; + Expression *addSubstractZero(Expression *expr) const; public: - Expression *visit(Variable *expr); - Expression *visit(Literal *expr); - Expression *visit(Function *expr); - Expression *visit(NegationExpression *expr); - Expression *visit(AddExpression *expr); - Expression *visit(SubExpression *expr); - Expression *visit(MultiplicationExpression *expr); - Expression *visit(DivisionExpression *expr); - Expression *visit(PowerExpression *expr); + Expression *visit(Variable *expr) const; + Expression *visit(Literal *expr) const; + Expression *visit(Function *expr) const; + Expression *visit(NegationExpression *expr) const; + Expression *visit(AddExpression *expr) const; + Expression *visit(SubExpression *expr) const; + Expression *visit(MultiplicationExpression *expr) const; + Expression *visit(DivisionExpression *expr) const; + Expression *visit(PowerExpression *expr) const; }; Expression *simplify(Expression *to_simplify); diff --git a/main.cpp b/main.cpp index fb8b8df..c1ecd22 100644 --- a/main.cpp +++ b/main.cpp @@ -7,6 +7,7 @@ #include "include/expressions.hpp" #include "include/exceptions.hpp" #include "include/differentiator.hpp" +#include "include/simplifier.hpp" using std::string, std::cin, std::cout, std::getline, std::vector, std::begin, std::end, std::endl; @@ -15,7 +16,7 @@ int main(){ string input; Parser parser; Expression *tree; - Expression *differential = NULL; + Expression *simplified = NULL; getline(cin, input); try { @@ -27,9 +28,10 @@ int main(){ } if(tree != NULL) { - differential = deriv(tree); + simplified = simplify(tree); + cout << simplified->getRepr() << endl; delete tree; - delete differential; + delete simplified; } return 0; diff --git a/makefile b/makefile index 8ec96d2..8296ff1 100644 --- a/makefile +++ b/makefile @@ -1,7 +1,7 @@ CC=g++ CFLAGS= -std=gnu++17 -g -DEPS = include/lexer.hpp include/exceptions.hpp include/parser.hpp include/expressions.hpp include/differentiator.hpp -OBJ = expressions.o differentiator.o expression_base.o lexer.o exceptions.o parser.o main.o +DEPS = include/lexer.hpp include/exceptions.hpp include/parser.hpp include/expressions.hpp include/differentiator.hpp include/simplifier.hpp +OBJ = expressions.o differentiator.o simplifier.o expression_base.o lexer.o exceptions.o parser.o main.o %.o : %.cpp $(DEPS) $(CC) -c -o $@ $< $(CFLAGS) diff --git a/simplifier.cpp b/simplifier.cpp index 8fb926c..d258515 100644 --- a/simplifier.cpp +++ b/simplifier.cpp @@ -6,13 +6,13 @@ #include "include/expressions.hpp" #include -void Simplifier::simplifyChildren(Expression *root, Expression *left, Expression *right) { - left = root->getLeft()->simplify(root->getLeft(), this); - right = root->getRight()->simplify(root->getRight(), this); +void Simplifier::simplifyChildren(Expression *root, Expression **left, Expression **right) const { + *left = root->getLeft()->simplify(this); + *right = root->getRight()->simplify(this); } // Reglas de simplificación. -Expression *Simplifier::ruleEval(Expression *expr) { +Expression *Simplifier::ruleEval(Expression *expr) const { Literal *left = dynamic_cast (expr->getLeft()); Literal *right = dynamic_cast (expr->getRight()); @@ -22,7 +22,7 @@ Expression *Simplifier::ruleEval(Expression *expr) { return NULL; } -Expression *Simplifier::ruleMultiplyByOne(MultiplicationExpression *expr) { +Expression *Simplifier::ruleMultiplyByOne(MultiplicationExpression *expr) const { Literal *left = dynamic_cast (expr->getLeft()); Literal *right = dynamic_cast (expr->getRight()); @@ -35,7 +35,7 @@ Expression *Simplifier::ruleMultiplyByOne(MultiplicationExpression *expr) { return NULL; } -Expression *Simplifier::ruleDivideByOne(DivisionExpression *expr) { +Expression *Simplifier::ruleDivideByOne(DivisionExpression *expr) const { Literal *right = dynamic_cast (expr->getRight()); if (right != NULL && right->getValue() == 1) @@ -44,7 +44,7 @@ Expression *Simplifier::ruleDivideByOne(DivisionExpression *expr) { return NULL; } -Expression *Simplifier::ruleMultiplyByZero(MultiplicationExpression *expr) { +Expression *Simplifier::ruleMultiplyByZero(MultiplicationExpression *expr) const { Literal *left = dynamic_cast (expr->getLeft()); Literal *right = dynamic_cast (expr->getRight()); @@ -54,7 +54,7 @@ Expression *Simplifier::ruleMultiplyByZero(MultiplicationExpression *expr) { return NULL; } -Expression *Simplifier::ruleZeroDivision(DivisionExpression *expr) { +Expression *Simplifier::ruleZeroDivision(DivisionExpression *expr) const { Literal *left = dynamic_cast (expr->getLeft()); if(left != NULL && left->getValue() == 0) @@ -63,7 +63,7 @@ Expression *Simplifier::ruleZeroDivision(DivisionExpression *expr) { return NULL; } -Expression *Simplifier::ruleOnePower(PowerExpression *expr) { +Expression *Simplifier::ruleOnePower(PowerExpression *expr) const { Literal *right = dynamic_cast (expr->getRight()); if(right != NULL && right->getValue() == 1) @@ -72,7 +72,7 @@ Expression *Simplifier::ruleOnePower(PowerExpression *expr) { return NULL; } -Expression *Simplifier::ruleZeroPower(PowerExpression *expr) { +Expression *Simplifier::ruleZeroPower(PowerExpression *expr) const { Literal *right = dynamic_cast (expr->getRight()); if(right != NULL && right->getValue() == 0) @@ -81,7 +81,7 @@ Expression *Simplifier::ruleZeroPower(PowerExpression *expr) { return NULL; } -Expression *Simplifier::addZero(AddExpression *expr) { +Expression *Simplifier::addSubstractZero(Expression *expr) const { Literal *left = dynamic_cast (expr->getLeft()); Literal *right = dynamic_cast (expr->getRight()); @@ -93,3 +93,191 @@ Expression *Simplifier::addZero(AddExpression *expr) { return NULL; } + +// Para variables y constantes sólo devolveremos una copia. +Expression *Simplifier::visit(Variable *expr) const { + return expr->copy(); +} + +Expression *Simplifier::visit(Literal *expr) const { + return expr->copy(); +} + +// Para las funciones sólo simplificaremos su argumento. +Expression *Simplifier::visit(Function *expr) const { + Expression *simplified = expr->getArg()->simplify(this); + + return new Function(simplified, expr->getFunctionName()); +} + +// Igual en negaciones. +Expression *Simplifier::visit(NegationExpression *expr) const { + Expression *simplified = expr->getRight()->simplify(this); + + return new NegationExpression(simplified); +} + +Expression *Simplifier::visit(AddExpression *expr) const { + Expression *left = NULL, *right = NULL, *simplified; + AddExpression *root; + + simplifyChildren(expr, &left, &right); + root = new AddExpression(left, right); + /* Primera regla: vemos si se puede evaluar. + (Los dos nodos hijos son números). */ + simplified = ruleEval(root); + + if(simplified != NULL) { + delete root; + + return simplified; + } + + /* Segunda regla: vemos si uno de los nodos + hijo es 0.*/ + simplified = addSubstractZero(root); + + if(simplified != NULL) { + delete root; + + return simplified; + } + + /* No se pudo simplificar más: regresamos un nodo suma + con los nodos hijo simplificados.*/ + return root; +} + +Expression *Simplifier::visit(SubExpression *expr) const { + Expression *left = NULL, *right = NULL, *simplified; + SubExpression *root; + + simplifyChildren(expr, &left, &right); + root = new SubExpression(left, right); + + simplified = ruleEval(root); + + if(simplified != NULL) { + delete root; + + return simplified; + } + + simplified = addSubstractZero(root); + + if(simplified != NULL) { + delete root; + + return simplified; + } + + return root; +} + +Expression *Simplifier::visit(MultiplicationExpression *expr) const { + Expression *left = NULL, *right = NULL, *simplified; + MultiplicationExpression *root; + + simplifyChildren(expr, &left, &right); + root = new MultiplicationExpression(left, right); + + simplified = ruleEval(root); + + if(simplified != NULL) { + delete root; + + return simplified; + } + + simplified = ruleMultiplyByOne(root); + + if(simplified != NULL) { + delete root; + + return simplified; + } + + simplified = ruleMultiplyByZero(root); + + if(simplified != NULL) { + delete root; + + return simplified; + } + + return root; +} + +Expression *Simplifier::visit(DivisionExpression *expr) const { + Expression *left = NULL, *right = NULL, *simplified; + DivisionExpression *root; + + simplifyChildren(expr, &left, &right); + root = new DivisionExpression(left, right); + + simplified = ruleEval(root); + + if(simplified != NULL) { + delete root; + + return simplified; + } + + simplified = ruleDivideByOne(root); + + if(simplified != NULL) { + delete root; + + return simplified; + } + + simplified = ruleZeroDivision(root); + + if(simplified != NULL) { + delete root; + + return simplified; + } + + return root; +} + +Expression *Simplifier::visit(PowerExpression *expr) const { + Expression *left = NULL, *right = NULL, *simplified; + PowerExpression *root; + + simplifyChildren(expr, &left, &right); + root = new PowerExpression(left, right); + + simplified = ruleEval(root); + + if(simplified != NULL) { + delete root; + + return simplified; + } + + simplified = ruleOnePower(expr); + + if(simplified != NULL) { + delete root; + + return simplified; + } + + simplified = ruleZeroPower(root); + + if(simplified != NULL) { + delete root; + + return simplified; + } + + return root; +} + +Expression *simplify(Expression *to_simplify) { + Simplifier s; + + return to_simplify->simplify(&s); +} -- cgit v1.2.3