If after the replacement of x the result is an equation up to 2 degrees in y, then it can be solved by Bhaskara’s formula:
a*y^2 + b*y + c = 0
y = -b +- raiz(b^2 - 4*a*c)
-----------------------
2*a
The trickiest thing is interpret the entrance to... You need to convert it from the text format to an abstract format, which allows you to manipulate the elements (multiplication of terms, playing terms from right to left with reversed sign, etc.) until isolating a, b and c.
The ideal is to use some parser able to interpret its desired format. In this answer, I will give a very simple suggestion, without error treatment or anything, but still able to interpret simple equations as your example.
Lexical analysis
Basically, a sequence of digits is a number (which I will 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";
}
Separate text in tokens is simply the case to go withdrawing 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 take precedence 0, exponentiation 1, multiplication 2, etc (i.e. a*b^c is a*(b^c) and not (a*b)^c), if we read the tokens from left to right, and we decide who goes in who, let’s end with a tree of expressions and sub-expressions:
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 method well simple to interpret an expression. It associates to the right always, while not every operation does it (power, for example, associates to the left). Again, I suggest looking for a parser more complete to make your system more robust.
That said, let’s finally get to the point of the question:
Replacing the x
In the code above, I defined a type variavel which 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 to say, x flipped {x:1,y:0,c:1}, y^2 flipped {x:0,y:2,c:1} and 42 flipped {x:0,y:0,c:42}. You can mix, too, like, 42*x*y^2 flipped {x:1,y:2,c:42 }, since the x is nothing more than 1 (in this representation; in the user input, can). Representing the variables in this way, replace the x by a value is simply a matter of multiplying the c at the value of x, and pass the xof 1 for 0 (if there was no 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 the x, we want to find the plots and pass them all to the left. In some cases it is easy:
x^2 + 3*y^2 = 12 [x = 2]
==>
4 + 3*y^2 + (-12) = 0
In others it’s harder:
(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 parcel:
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()); }
};
},
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 = have to pass everything that is right to left, with the reversed signal:
"=":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, only apply the formula mentioned at the beginning of the reply:
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)];
}
Full example:
Joining the above code, with one or two extra things (the missing operators, and the parentheses - which have zero precedence, but "capture" everything within 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 said, this parser handmade is not very good, but it should be enough to demonstrate the logic necessary to deal with the equations, which is the focus of the question.
I leave the bug fix when x == 0 as an exercise for the reader... P
There is no generalized way of solving equations from third degree upward. His examples are both second degree, so the Bhaskara’s formula is sufficient. In this case, it is only a matter of interpreting and manipulating the user input. In what format will this input be made? Can you give some examples? (type, how the user would enter with "a raised to b"?)
– mgibsonbr
it will enter as follows: x 2 + 3*y 2 = 12. Where x I will fill in the program with values from -100 to 100. There’s a website that does exactly what I want: http://www.wolframalpha.com/
– HiHello
Dude, comparing wolframalpha to anything we poor mortals are capable of is bullshit... P
– mgibsonbr
Very relevant to the problem: http://www.cs.cornell.edu/w8/~Andru/relplot/ I contacted you requesting the source code. If accepted, I will post an answer explaining how the same thing can be done with general equations and not just polynomials.
– Guilherme Bernal