Nach x Auflösen

V

Virus

0
Hallo miteinander,
Ich beschäftige mich jetzt schon fast ein halbes jahr mit c++, und will nun ein kleines projekt schreiben, und zwar soll dieses programm nach einfach eingabe einer formel ( z.b. 40 = 2x + 10) in der konsole diese nach x auflösen.
Das ganze soll objektorientiert programmiert werden.
Nun habe ich aber keinen schimmer wie ich das verwirklichen bzw wo ich anfangen soll.
Ein paar einfache Anregungen wären nett.

Gruß Virus
 
Je nachdem was für Gleichungen du aufzulösen gedenkst, wird das ein enorm schwieriges Unterfangen. Generell solltest du einen Parser schreiben, um die Struktur der Gleichung zu erkennen, x zu finden und einzeln entsprechende Umkehrungen für die Operationen durchzuführen. Sollte x nur linear vorkommen ginge dies noch, da du lediglich die anderen Summanden auf beiden Seiten subtrahieren musst und dann durch den entsprechenden Faktor teilen musst, aber sobald es viel komplizierter(Schon ax^5 + bx^4 + cx^3 + dx^2 + ex + f = 0 lässt sich meines Wissens schon nur numerisch lösen) wird, bekommt man schnell Probleme.
Allgemein würde ich als Übung damit anfangen einfache Rechenausdrücke wie "4+3*2" zu parsen, wenn das funktioniert kannst du Variablen hinzufügen.
 
Hallo,
wenn man es numerisch betrachtet, ist es ganz einfach:
Du musst die Nullstelle von 40 - (2x + 10) finden.

Es gibt einige Algorithmen, die relativ effektiv eine Nullstelle finden und auch recht leicht zu implementieren sind, insbesondere wenn man schon einen Intervall angeben kann, in der die Nullstelle liegen muss (z.B. dort zwischen 0 und 40).


Dieses algebraisch zu lösen, also nach:
40 = 2x + 10 | -10
30 = 2x | :2
15 = x

ist es schon sehr schwierig, gut, je nachdem was man an Operatoren zulässt. Auch das parsen solch einer Gleichung ist gar nicht so leicht.
 
Ich hab mal einen Parser in java geschrieben(Nur normale math ausdrücke).
Leider is iwo noch ein Bug, da bei 99 - 99 und ähnlichen Ausdrücken er sich aufhängt.
Code: 
package math.parser;

/**
 * @dateOfCreation 19.07.2008
 */
public class Parser {
	
	// public static Rational solve(String mathString) {
	//		
	// mathString = removeBracketSurround(mathString);
	//		
	// if (isNumber(mathString)) {
	// return new Rational(Integer.valueOf(mathString), 1);
	// }
	//		
	// int mainSign = giveIndexOfMainSign(mathString);
	// String part1 = new String(mathString.substring(0, mainSign));
	// String part2 = new String(mathString.substring(mainSign + 1));
	// switch (mathString.charAt(mainSign)) {
	// case '+':
	// return solve(part1).add(solve(part2));
	// case '-':
	// return solve(part1).sub(solve(part2));
	// case '*':
	// return solve(part1).mult(solve(part2));
	// case '/':
	// if (isNumber(part1) && isNumber(part2)) {
	// return new Rational(Integer.valueOf(part1), Integer
	// .valueOf(part2));
	// }
	// return solve(part1).div(solve(part2));
	// }
	//		
	// return Rational.NOTSOLVEABLE;
	//		
	// }
	
	private static Rational solve_help(String mathString, MathSign[] functions) {
		
		// mathString = removeBracketSurround(mathString);
		
		if (isNumber(mathString)) {
			return new Rational(Integer.valueOf(mathString), 1);
		}
		
		int mainSign = giveIndexOfMainSign(mathString);
		if (mainSign == -1) {
			boolean gehtnoch = true;
			while (gehtnoch) {
				String temp = new String(mathString);
				mathString = removeBracketSurround(mathString);
				if (!temp.equals(mathString)) {
					mainSign = giveIndexOfMainSign(mathString);
				}
				else {
					gehtnoch = false;
				}
			}
		}
		if (mainSign == -1) {
			return Rational.NOTSOLVEABLE;
		}
		String part1 = new String(mathString.substring(0, mainSign));
		String part2 = new String(mathString.substring(mainSign + 1));
		
		for (MathSign function : functions) {
			Rational temp = function.compute(mathString.charAt(mainSign),
					part1, part2);
			if (temp != null) {
				return temp;
			}
		}
		return Rational.NOTSOLVEABLE;
	}
	
	public static Rational solve(String mathString) {
		MathSign[] functions = { new PlusMinus(), new DivideTimes(),
				new Power() };
		
		return solve_help(mathString, functions);
	}
	
	private static int giveIndexOfMainSign(String mathString) {
		int openBrackets = 0;
		int firstPlusMinus = -1;
		int firstDivideTimes = -1;
		int firstPower = -1;
		for (int i = 0; i < mathString.length(); i++) {
			switch (mathString.charAt(i)) {
				case '(':
					openBrackets++;
					break;
				case ')':
					openBrackets--;
					break;
			}
			if (openBrackets == 0) {
				switch (mathString.charAt(i)) {
					case '^':
						firstPower = (firstPower == -1) ? i : firstPower;
						break;
					case '/':
						firstDivideTimes = (firstDivideTimes == -1) ? i
								: firstDivideTimes;
						break;
					case '*':
						firstDivideTimes = (firstDivideTimes == -1) ? i
								: firstDivideTimes;
						break;
					case '+':
						firstPlusMinus = (firstPlusMinus == -1) ? i
								: firstPlusMinus;
						break;
					case '-':
						firstPlusMinus = (firstPlusMinus == -1) ? i
								: firstPlusMinus;
						break;
				}
			}// if closed
		}// for
		
		if (firstPower != -1) {
			return firstPower;
		}
		if (firstPlusMinus != -1) {
			return firstPlusMinus;
		}
		if (firstDivideTimes != -1) {
			return firstDivideTimes;
		}
		
		return -1;
		
	}// method
	
	private static String removeBracketSurround(String s) {
		if (s.charAt(0) == '(' && s.charAt(s.length() - 1) == ')') {
			return new String(s.substring(1, s.length() - 1));
		}
		return s;
	}
	
	protected static boolean isNumber(final String sString) {
		boolean b = false;
		final String zahlen = "0123456789";
		char c;
		for (int i = 0; i < sString.length(); i++) {
			c = sString.charAt(i);
			
			if (zahlen.indexOf(c) == -1) {
				b = false;
				break;
			} else {
				b = true;
			}
		}
		return b;
	}
	
}

Anbei der restliche Code.
 
Wow, ein recht ehrgeiziges Vorhaben, nach einem halben Jahr Erfahrung, aber durchaus umsetzbar.
Dein Problem besteht grob aus 3 Teilen.
Zunächst musst du eine geeignete Datenstruktur finden, auf der man Lösungsalgorithmen einfach anwenden kann. Danach einen parser schreiben, der den eingabestring in die datenstruktur übersetzt und letztendlich noch die Lösungsalgorithmen entwerfen.

Als Datenstruktur geht denk ich ne Klasse Equation, welche wiederum 2 Terme referenziert (links und rechts). Ein Term sollte ne abstrakte Klasse sein, von denen sich diverse n-stellige Operatoren ableiten (z.B. Constant, Variable, Sum, Product, Power, Sin, Cos, ...) und n member vom typ Term haben,. Terme sind also DAG's.

Für Term könnten folgende Methoden sinnvoll sein:
bool equivalent(Term*),
void applyOperator(SingleParameterOperator*),
virtual bool isConstant(),
virtual T calculate(),
virtual Term* removeConstantPart(),
virtual Term* removeVariablePart(),
virtual Term* simplify().

Der Lösungsalgorithmus müsste dann dafür sorgen, das nur der Linke Term isConstant() == true ist (die methode soll feststellen, ob der Term keine Variable enthält, indem er den DAG traversiert). Anfangs ist das natürich nicht so. Also rufst du links extractConstantPart() auf diese Methode liefert dir dann einen einstelligen operator, oder NULL, wenn es nicht möglich ist. Dieser operator muss die konstanten in dem term eliminieren. Du wendest ihn also auf beide terme der gleichung an (applyOperator()).
Das gleiche machst du für die andere seite mit den Variablen. Nun wirst du feststellen, dass es nicht immer ganz einfach ist diesen Operator zu finden. Um das zu erleichtern gibt es die Methode simplify(). Diese soll den term vereinfachen (zum beispiel bei einer summe dafür sorgen einen eqivalenten term finden, bei dem einer der summanden keine variablen enthält) damit der algorithmus in extract es immer mit dem trivialfall zu tun hat.

Ich denke die umsetzung dieses konzeptes ist für gleichungen, die nur aus summen und produkten bestehen noch relativ einfach und es lässt sich durch den rekursiven Ansatz sogar bishin zu komplexer Lösungslogik erweitern.
Das war jetzt nur mal nen kurzes brainstorming, ich hab sowas noch nie implementiert und weiss nicht, wie weit man wirklich damit kommt. Wär nett, wenn hier ne kleine diskussion darüber entsteht

Alternativ könntest du mal schaun, ob du offenen source für das problem fndest, bei dem du abgucken kannst.
 
Original von ArnoNühm

Alternativ könntest du mal schaun, ob du offenen source für das problem fndest, bei dem du abgucken kannst.
Zum Vergrößern anklicken....

Die solve()-Funktion von maxima wäre evtl. ein Ansatzpunkt, wenn auch wahrscheinlich ein Overkill für die einfachen Beispiele.
 
Servus,
sorry dass ich mich so lange nicht gemeldet hab, hatte aber in der schule einigen stress und dass geht momentan vor. Nicht dass ihr denk ich hab jetzt angefangen und dann fällt das ganze ins wasser.
Also erst mal danke ihr habt mir schon geholfen
Iich hab mir nun mal ein paar gedanken/ entwürfe gemacht und hab nun noch ein paar fragen.
Zu dem parser, Ich habe mir gedacht dass die eingabe in einen cstring (char array) eingelesen wird und dass dann zeichen für zeichen überprüft wird wie damit vorzugehen ist. (Ist das jetzt schon ein parser oder versteh ich da was falsch? ) Danach wollte ich das alles in einen 2 dimensionalen cstring gespeichert wird? was haltet ihr davon? Habt ihr vllt bessere ideen, wäre sehr dankbar. Aber Objekt Orientiert ist das ja nicht. Komme mit den ideen von ArnoNühm noch nicht ganz mit. Nochmal zu der Datenstruktur wie könnte ich das ganze denn noch gestalten? Ich habe mir auch überlegt vllt verschiedene strukturen zu schreiben welche den Datentypen enthält Bsp: die struktur variable enthält eine zahl (die zahl vor x ) und eben x. also z.b. 2 und x = 2x ( 2 * x ). Hab mir das ganze zwar nicht ganz so schwer vorgestellt aber ich denke mit etwas zeit und eurer hilfe schaff ich das schon. Soll auch ein längeres Projekt werden.

Gruß Virus
 
Danke für den Link, jedoch würde ich den parser gerne selber schreiben (soll ja mein c++ verbessern ).
Habt ihr vllt sonst noch irgendwelche ideen zu meinen fragen?
Oder vllt Beispiele/tipps wie man einen parser schreiben könnte.

Gruß Virus
 
Ich bin kein parserexperte (gibt zuhauf dicke bücher über das thema), aber nen paar kleine tips kann ich dir geben. einfache Mathematische Gelichungen sind ja zum Glück nicht sonderlich komplex.

Allgemein arbeiten einfache parser in 2 schritten:
Zuerst wird eine lexikalische analyse durchgeführt, welche die eingabe in tokens zerlegt (ein token ist dann sowas wie eine klammer, eine zahl, eine variable, ein operator, ...). am besten du schreibst die dinger dann in einen vector aus tokens.
Danach solltest du diese TokenListe zu einen Baum machen.
z.B.
Code: 
                                            =
                                  /                     \
                                2                       +
                                                 /              \
                                               x                3

Damit hast du die Daten in einem Format, worauf du dann arbeiten kannst und die Gleichung lösen kannst.
 
Servus, nochmal danke für deine hilfe würd warscheinlich ohne dich nicht weit kommen.

Also ich hab das ganze jetzt so weit dass ich eine Gleichung eingebe, diese wird dann so geparst dass sie in einem 2 dimensionalen array landet bsp: 2x+4=10
wird zu
array[1][ ] = 2x
array[2][ ] = +
array[3][ ] = 4
array[4][ ] = =
array[5][ ] = 10

Du hast gesagt ich solle das ganze in einen Baum zerlegen jedoch kapiere ich nicht wie darauf einen Lösungsalgorithmus anweden soll? Und wie dieser aufgebaut sein soll? Jedoch funktioniert dass so wie es jetzt aussieht auch nicht wirklich gut. Habe mir überlegt ich könnt zusätzlich in eine Variable die Form schreiben und dann anhand dieser verschiedene Funktionen auf die Gleichung ( so wie sie jetzt ist, im array ) anzuwenden( Bsp: aus 2x, x machen indem man auf beiden seiten durch 2 teilt). Ist das vllt einfacher möglich denn so wird es schon ein ziemlich schwieriges unterfangen. Oder könntet ihr mir einen kleinen Ansatz für einen Lösungsalgorithmus geben, wenn ich weiß wie anfangen soll bring ich das schon hin.
gruß Virus
 
Bevor du irgendwie anfängst, überlege bitte zuerst, was _genau_ du für Gleichen du lösen willst. Also _welche_ Operatoren dürfen vorkommen, wieviele Verschiedene Variablen, dürfen auch Klammern gesetzt werden usw.
Wenn du damit fertig bist, kann man anfangen hier vernünftige Lösungsvorschläge und Ansätze zu posten, aber ohne konkretes Ziel wird das nichts. Wie man allgemein an die Sache herangehen kann, wurde ja nun schon oft genug beschrieben.
 
@valenterry hab ich mir schon überlegt also es sind nur gleichungen mit den rechenzeichen +, -, *, /. Klammer sollen keine Gesetzt werden. Und variablen auch nur eine. Dazu wie man allgemein herangehen soll, ich habe mir ya überlegt wie ich vorgehen könnte jedoch frage ich euch ob es vllt einfacher möglich wäre. Da es so wie ich es oben beschrieben habe recht schwierig zu verwirklichen wäre.
Bin auf dem gebiet halt noch nicht so erfahren. sry

mfg virus
 
Gut, die wenigen Operationen machen die Sache einfach. Du hast ja nun schon ein Array mit allen Operatoren und Operanden. Nun gehst du dieses Array durch und guckst, ob du an irgendeiner Stelle erst einen Operanden hast, der nicht die Variable ist (also einfach eine Zahl), danach einen * oder / Operater und dann wieder einen Operanden, der keine Variable ist.
Also z.B. soetwas 4 * 6 oder soetwas: 2.5 / 3
Falls du soetwas findest, rechnest du das Erebnis aus und ersetzt die ursprünglichen drei Arraywerte mit dem neuen. Das machst du zuerst solange für * und / bis es diesen Fall nicht mehr gibt und dann solange mit + und - bis es diesen Fall nicht mehr gibt.

Dann hast du soetwas: 5 * x + 3 = 6

Nun überprüfst du, auf welcher Seite der Gleichung die Variable ist und bringst alle Zahlen, die mit der Variable nicht durch * oder / verknüpft sind auf die andere Seite.

Danach hast du also soetwas: 5 * x = 3

Als letztes teilst du durch den Faktor vor der Variablen. Das was dann auf der anderen Seite noch steht, ist der Wert der Variablen.
 
Quereinsteiger^^

Hallo,

ich habe das erstmal mit " 4*4 " versucht. Den Array nach dem Zeichen durchsuchen ist ja kein Problem und dann die Operanden herauszubekommen auch nicht. Doch es gibt einen Harken:P
Code: 
cout << static_cast<int>(4)<< endl; // = 4
cout << static_cast<char>(52)<<endl;// = 4

Leider habe ich nur das "char 4" und weiß nun nicht weiter wie ich an die 4 komme, die nicht den int oder char-Wert 52 hat;) Denn wenn ich rechne, rechne ich mit 52 anstatt mit 4, (der string besteht ja aus chars und nicht aus int)^^

Hoffe Ihr könnt mir helfen. Denn wenn ich weiß wie das geht, will ich auch den Gleichungslöser coden:)
 
Dafür gibt es die Funktion int atoi (char *) aus der C Standard-Library. Die Funktion nimmt ein Array aus Zeichen, also einen String, als Argument und gibt den Zahlenwert, den diese repräsentiert zurück, zum Beispiel so:

atoi("123") = 123
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben