Resolution of equations

6

I created a Cartesian plan and I get the user an equation whatsoever. My goal is to draw this equation on the plane. I'm doing this using canvas. But here comes a problem, I can only do this if I separate each type of equation (circle, straight ...). What I want is for the user to put any kind of equation, of 2 variables (x and y). So I get and put in the 'x' values from -100 to 100. That is, in the end, I'll have an equation with a single variable (y). But I can not generalize these equations.

How do I make an algorithm so that regardless of the way the user enters, I isolate the 'y' of the equation?

Example 1: 3² / 4 + y² / 25 = 1
Example 2: 4²-6 = (y-1) ²

It should return the value of y.

Who can help, thank you! // JAVASCRIPT, but I accept PHP or C ++ to have as base for me to do in javascript (without using framework in any of these)

    
asked by anonymous 13.12.2014 / 02:30

1 answer

6

If after the substitution of x the result is an equation up to 2nd degree in y , then you can solve for #:

a*y^2 + b*y + c = 0

y = -b +- raiz(b^2 - 4*a*c)
    -----------------------
              2*a

The most complicated is to interpret the input ... You need to convert it from text format to an abstract format, which allows you to manipulate the elements (multiply terms, play terms from the right to the left with an inverted signal, etc.) until you isolate a , b and c .

The ideal is to use some parser capable of interpreting your desired format. In this answer, I will give a very simple suggestion, without error handling or anything, but still able to interpret simple equations as your example.

Lexical analysis

Basically, a sequence of digits is a number (which I'll call c - "constant"), x is x and y is y . Spaces are ignored, and operators are = , + e - , * e / and ^ , in that order of precedence . Parentheses are a special case ...

  function token() {
    var numero = /^-?\d+/.exec(s);
    if ( numero ) {
      s = s.substring(numero[0].length);
      return variavel(0,0,parseInt(numero[0], 10)); // x^0 * y^0 * c
    }

    var simbolo = s[0];
    s = s.substring(1);

    if ( simbolo == "x" )
      return variavel(1); // x^1 * y^0 * 1
    if ( simbolo == "y" )
      return variavel(0,1); // x^0 * y^1 * 1
    if ( operadores[simbolo] )
        return operadores[simbolo]();
    if ( simbolo == " " )
      return token(); // Ignora o espaço em branco

    throw "Formato inválido";
  }

Separating text into tokens is simply the case of removing tokens from the beginning of the string until it ends:

function lexica(str) {
  var s = str;
  function token() { ... }

  var tokens = [];
  while ( s.length > 0 )
    tokens.push(token());
  return tokens;
}

Syntactic analysis

Assuming that variables and constants have precedence 0 , exponentiation 1 , multiplication 2 , etc (ie a*b^c is a*(b^c) and not (a*b)^c ), if we read tokens < in> from left to right, and decide who goes into who, let's end with a tree of expressions and subexpressions:

function sintatica(tokens, i) {
  var ret = undefined;
  i = i || 0;
  for ( ; i < tokens.length ; i++ ) {
    if ( !ret || tokens[i].p >= ret.p ) { // Se o próximo da lista tem precedência maior
      tokens[i].esq = ret;                // a antiga raiz entra na esquerda dele
      ret = tokens[i];                    // e ele vira a raiz
    }
    else { // Senão, ele é inserido na direita da raiz

      // mas se alguém na direita tem precedência menor que ele
      for (var pai = ret ; pai.dir && pai.dir.p > tokens[i].p ; pai = pai.dir) { }
      tokens[i].esq = tokens[i].esq || pai.dir; // então ele o coloca à sua esquerda
      pai.dir = tokens[i];                      // e toma o lugar dele
    }
  }
  return [ret,i]; // No fim todos os tokens vão formar uma árvore, na precedência certa
}

This is a simple method method of interpreting an expression. It associates to the right always, whereas not every operation does this (the power, for example, associates to the left). Again, I suggest looking for a more complete parser to make your system more robust.

That said, let's finally focus on the question:

Replacing the x

In the code above, I set a variavel type that is implemented as follows:

function variavel(x,y,c) {
  return {
    x:x || 0, // O expoente do x, padrão 0
    y:y || 0, // O expoente do y, padrão 0
    c:c || 1, // Uma constante, padrão 1
    p:0,      // A precedência é zero (não é um operador)

That is, x turns {x:1,y:0,c:1} , y^2 turns {x:0,y:2,c:1} and 42 turns {x:0,y:0,c:42} . You can also mix, type 42*x*y^2 {x:1,y:2,c:42 } , as long as x does not exceed 1 (in that representation, at user input, you can). By representing the variables in this way, replacing x with a value is simply a matter of multiplying c by the value of x , and pass x 1 to 0 (if there was x , the value does not change).

    substitui:function(x) { this.c *= this.x ? x : 1; this.x = 0; },

In operators, simply replace the left and right side independently ...

function substitui(x) {
  this.esq.substitui(x);
  this.dir.substitui(x);
}

Finding the plots

After replacing x , we want to find the plots and move them all to the left. In some cases it's easy:

x^2 + 3*y^2 = 12 [x = 2]
==>
4 + 3*y^2 + (-12) = 0

In others it is more difficult:

(y + 1)^2
==>
(y + 1)*(y + 1)
(y*y) + (y*1) + (1*y) + (1*1)

The solution is to make each operator have a function to turn their arguments into a list of plots. A variable / constant is a single portion:

function variavel(x,y,c) {
    soma:function() { return [this]; },

A sum is simply the set of plots on the left plus the set of plots on the right:

var operadores = {
  "+":function(){
    return {
      p:3,
      substitui:substitui,
      soma:function() { return this.esq.soma().concat(this.dir.soma()); }
    };
  },

The multiplication has to multiply each portion of the left with each portion of the right:

  "*":function(){
    return {
      p:2,
      substitui:substitui,
      soma:function() {
        var esq = this.esq.soma(); // Acha todas as parcelas da esquerda
        var dir = this.dir.soma(); // e todas da direita

        var ret = [];
        for ( var i = 0 ; i < esq.length ; i++ )   // Cada termo da esquerda
          for ( var t = 0 ; t < dir.length ; t++ ) // Vezes cada termo da direita
            ret.push(esq[i].vezes(dir[t]));
        return ret;
      }
    };
  },

Etc. Finally, the = operator has to pass everything that is on the right to the left, with the sign reversed:

  "=":function(){
    return {
      p:4,
      substitui:substitui,
      soma:function() {
        var ret = this.esq.soma();
        var dir = this.dir.soma();
        for ( var i = 0 ; i < dir.length ; i++ ) {
          dir[i].c = -dir[i].c; // Passa pra esquerda, trocando o sinal
          ret.push(dir[i]);
        }
        return ret;
      }
    };
  },

Bhaskara

Finally, just apply the formula mentioned at the beginning of the answer:

function avaliar(equacao, x) {
  var raiz = sintatica(lexica(equacao))[0]; // Interpreta
  raiz.substitui(x); // Substitui o x
  var termos = raiz.soma(); // Transforma numa soma de termos

  // Bhaskara
  var a = 0, b = 0, c = 0;
  for ( var i = 0 ; i < termos.length ; i++ ) {
    if ( termos[i].y == 0 )
      c += termos[i].c;
    else if ( termos[i].y == 1 )
      b += termos[i].c;
    else if ( termos[i].y == 2 )
      a += termos[i].c;
    else
      throw "Equação maior que segundo grau!";
  }

  if ( a == 0 )
    return [-c/b] // Equação de primeiro grau

  var rdelta = Math.sqrt(b*b - 4*a*c);
  return [(-b + rdelta)/(2*a), (-b - rdelta)/(2*a)];
}

Complete example:

Adding the code above, with one or two more things (the missing operators, and the parentheses - which have zero precedence but "capture" everything inside them), we have a complete example:

function substitui(x) {
  this.esq.substitui(x);
  this.dir.substitui(x);
}

var operadores = {
  "=":function(){
    return {
      p:4,
      substitui:substitui,
      soma:function() {
        var ret = this.esq.soma();
        var dir = this.dir.soma();
        for ( var i = 0 ; i < dir.length ; i++ ) {
          dir[i].c = -dir[i].c; // Passa pra esquerda, trocando o sinal
          ret.push(dir[i]);
        }
        return ret;
      }
    };
  },
  "+":function(){
    return {
      p:3,
      substitui:substitui,
      soma:function() { return this.esq.soma().concat(this.dir.soma()); }
    };
  },
  "-":function(){
    return {
      p:3,
      substitui:substitui,
      soma:function() {
        var ret = this.esq.soma();
        var dir = this.dir.soma();
        for ( var i = 0 ; i < dir.length ; i++ ) {
          dir[i].c = -dir[i].c; // troca o sinal
          ret.push(dir[i]);
        }
        return ret;
      }
    };
  },
  "*":function(){
    return {
      p:2,
      substitui:substitui,
      soma:function() {
        var esq = this.esq.soma();
        var dir = this.dir.soma();
        var ret = [];
        for ( var i = 0 ; i < esq.length ; i++ )   // Cada termo da esquerda
          for ( var t = 0 ; t < dir.length ; t++ ) // Vezes cada termo da direita
            ret.push(esq[i].vezes(dir[t]));
        return ret;
      }
    };
  },
  "/":function(){
    return {
      p:1,
      substitui:substitui,
      soma:function() {
        var ret = this.esq.soma();
        var divisor = this.dir.c;
        for ( var i = 0 ; i < ret.length ; i++ )
            ret[i].c /= divisor;
        return ret;
      }
    };
  },
  "^":function(){
    return {
      p:1,
      substitui:substitui,
      soma:function() {
        var esq = this.esq.soma();
        var potencia = this.dir.c;
        var ret = esq;
        while ( potencia-- > 1 ) { // Cada termo da esquerda multiplica com
          var tmp = ret;           // cada termo da esquerda n vezes
          var ret = [];
          for ( var i = 0 ; i < tmp.length ; i++ )
            for ( var t = 0 ; t < esq.length ; t++ )
              ret.push(tmp[i].vezes(esq[t]));
        }
        return ret;
      }
    };
  },
  "(":function(){
    return { par:"(" };
  },
  ")":function(){
    return { par:")" };
  }
};

function variavel(x,y,c) {
  return {
    x:x || 0,
    y:y || 0,
    c:c || 1,
    p:0,
    substitui:function(x) { this.c *= this.x ? x : 1; this.x = 0; },
    soma:function() { return [this]; },
    vezes:function(v) {
      return variavel(this.x + v.x, this.y + v.y, this.c * v.c);
    }
  }
}

function lexica(str) {
  var s = str;
  
  function token() {
    var numero = /^\d+/.exec(s);
    if ( numero ) {
      s = s.substring(numero[0].length);
      return variavel(0,0,parseInt(numero[0], 10));
    }
    
    var simbolo = s[0];
    s = s.substring(1);
    
    if ( simbolo == "x" )
      return variavel(1);
    if ( simbolo == "y" )
      return variavel(0,1);
    if ( operadores[simbolo] )
        return operadores[simbolo]();
    if ( simbolo == " " )
      return token(); // Ignora o espaço em branco
      
    throw "Formato inválido";
  }
  
  var tokens = [];
  while ( s.length > 0 )
    tokens.push(token());
  return tokens;
}

function sintatica(tokens, i) {
  var ret = undefined;
  i = i || 0;
  for ( ; i < tokens.length ; i++ ) {
    // Parênteses "quebram" a lógica da precedência...
    if ( tokens[i].par == ')' )
        break;
    if ( tokens[i].par == '(' ) {
        var conteudo = sintatica(tokens, i+1);
        i = conteudo[1];
        tokens[i] = conteudo[0];
        tokens[i].p = 0;
    }
    //
      
    if ( !ret || tokens[i].p >= ret.p ) {
      tokens[i].esq = ret;
      ret = tokens[i];
    }
    else {
      for (var pai = ret ; pai.dir && pai.dir.p > tokens[i].p ; pai = pai.dir) { }
      tokens[i].esq = tokens[i].esq || pai.dir;
      pai.dir = tokens[i];
    }
  }
  return [ret,i];
}

function avaliar(equacao, x) {
  var raiz = sintatica(lexica(equacao))[0]; // Interpreta
  raiz.substitui(x); // Substitui o x
  var termos = raiz.soma(); // Transforma numa soma de termos
    
  // Bhaskara
  var a = 0, b = 0, c = 0;
  for ( var i = 0 ; i < termos.length ; i++ ) {
    if ( termos[i].y == 0 )
      c += termos[i].c;
    else if ( termos[i].y == 1 )
      b += termos[i].c;
    else if ( termos[i].y == 2 )
      a += termos[i].c;
    else
      throw "Equação maior que segundo grau!";
  }
  
  if ( a == 0 )
    return [-c/b] // Equação de primeiro grau
  
  var rdelta = Math.sqrt(b*b - 4*a*c);
  return [(-b + rdelta)/(2*a), (-b - rdelta)/(2*a)];
}

/***** Exemplos *****/

var exemplos = ["x^2 + 3*y^2 = 12", 
                "x^2/4 + y^2/25 = 1",
                "x^2 - 6 = (y-1)^2",
                "4*x + 5*y = 15"];

for ( var e = 0 ; e < exemplos.length ; e++ ) {

  var entrada = exemplos[e]; 
  
  document.body.innerHTML += "<p><strong>" + entrada + "</strong></p>";

  for ( var i = 0 ; i <= 5 ; i++ )
    document.body.innerHTML += "<p>x = " + i + ", y = " +
                                   JSON.stringify(avaliar(entrada,i)) + 
                               "</p>";
}

As already mentioned, this handmade parser is not very good, but should be enough to demonstrate the logic needed to deal with the equations, which is the focus of the question.

I leave the bug fix when x == 0 as exercise for the reader ...: P     

13.12.2014 / 17:37