summaryrefslogtreecommitdiff
path: root/fuzzylite/src/term/Function.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'fuzzylite/src/term/Function.cpp')
-rw-r--r--fuzzylite/src/term/Function.cpp600
1 files changed, 600 insertions, 0 deletions
diff --git a/fuzzylite/src/term/Function.cpp b/fuzzylite/src/term/Function.cpp
new file mode 100644
index 0000000..c0f54b8
--- /dev/null
+++ b/fuzzylite/src/term/Function.cpp
@@ -0,0 +1,600 @@
+/*
+ Author: Juan Rada-Vilela, Ph.D.
+ Copyright (C) 2010-2014 FuzzyLite Limited
+ All rights reserved
+
+ This file is part of fuzzylite.
+
+ fuzzylite is free software: you can redistribute it and/or modify it under
+ the terms of the GNU Lesser General Public License as published by the Free
+ Software Foundation, either version 3 of the License, or (at your option)
+ any later version.
+
+ fuzzylite is distributed in the hope that it will be useful, but WITHOUT
+ ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License
+ for more details.
+
+ You should have received a copy of the GNU Lesser General Public License
+ along with fuzzylite. If not, see <http://www.gnu.org/licenses/>.
+
+ fuzzyliteâ„¢ is a trademark of FuzzyLite Limited.
+
+ */
+
+#include "fl/term/Function.h"
+
+#include "fl/Engine.h"
+#include "fl/factory/FactoryManager.h"
+#include "fl/factory/FunctionFactory.h"
+#include "fl/rule/Rule.h"
+#include "fl/variable/InputVariable.h"
+#include "fl/variable/OutputVariable.h"
+
+#include <cctype>
+#include <functional>
+#include <queue>
+#include <signal.h>
+#include <stack>
+
+
+namespace fl {
+
+ /**
+ * Parsing elements
+ */
+
+
+ Function::Element::Element(const std::string& name, const std::string& description, Type type)
+ : name(name), description(description), type(type), unary(fl::null), binary(fl::null), arity(0),
+ precedence(0), associativity(-1) {
+
+ }
+
+ Function::Element::Element(const std::string& name, const std::string& description,
+ Type type, Unary unary, int precedence, int associativity)
+ : name(name), description(description), type(type), unary(unary), binary(fl::null), arity(1),
+ precedence(precedence), associativity(associativity) {
+ }
+
+ Function::Element::Element(const std::string& name, const std::string& description,
+ Type type, Binary binary, int precedence, int associativity)
+ : name(name), description(description), type(type), unary(fl::null), binary(binary), arity(2),
+ precedence(precedence), associativity(associativity) {
+ }
+
+ Function::Element::~Element() {
+
+ }
+
+ bool Function::Element::isOperator() const {
+ return type == OPERATOR;
+ }
+
+ bool Function::Element::isFunction() const {
+ return type == FUNCTION;
+ }
+
+ Function::Element* Function::Element::clone() const {
+ return new Element(*this);
+ }
+
+ std::string Function::Element::toString() const {
+ std::ostringstream ss;
+
+ if (type == OPERATOR) {
+ ss << "Operator (name=" << name << ", "
+ << "description=" << description << ", "
+ << "precedence=" << precedence << ", "
+ << "arity=" << arity << ", "
+ << "associativity=" << associativity << ", ";
+ if (arity == 1) ss << "pointer=" << unary;
+ else if (arity == 2) ss << "pointer=" << binary;
+ else ss << "pointer=error";
+ ss << ")";
+ } else if (type == FUNCTION) {
+ ss << "Function (name=" << name << ", "
+ << "description=" << description << ", "
+ << "arity=" << arity << ", "
+ << "associativity=" << associativity << ", ";
+ if (arity == 1) ss << "pointer=" << unary;
+ else if (arity == 2) ss << "pointer=" << binary;
+ else ss << "pointer=error";
+ ss << ")";
+ }
+ return ss.str();
+ }
+
+ /******************************
+ * Tree Node Elements
+ ******************************/
+
+ Function::Node::Node(Element* element, Node* left, Node* right)
+ : element(element), left(left), right(right), variable(""), value(fl::nan) {
+ }
+
+ Function::Node::Node(const std::string& variable)
+ : element(fl::null), left(fl::null), right(fl::null), variable(variable), value(fl::nan) {
+ }
+
+ Function::Node::Node(scalar value)
+ : element(fl::null), left(fl::null), right(fl::null), variable(""), value(value) {
+ }
+
+ Function::Node::Node(const Node& other)
+ : element(fl::null), left(fl::null), right(fl::null), variable(""), value(fl::nan) {
+ copyFrom(other);
+ }
+
+ Function::Node& Function::Node::operator=(const Node& other) {
+ if (this != &other) {
+ element.reset(fl::null);
+ left.reset(fl::null);
+ right.reset(fl::null);
+
+ copyFrom(other);
+ }
+ return *this;
+ }
+
+ void Function::Node::copyFrom(const Node& other) {
+ if (other.element.get()) element.reset(other.element->clone());
+ if (other.left.get()) left.reset(other.left->clone());
+ if (other.right.get()) right.reset(other.right->clone());
+ variable = other.variable;
+ value = other.value;
+ }
+
+ Function::Node::~Node() {
+ }
+
+ scalar Function::Node::evaluate(const std::map<std::string, scalar>* variables) const {
+ scalar result = fl::nan;
+ if (element.get()) {
+ if (element->unary) {
+ result = element->unary(left->evaluate(variables));
+ } else if (element->binary) {
+ result = element->binary(right->evaluate(variables), left->evaluate(variables));
+ } else {
+ std::ostringstream ex;
+ ex << "[function error] arity <" << element->arity << "> of "
+ << (element->isOperator() ? "operator" : "function") <<
+ " <" << element->name << "> is fl::null";
+ throw fl::Exception(ex.str(), FL_AT);
+ }
+
+ } else if (not variable.empty()) {
+ if (not variables) {
+ throw fl::Exception("[function error] "
+ "expected a map of variables, but none was provided", FL_AT);
+ }
+ std::map<std::string, scalar>::const_iterator it = variables->find(variable);
+ if (it != variables->end()) result = it->second;
+ else throw fl::Exception("[function error] "
+ "unknown variable <" + variable + ">", FL_AT);
+ } else {
+ result = value;
+ }
+ return result;
+ }
+
+ Function::Node* Function::Node::clone() const {
+ return new Node(*this);
+ }
+
+ std::string Function::Node::toString() const {
+ std::ostringstream ss;
+ if (element.get()) ss << element->name;
+ else if (not variable.empty()) ss << variable;
+ else ss << fl::Op::str(value);
+ return ss.str();
+ }
+
+ std::string Function::Node::toPrefix(const Node* node) const {
+ if (not node) node = this;
+ if (not fl::Op::isNaN(node->value)) { //is terminal
+ return fl::Op::str(node->value);
+ }
+ if (not node->variable.empty()) {
+ return node->variable;
+ }
+
+ std::ostringstream ss;
+ ss << node->toString();
+ if (node->left.get())
+ ss << " " << this->toPrefix(node->left.get());
+ if (node->right.get())
+ ss << " " << this->toPrefix(node->right.get());
+ return ss.str();
+ }
+
+ std::string Function::Node::toInfix(const Node* node) const {
+ if (not node) node = this;
+ if (not fl::Op::isNaN(node->value)) { //is proposition
+ return fl::Op::str(node->value);
+ }
+ if (not node->variable.empty()) {
+ return node->variable;
+ }
+
+ std::ostringstream ss;
+ if (node->left.get())
+ ss << this->toInfix(node->left.get()) << " ";
+ ss << node->toString();
+ if (node->right.get())
+ ss << " " << this->toInfix(node->right.get());
+ return ss.str();
+ }
+
+ std::string Function::Node::toPostfix(const Node* node) const {
+ if (not node) node = this;
+ if (not fl::Op::isNaN(node->value)) { //is proposition
+ return fl::Op::str(node->value);
+ }
+ if (not node->variable.empty()) {
+ return node->variable;
+ }
+
+ std::ostringstream ss;
+ if (node->left.get())
+ ss << this->toPostfix(node->left.get()) << " ";
+ if (node->right.get())
+ ss << this->toPostfix(node->right.get()) << " ";
+ ss << node->toString();
+ return ss.str();
+ }
+
+ /**********************************
+ * Function class.
+ **********************************/
+ Function::Function(const std::string& name,
+ const std::string& formula, const Engine* engine)
+ : Term(name), _root(fl::null), _formula(formula), _engine(engine) {
+ }
+
+ Function::Function(const Function& other) : Term(other),
+ _root(fl::null), _formula(other._formula), _engine(other._engine) {
+ if (other._root.get()) _root.reset(other._root->clone());
+ variables = other.variables;
+ }
+
+ Function& Function::operator=(const Function& other) {
+ if (this != &other) {
+ _root.reset(fl::null);
+
+ Term::operator=(other);
+ _formula = other._formula;
+ _engine = other._engine;
+ if (other._root.get()) _root.reset(other._root->clone());
+ variables = other.variables;
+ }
+ return *this;
+ }
+
+ Function::~Function() {
+ }
+
+ std::string Function::className() const {
+ return "Function";
+ }
+
+ scalar Function::membership(scalar x) const {
+ if (not this->_root.get()) {
+ throw fl::Exception("[function error] function <" + _formula + "> not loaded.", FL_AT);
+ }
+ if (this->_engine) {
+ for (int i = 0; i < this->_engine->numberOfInputVariables(); ++i) {
+ InputVariable* input = this->_engine->getInputVariable(i);
+ this->variables[input->getName()] = input->getInputValue();
+ }
+ for (int i = 0; i < this->_engine->numberOfOutputVariables(); ++i) {
+ OutputVariable* output = this->_engine->getOutputVariable(i);
+ this->variables[output->getName()] = output->getOutputValue();
+ }
+ }
+ this->variables["x"] = x;
+ return this->evaluate(&this->variables);
+ }
+
+ scalar Function::evaluate(const std::map<std::string, scalar>* localVariables) const {
+ if (not this->_root.get())
+ throw fl::Exception("[function error] evaluation failed because the function is not loaded", FL_AT);
+ if (localVariables)
+ return this->_root->evaluate(localVariables);
+ return this->_root->evaluate(&this->variables);
+ }
+
+ std::string Function::parameters() const {
+ return _formula;
+ }
+
+ void Function::configure(const std::string& parameters) {
+ load(parameters);
+ }
+
+ Function* Function::create(const std::string& name,
+ const std::string& infix, const Engine* engine) {
+ FL_unique_ptr<Function> result(new Function(name));
+ result->load(infix, engine);
+ return result.release();
+ }
+
+ bool Function::isLoaded() const {
+ return this->_root.get() != fl::null;
+ }
+
+ void Function::unload() {
+ this->_root.reset(fl::null);
+ this->variables.clear();
+ }
+
+ void Function::load() {
+ load(this->_formula);
+ }
+
+ void Function::load(const std::string& formula) {
+ load(formula, this->_engine);
+ }
+
+ void Function::load(const std::string& formula,
+ const Engine* engine) {
+ unload();
+ this->_formula = formula;
+ this->_engine = engine;
+ this->_root.reset(parse(formula));
+ membership(0.0); //make sure function evaluates without throwing exception.
+ }
+
+ void Function::setFormula(const std::string& formula) {
+ this->_formula = formula;
+ }
+
+ std::string Function::getFormula() const {
+ return this->_formula;
+ }
+
+ void Function::setEngine(const Engine* engine) {
+ this->_engine = engine;
+ }
+
+ const Engine* Function::getEngine() const {
+ return this->_engine;
+ }
+
+ Function::Node* Function::root() const {
+ return this->_root.get();
+ }
+
+ Function* Function::clone() const {
+ return new Function(*this);
+ }
+
+ Term* Function::constructor() {
+ return new Function;
+ }
+
+ std::string Function::space(const std::string& formula) const {
+ std::vector<std::string> chars;
+ chars.push_back("(");
+ chars.push_back(")");
+ chars.push_back(",");
+
+ std::vector<std::string> operators = fl::FactoryManager::instance()->function()->availableOperators();
+ for (std::size_t i = 0; i < operators.size(); ++i) {
+ if (not (operators.at(i) == fl::Rule::andKeyword() or
+ operators.at(i) == fl::Rule::orKeyword())) {
+ chars.push_back(operators.at(i));
+ }
+ }
+
+ std::string result = formula;
+ for (std::size_t i = 0; i < chars.size(); ++i) {
+ result = fl::Op::findReplace(result, chars.at(i), " " + chars.at(i) + " ");
+ }
+ return result;
+ }
+
+ /****************************************
+ * The Glorious Parser
+ * Shunting-yard algorithm
+ * TODO: Maybe change it for http://en.wikipedia.org/wiki/Operator-precedence_parser
+ ***************************************/
+
+ std::string Function::toPostfix(const std::string& formula) const {
+ std::string spacedFormula = space(formula);
+
+ std::queue<std::string> queue;
+ std::stack<std::string> stack;
+
+ std::stringstream tokenizer(spacedFormula);
+ std::string token;
+ FunctionFactory* factory = fl::FactoryManager::instance()->function();
+ while (tokenizer >> token) {
+ Element* element = factory->getObject(token);
+ bool isOperand = not element and token != "(" and token != ")" and token != ",";
+
+ if (isOperand) {
+ queue.push(token);
+
+ } else if (element and element->isFunction()) {
+ stack.push(token);
+
+ } else if (token == ",") {
+ while (not stack.empty() and stack.top() != "(") {
+ queue.push(stack.top());
+ stack.pop();
+ }
+ if (stack.empty() or stack.top() != "(") {
+ std::ostringstream ex;
+ ex << "[parsing error] mismatching parentheses in: " << formula;
+ throw fl::Exception(ex.str(), FL_AT);
+ }
+
+ } else if (element and element->isOperator()) {
+ Element* op1 = element;
+ for (;;) {
+ Element* op2 = fl::null;
+ if (not stack.empty()) op2 = factory->getObject(stack.top());
+ if (not op2) break;
+
+ if ((op1->associativity < 0 and op1->precedence == op2->precedence)
+ or op1->precedence < op2->precedence) {
+ queue.push(stack.top());
+ stack.pop();
+ } else
+ break;
+ }
+ stack.push(token);
+
+ } else if (token == "(") {
+ stack.push(token);
+
+ } else if (token == ")") {
+ while (not stack.empty() and stack.top() != "(") {
+ queue.push(stack.top());
+ stack.pop();
+ }
+ if (stack.empty() or stack.top() != "(") {
+ std::ostringstream ex;
+ ex << "[parsing error] mismatching parentheses in: " << formula;
+ throw fl::Exception(ex.str(), FL_AT);
+ }
+ stack.pop(); //get rid of "("
+
+ Element* top = fl::null;
+ if (not stack.empty()) top = factory->getObject(stack.top());
+ if (top and top->isFunction()) {
+ queue.push(stack.top());
+ stack.pop();
+ }
+ } else {
+ std::ostringstream ex;
+ ex << "[parsing error] unexpected error with token <" << token << ">";
+ throw fl::Exception(ex.str(), FL_AT);
+ }
+ }
+
+ while (not stack.empty()) {
+ if (stack.top() == "(" or stack.top() == ")") {
+ std::ostringstream ex;
+ ex << "[parsing error] mismatching parentheses in: " << formula;
+ throw fl::Exception(ex.str(), FL_AT);
+ }
+ queue.push(stack.top());
+ stack.pop();
+ }
+
+ std::stringstream ssPostfix;
+ while (not queue.empty()) {
+ ssPostfix << queue.front();
+ queue.pop();
+ if (not queue.empty()) ssPostfix << " ";
+ }
+ // FL_DBG("postfix=" << ssPostfix.str());
+ return ssPostfix.str();
+ }
+
+ // bool FunctionFactory::isOperand(const std::string& name) const {
+ // //An operand is not a parenthesis...
+ // if (name == "(" or name == ")" or name == ",") return false;
+ // //nor an operator...
+ // if (isOperator(name)) return false;
+ // //nor a function...
+ // if (isFunction(name)) return false;
+ // //...it is everything else :)
+ // return true;
+ // }
+
+ Function::Node* Function::parse(const std::string& formula) {
+ if (formula.empty())
+ throw fl::Exception("[function error] formula is empty", FL_AT);
+ std::string postfix = toPostfix(formula);
+
+ std::stack<Node*> stack;
+
+ std::istringstream tokenizer(postfix);
+ std::string token;
+ FunctionFactory* factory = fl::FactoryManager::instance()->function();
+ while (tokenizer >> token) {
+ Element* element = factory->getObject(token);
+ bool isOperand = not element and token != "(" and token != ")" and token != ",";
+
+ if (element) {
+ if (element->arity > (int) stack.size()) {
+ std::ostringstream ss;
+ ss << "[function error] " << (element->isOperator() ? "operator" : "function") <<
+ " <" << element->name << "> has arity <" << element->arity << ">, "
+ "but found <" << stack.size() << "> element" <<
+ (stack.size() == 1 ? "" : "s");
+ throw fl::Exception(ss.str(), FL_AT);
+ }
+
+ Node* node = new Node(element->clone());
+ node->left.reset(stack.top());
+ stack.pop();
+ if (element->arity == 2) {
+ node->right.reset(stack.top());
+ stack.pop();
+ }
+ stack.push(node);
+
+ } else if (isOperand) {
+ Node* node;
+ try {
+ scalar value = fl::Op::toScalar(token);
+ node = new Node(value);
+ } catch (std::exception& ex) {
+ (void) ex;
+ node = new Node(token);
+ }
+ stack.push(node);
+ }
+ }
+
+ if (stack.size() != 1)
+ throw fl::Exception("[function error] ill-formed formula <" + formula + ">", FL_AT);
+
+ return stack.top();
+ }
+
+ void Function::main() {
+ Function f;
+ std::string text = "3+4*2/(1-5)^2^3";
+ FL_LOG(f.toPostfix(text));
+ FL_LOG("P: " << f.parse(text)->toInfix());
+ FL_LOG(">" << f.parse(text)->evaluate());
+ //3 4 2 * 1 5 - 2 3 ^ ^ / +
+
+ f.variables["y"] = 1.0;
+ text = "sin(y*x)^2/x";
+ FL_LOG("pre: " << f.parse(text)->toPrefix());
+ FL_LOG("in: " << f.parse(text)->toInfix());
+ FL_LOG("pos: " << f.parse(text)->toPostfix());
+ f.load(text);
+ FL_LOG("Result: " << f.membership(1));
+ //y x * sin 2 ^ x /
+
+
+ text = "(Temperature is High and Oxygen is Low) or "
+ "(Temperature is Low and (Oxygen is Low or Oxygen is High))";
+ FL_LOG(f.toPostfix(text));
+
+ f.variables["pi"] = 3.14;
+ text = "-5 *4/sin(-pi/2)";
+ FL_LOG(f.toPostfix(text));
+ try {
+ FL_LOG(f.parse(text)->evaluate());
+ } catch (std::exception& e) {
+ FL_LOG(e.what());
+ }
+ f.variables["pi"] = 3.14;
+ text = "~5 *4/sin(~pi/2)";
+ FL_LOG(f.toPostfix(text));
+ try {
+ FL_LOG(f.parse(text)->evaluate(&f.variables));
+ } catch (std::exception& e) {
+ FL_LOG(e.what());
+ }
+ }
+
+}