Lösen linearer Gleichungen, dargestellt als String

algorithm expression-trees

Frage

Ich gebe eine Zeichenfolge 2*x + 5 - (3*x-2)=x + 5 und ich muss für x lösen. Mein Denkprozess ist, dass ich es in einen Ausdrucksbaum umwandeln würde.

          =
        /  \
       -    +
      /\    /\
     +  -   x  5
    /\  /\ 
   *  5 * 2
  /\   /\
 2  x  3 x

Aber wie reduziere ich den Baum von hier eigentlich? Irgendwelche anderen Ideen?

Akzeptierte Antwort

Sie müssen es mit Axiomen aus der Algebra reduzieren

a * (b + c) -> (a * b) + (a * c)

Dies wird durch Überprüfen der Typen jedes Knotens in der Pass-Struktur durchgeführt. Sobald das Ding vollständig zu Termen erweitert wurde, können Sie überprüfen, ob sie tatsächlich linear sind usw.

Die Werte in der Baumstruktur sind entweder Variablen oder Zahlen. Es ist nicht sehr nett, diese als Klassen darzustellen, die von einer Klasse von AbstractTreeNode geerbt werden, da cplusplus nicht mehrere Dispatchs hat. Es ist also besser, es auf "c" zu machen.

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
}

Jetzt können Sie die Typen eines Knotens und seiner untergeordneten Objekte abfragen, indem Sie den Schalter case verwenden.

Wie ich bereits sagte - c ++ idiomatic Code würde virtuelle Funktionen verwenden, aber es fehlt die notwendige mehrfache Versendung, um dies sauber zu lösen. (Sie müssten den Typ trotzdem speichern)

Dann gruppieren Sie Begriffe usw. und lösen die Gleichung.

Sie können Regeln haben, um beispielsweise den Baum zu normalisieren

constant + variable -> variable + constant

Würde x immer links von einem Begriff setzen. Dann könnte x * 2 + x * 4 einfacher vereinfacht werden

var * constant + var * constant -> (sum of constants) * var

In deinem Beispiel ...

Vereinfachen Sie zunächst das '=' durch Verschieben der Begriffe (gemäß der obigen Regel).

Die rechte Seite wird -1 * (x + 5) und wird -1 * x + -1 * 5. Die linke Seite wird härter sein - erwäge, a - b durch a + -1 * b zu ersetzen.

Schließlich,

2x + 5 + -3x + 2 + -x + -5 = 0

Dann können Sie Begriffe so gruppieren, wie Sie möchten. (Durch Scannen usw.)

(2 + -3 + -1) x + 5 + 2 + -5 = 0

Fasse sie zusammen und wenn du mx + c hast, löse sie.


Beliebte Antwort

Angenommen, die Gleichung kann sich auf f (x) = 0 reduzieren, und f (x) = a * x + b.

Sie können alle Blätter im Ausdrucksbaum in f (x) umwandeln, zum Beispiel: 2 -> 0 * x + 2, 3 * x -> 3 * x + 0, dann können Sie arithmetische Operationen von f (x) ausführen Ausdrucksbaum. schließlich löse die Gleichung f (x) = 0.

Wenn die Funktion viel komplizierter als Polynom ist, können Sie eine binäre Suche auf x durchführen und den Ausdrucksbaum verwenden, um die linke und rechte Seite der Gleichung zu berechnen.



Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow
Lizenziert unter: CC-BY-SA with attribution
Nicht verbunden mit Stack Overflow