6

Criei um plano cartesiano e eu recebo do usuário uma equação qualquer. O meu objetivo é traçar essa equação no plano. Estou fazendo isso usando canvas. Só que aqui entra um problema, eu só consigo fazer isso se eu separar cada tipo de equação (círculo, reta...). O que eu quero é que o usuário coloque qualquer tipo de equação, de 2 variáveis (x e y). Então eu pego e coloco no 'x' valores de -100 a 100. Ou seja, no final das contas, eu vou ter uma equação com uma só variável (y). Só que eu não consigo generalizar essas equações.

Como eu faço um algoritmo para que independente da forma que o usuário insira, eu isole o 'y' da equação?

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

Ele deve retornar qual o valor de y.

Quem puder ajudar, agradeço!
//JAVASCRIPT, mas aceito PHP ou C++ para ter como base para eu fazer em javascript (sem usar framework em nenhuma dessas)

4
  • 2
    Não existe um meio generalizado de se resolver equações do 3º grau para cima. Seus exemplos são ambos de 2º grau, então a Fórmula de Bhaskara é suficiente. Nesse caso, é só uma questão de interpretar e manipular a entrada do usuário. Em que formato será feita essa entrada? Pode dar alguns exemplos? (tipo, como o usuário entraria com "a elevado a b"?)
    – mgibsonbr
    13/12/2014 às 2:55
  • 1
    ele vai entrar da seguinte forma: x^2 + 3*y^2 = 12. Sendo que o 'x' eu vou preencher no programa com valores de -100 a 100. Tem um site que faz exatamente o que eu quero: wolframalpha.com
    – HiHello
    13/12/2014 às 12:33
  • 1
    Cara, comparar o wolframalpha com qualquer coisa que nós pobres mortais somos capaz de fazer é sacanagem... :P
    – mgibsonbr
    13/12/2014 às 16:37
  • 2
    Bastante relevante para o problema: cs.cornell.edu/w8/~andru/relplot Eu entrei em contato solicitando o código fonte. Caso aceito, postarei uma resposta com explicações sobre como a mesma coisa pode ser feita com equações gerais e não apenas polinômios. 13/12/2014 às 17:19

1 Resposta 1

6

Se após a substituição do x o resultado for uma equação até de 2º grau em y, então dá para resolver pela Fórmula de Bhaskara:

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

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

O mais complicado é interpretar a entrada... Você precisa convertê-la do formato texto para um formato abstrato, que te permita manipular os elementos (fazer a multiplicação de termos, jogar termos da direita pra esquerda com sinal invertido, etc) até isolar a, b e c.

O ideal é usar algum parser capaz de interpretar o seu formato desejado. Nessa resposta, vou dar uma sugestão bem simples, sem tratamento de erro nem nada, mas ainda capaz de interpretar equações simples como seu exemplo.

Análise léxica

Basicamente, uma sequência de dígitos é um número (que chamarei de c - "constante"), x é x e y é y. Espaços são ignorados, e os operadores são =, + e -, * e / e ^, nessa ordem de precedência. Parênteses são um caso especial...

  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";
  }

Separar o texto em tokens é simplesmente o caso de ir retirando tokens do começo da string até ela acabar:

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

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

Análise sintática

Assumindo que variáveis e constantes têm precedência 0, exponenciação 1, multiplicação 2, etc (i.e. a*b^c é a*(b^c) e não (a*b)^c), se lermos os tokens da esquerda pra direita, e decidirmos quem entra dentro de quem, vamos terminar com uma árvore de expressões e sub-expressões:

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
}

Esse é um método bem simplório de se interpretar uma expressão. Ele associa à direita sempre, enquanto nem toda operação faz isso (a potência, por exemplo, associa à esquerda). De novo, sugiro procurar um parser mais completo para tornar seu sistema mais robusto.

Dito isso, vamos finalmente ao foco da pergunta:

Substituindo o x

No código acima, eu defini um tipo variavel que é implementado da seguinte forma:

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)

Ou seja, x vira {x:1,y:0,c:1}, y^2 vira {x:0,y:2,c:1} e 42 vira {x:0,y:0,c:42}. Também dá pra misturar, tipo 42*x*y^2 vira {x:1,y:2,c:42 }, desde que o x não passe de 1 (nessa representação; na entrada do usuário, pode). Representando as variáveis dessa forma, substituir o x por um valor é simplesmente uma questão de multiplicar o c pelo valor de x, e passar o xde 1 para 0 (se não havia x, o valor não se altera).

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

Nos operadores, basta substituir independentemente o lado esquerdo e o lado direito...

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

Achando as parcelas

Depois de substituir o x, queremos achar as parcelas e passar todas elas pra esquerda. Em alguns casos é fácil:

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

Em outros é mais difícil:

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

A solução é fazer com que cada operador tenha um função pra transformar seus argumentos numa lista de parcelas. Uma variável/constante é uma parcela só:

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

Uma soma é simplesmente o conjunto das parcelas da esquerda mais o conjunto das parcelas da direita:

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

A multiplicação tem que multiplicar cada parcela da esquerda com cada parcela da direita:

  "*":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. Por fim, o operador = têm de passar tudo que está na direita pra esquerda, com o sinal invertido:

  "=":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

Por fim, é só aplicar a fórmula mencionada no início da resposta:

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)];
}

Exemplo completo:

Juntando o código acima, com uma ou outra coisinha a mais (os operadores que faltavam, e os parênteses - que têm precedência zero, mas "capturam" tudo o que tem dentro deles), temos um exemplo completo:

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>";
}

Como já dito, esse parser feito à mão não é muito bom, mas deve ser suficiente pra demonstrar a lógica necessária pra tratar das equações, que é o foco da pergunta.

Deixo a correção do bug quando x == 0 como exercício para o leitor... :P

1
  • Eu tinha começado esboçar algo do tipo, mas vi que daria muito trabalho fazer tudo que eu queria.. Quando pensei no problema achei que seria mais simples, tanto que já to com o traçador e o gráfico prontos (só falta interpretar a equação) rsrs. No mais, valeu pela ajuda!
    – HiHello
    13/12/2014 às 16:57

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .