Domanda
Mi viene data una stringa 2*x + 5 - (3*x-2)=x + 5 e ho bisogno di risolvere x . Il mio pensiero è che lo convertirò in un albero di espressione, qualcosa del genere,
=
/ \
- +
/\ /\
+ - x 5
/\ /\
* 5 * 2
/\ /\
2 x 3 x
Ma come faccio a ridurre effettivamente l'albero da qui? Altre idee?
Risposta accettata
Devi ridurlo usando gli assiomi dell'algebra
a * (b + c) -> (a * b) + (a * c)
Questo viene fatto controllando i tipi di ogni nodo nell'albero del passaggio. Una volta che la cosa è stata completamente espansa in termini, puoi verificare che siano effettivamente lineari, ecc.
I valori nella struttura saranno variabili o numeri. Non è molto semplice rappresentarli come classi che ereditano da una classe AbstractTreeNode, tuttavia, poiché cplusplus non ha dispatch multipli. Quindi è meglio farlo in modo 'c'.
enum NodeType {
Number,
Variable,
Addition //to represent the + and *
}
struct Node {
NodeType type;
//union {char*, int, Node*[2]} //psuedo code, but you need
//something kind of like this for the
//variable name ("x") and numerical value
//and the children
}
Ora puoi interrogare i loro tipi di un nodo e i suoi figli usando il caso di commutazione.
Come ho detto prima, il codice idiatico c ++ userebbe funzioni virtuali, ma mancano del dispatch multiplo necessario per risolverlo in modo pulito. (Dovresti comunque memorizzare il tipo)
Quindi raggruppate i termini, ecc. E risolvete l'equazione.
Puoi avere regole per normalizzare l'albero, per esempio
constant + variable -> variable + constant
Metterei x sempre a sinistra di un termine. Quindi x * 2 + x * 4 potrebbe essere semplificato più facilmente
var * constant + var * constant -> (sum of constants) * var
Nel tuo esempio ...
Innanzitutto, semplifica il '=' spostando i termini (come da regola sopra)
Il lato destro sarà -1 * (x + 5), diventando -1 * x + -1 * 5. Il lato sinistro sarà più difficile - considera la sostituzione di a - b con un + -1 * b.
Infine,
2x + 5 + -3x + 2 + -x + -5 = 0
Quindi puoi raggruppare i termini sempre nel modo desiderato. (Scansionando insieme, ecc.)
(2 + -3 + -1) x + 5 + 2 + -5 = 0
Sommali e quando hai mx + c, risolvilo.
Risposta popolare
Supponendo che l'equazione possa ridurre a f (x) = 0 e f (x) = a * x + b.
Puoi trasformare tutte le foglie nell'albero delle espressioni in f (x), ad esempio: 2 -> 0 * x + 2, 3 * x -> 3 * x + 0, quindi puoi eseguire operazioni aritmetiche di f (x) in albero delle espressioni. risolve infine l'equazione f (x) = 0.
Se la funzione è molto più complicata del polinomio, puoi eseguire una ricerca binaria su x e usare l'albero delle espressioni per calcolare il lato sinistro e destro dell'equazione.
Autorizzato sotto: CC-BY-SA with attribution
Non affiliato con Stack Overflow