Résoudre l'équation de la chaîne de résultat en C

Question

Je voudrais savoir si quelqu'un a des infos ou de l'expérience sur la façon de faire quelque chose qui semble simple, mais ne ressemble pas en essayant de programmer. L'idée est: donner une chaîne contenant une équation, par exemple: « 2 * x = 10 » par exemple (ce qui est simple, mais il pourrait être très complexe, comme sqrt (54) * 35 = x ^ 2, et ainsi sur ....) et le programme retournerait x = 5 et peut-être donner un journal de la façon dont il est arrivé là.

Est-ce faisable? Si oui, est-ce que quelqu'un a une avance? Pour info il y a ce site ( http://www.numberempire.com/equationsolver.php ) qui fait la même chose en PHP, mais pas open source.

Merci pour toute aide!

Answer 1

On appelle « l'analyse », et bien que la science informatique a déjà résolu ce problème, il est pas simple du tout jusqu'à ce que vous le comprenez bien. Il y a toute une discipline informatique qui décrit comment résoudre ce problème. En C, vous devez définir la grammaire de votre entrée (éventuellement avec les règles de priorité en elle), puis effectuer analyse lexicale sur votre entrée, puis parse le résultat et enfin évaluer votre analyse syntaxique arbre.

Dans les langues telles que Ruby, cependant, parce que vous avez un tel soutien complet pour la manipulation de chaînes et parce que vous avez un tel pouvoir d'exécution énorme, vous pouvez résoudre votre problème avec une seule ligne de code comme ceci:

puts(eval($_)) while gets

Oui, qui couvrira plus de ce que vous demandez.

Answer 2

Tout d'abord vous devez bien définir quels types d'équations vous pouvez avoir une entrée. Ensuite, vous devez créer une bonne abstraction pour représenter l'équation, par exemple une classe polynomiale. Si vous voulez utiliser l'expression plus complexe, optez pour un arbre pour les expressions numériques. Parsing peut être assez facile si vous avez de bonnes règles pour convertir l'expression en notation préfixe, alors l'évaluation est facile à l'aide de piles. Une fois que vous avez des arbres artithmetic ou polynômes, vous pouvez mettre en œuvre des transformations pour calculer la variable (s).

Answer 3

Si les équations ne se complexe, il ne sera sûrement pas quelques lignes de code de C / C.

Pour les équations linéaires, vous devez simuler l'une des méthodes décrites dans l'algèbre linéaire Livres. Le code de qui est assez petit.

Answer 4

Vous pouvez essayer de relier à sympy à votre C (ou C ++) le code et l'utiliser pour résoudre vos équations.

IIRC, sympy a ce genre de fonctionnalité. De plus, il devrait être plus facile de manipuler la chaîne d'entrée à une équation utilisable à l'intérieur de Python, puis le faire passer à sympy pour la résolution.

Answer 5

Il va être deux parties à votre problème: analyse syntaxique l'équation (s), et de les résoudre symboliquement. Je ne vais pas dire grand-chose sur la première, étant donné que d'autres réponses ont déjà couvert ce sujet bien; ma recommandation personnelle serait d'écrire un analyseur simple descente récursive pour les expressions en notation préfixe.

La deuxième partie, la résolution des équations analytiquement, va être délicat. D'une manière générale, il existe des classes spéciales d'équations pour lesquelles les méthodes standards existent pour trouver une solution analytique:

• Systèmes d'équations linéaires: tout solveur linéaire directe. Si vous voulez montrer les étapes explicitement et le nombre d'équations / inconnues est faible, je vous recommande simple quelque chose comme l'élimination gaussienne ou non pivotée règle de Cramer.
• Système d'équations polynomiales: équivalent, après substitution de variables, à la recherche de racines de polynômes simples. Si ceux-ci ont un degré <= 4, il existe des formules pour les solutions exactes. NB: Pour le degré 3 et 4 ces formules ne sont pas agréables
.
• des solutions rationnelles à un système d'équations polynomiales avec coefficient rationnel: Do substitution de variables comme ci-dessus. Puis la force brute à l'aide du test de zéro rationnel.
• D'autres types d'équations: Bonne chance. Pour plus complexes [systèmes de] équations non linéaires, si vous pouvez régler des solutions numériques (non analytiques), regard sur la méthode de Newton.

Answer 6

Une correction: ce n'est pas l'algèbre linéaire, ce qui signifie généralement matricies de multiples équations et inconnues

.

Votre exemple est certainement pas complexe.

Qu'est-ce que vous avez besoin est une grammaire d'expression simple et analyseur. Parse l'équation dans un arbre de syntaxe abstraite et parcourir l'arborescence pour l'évaluer.

Si vous écriviez Java, il pourrait ressembler à cette . Un autre exemple est symja . Peut-être que ce sera assez d'inspiration pour vous de venir avec votre propre C ++.

Vous pouvez également regarder dans Mathematica et Alpha Wolfram. Stephen Wolfram est l'un des meilleurs mathématiciens et des informaticiens du monde. Il a beaucoup de choses que vous pouvez réutiliser à bon escient plutôt que de l'écrire vous-même.

Vous devrez définir ce que vous entendez par « résoudre » et ce que vous attendez d'avoir de retour.

Il existe des solutions symboliques et des solutions numériques. Lequel voulez-vous dire? Les deux sont tout aussi valables, mais ils sont différents. Vous appliquez différentes techniques en fonction de votre réponse.

Un autre point: il existe de nombreuses techniques pour « résoudre » les équations qui dépendent beaucoup du type d'équation. Si vous me donnez quelque chose comme f(x) = 0 Je pense que des algorithmes de recherche des racines comme la méthode de Newton. Si vous me donnez une méthode équation différentielle ordinaire que je pourrais essayer une substitution ou l'intégration numérique à l'aide Runge-Kutta. Si vous me donnez une équation différentielle partielle je peux appliquer des différences finies, éléments finis, ou des techniques d'éléments de frontière. (Ne me lancez pas sur elliptique, parabolique et systèmes hyperboliques.)

Le point est que votre question est très générique, et la réponse dépend beaucoup de ce que vous essayez de faire. Plus de détails pourrait aider.

Answer 7

En général, vous devrez analyser l'expression dans une représentation interne. De nombreux livres d'algèbre linéaire (matrices suggèrent d'utiliser ou std::vector) pour représenter les coefficients. L'exposant du terme est défini par sa position dans le vecteur.

Ainsi, par exemple, l'expression:

 2 + 3x + 5x^2

peut être représenté sous la forme d'un tableau ou std::vector:

std::vector<int> expression;
expression[0] = 2; // 2 * x ^ 0
expression[1] = 3;
expression[2] = 5;

L'écriture d'une fonction d'évaluation devient trivial, et à gauche comme un exercice pour le lecteur.

Résolution des équations multiples devient plus complexe. Il existe des bibliothèques existantes et des algorithmes pour cela. Une recherche Google devrait trouver une bonne chose. : -)

Je suggère de commencer avec des termes simples et la construction d'un analyseur pour cela. Une fois que les travaux, vous pouvez modifier l'analyseur pour accepter les noms de fonctions aussi bien.

Si vous essayez de simplifier une expression qui a des termes des deux côtés de la =, il suffit d'écrire les étapes qui vous normalement prendre pour résoudre manuellement. Essayez quelques équations différentes pour obtenir des règles vers le bas. Maintenant, mettre en œuvre ces règles en C ++.