Discussion :

[InitSreen]

Bonjour,

Est-ce qu'il existe un algorithme type pour résoudre une expression numérique sous forme de chaîne de caractères en respectant la précédence des opérateurs. Le but est d'interpréter cette chaîne comme une expression numérique et donc d'obtenir son résultat.

[BufferBob]

salut,

tout dépend de la complexité de l'expression j'imagine, s'il y a des parenthèses ou non par exemple etc.

à mon sens plus qu'un algorithme c'est un parseur qu'il te faut de manière générale, et définir la grammaire d'une expression numérique, la syntaxe BNF de ce genre de chose est assez simple
un exemple concret de ce que tu veux faire en python avec pyparsing : http://pyparsing.wikispaces.com/file/view/SimpleCalc.py

en espérant que ça aide,

[Flodelarab]

Bonjour,

Bonjour,

Est-ce qu'il existe un algorithme type pour résoudre une expression numérique sous forme de chaîne de caractères en respectant la précédence des opérateurs. Le but est d'interpréter cette chaîne comme une expression numérique et donc d'obtenir son résultat.

Si tu utilises la notation polonaise inversée, l'algorithme tombe tout cuit dans la bouche!

[kolodz]

En fonction du langage, il t'est possible d'avoir une interprétation d'une chaine de caractères.

Par exemple avec Java :

Code Java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
 
public class TestDeveloppez {
	public static void main(String[] args) throws Exception {
		ScriptEngineManager mgr = new ScriptEngineManager();
		ScriptEngine engine = mgr.getEngineByName("JavaScript");
		String foo = "40+(2*10)";
		System.out.println(engine.eval(foo));
	}
}

Dans ce cas, on interpréter l'équation comme étant du JavaScript, qui inclus tout ce qu'il faut pour faire le calcul.

Il en va de même pour PHP :

Code PHP :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
$expression = '40+(2*10)';
eval( '$result = (' . $expression . ');' );
echo $result;

Ici, c'est la fonction eval qui est utilisé.

Il est très probable que le langage que tu cherche à utiliser dispose déjà d’interpréteur gérant l'ensemble des opérations mathématique. Il est très peu intéressant de refaire cette partie à la main. Car, cela implique en grande partie la théorie des langages et la redéfinition d'un langage et d'utilisation d'un parseur.
Donc même si tu refait cette partie, il est très probable que tu te base sur un parseur pré-existant (Exemple JFlex) et que tu ne réalise que les règles lexicals et le traitement associé. Là encore, tout a déjà été fait plusieurs fois ! Donc à reprendre de ce qui existe déjà sauf si tu réalise ton propre langage mathématique.

Cordialement,
Patrick Kolodziejczyk.

Source :
http://de.php.net/manual/en/function.eval.php
http://jflex.de/manual.html#LexRules

[InitSreen]

Merci pour vos réponse, je pense que la notation polonaise inversé est la plus adapté à mon problème étant donné que je dois le faire en C.

[kolodz]

A re-coder, je serai partie sur l’algorithme Shunting-yard. Mais bon pas comme si cela n'existait pas déjà ici ou là.

C'est le genre d'algorithme que si tu le code et que ce n'est pas dans un but d'apprentissage, c'est que tu fait quelque chose de faux. Je dis ça, mais je travail sur une application qui implémente sont propre Shunting-yard, mais elle a une excuse... Elle a plus de 20 ans !

Cordialement,
Patrick Kolodziejczyk.

source :
http://en.wikipedia.org/wiki/Shunting-yard_algorithm
http://rosettacode.org/wiki/Parsing/...yard_algorithm
http://en.literateprograms.org/Shunt...orithm_%28C%29

Edit : La partie "token" de l'algorithme vient de la théorie des langages !

[InitSreen]

L’algorithme Shunting-yard revient à peu près à faire une NPI mais avec une entrée et une sortie. Et non c'est pas dans un but d'apprentissage, mais je pense que ça correspond à ce que je recherche. Je vais faire une première lecture de la chaîne et disposer les jetons en fonction de la précédence puis calculer un résultat en sortie. ça règle les problèmes qui se posent, l'optimisation viendra dans un second temps.

[ChMeessen]

L'algorithme de Pratt est le plus simple et le plus efficace pour évaluer une expression.
Voici un excellent article présentant un exemple écrit en python.
https://eli.thegreenplace.net/2010/0...edence-parsing
Il est d'une remarquable simplicité et concision.