Associer l'expression mathématique à l'expression régulière?

Par exemple, ceux-ci sont valides des expressions mathématiques:

a * b + c
-a * (b / 1.50)
(apple + (-0.5)) * (boy - 1)

et ce sont des expressions mathématiques invalides:

--a *+ b @ 1.5.0  // two consecutive signs, two consecutive operators, invalid operator, invalid number
-a * b + 1)  // unmatched parentheses
a) * (b + c) / (d  // unmatched parentheses

Je n'ai aucun problème avec les nombres flottants correspondants, mais j'ai des difficultés avec les parenthèses correspondant. Une idée? S'il y a une meilleure solution que l'expression régulière, j'accepterai aussi. Mais le regex est préférable.

========

Edit:

je veux faire quelques commentaires sur mon choix de la "réponse acceptée", en espérant que les gens qui ont la même question et trouvent ce fil ne seront pas induits en erreur.

il y a plusieurs réponses que je considère comme "acceptées", mais je n'ai aucune idée de laquelle est la meilleure. J'ai donc choisi la réponse acceptée (presque) au hasard. Je recommande la lecture de la réponse de Guillaume Malartre ainsi que la réponse acceptée. Tous apportent des solutions pratiques à ma question. Pour une réponse quelque peu rigoureuse/théorique, veuillez lire les commentaires de David Thornley sous la réponse acceptée. Comme il a mentionné, L'extension de Perl à l'expression régulière (provenant du langage régulier) la rend "irrégulière". (Je n'ai pas mentionné de langage dans ma question, donc la plupart des répondants ont supposé la mise en œuvre Perl de l'expression régulière – probablement la mise en œuvre la plus populaire. Moi aussi quand j'ai posté ma question.)

s'il vous plaît, corrigez-moi si j'ai dit quelque chose de mal ci-dessus.

17
demandé sur user187291 2010-04-07 23:23:10

8 réponses

voici un script Perl qui va analyser arbitrairement deep matching parens. Bien qu'il va jeter les parens non-appariés à l'Extérieur, Je ne l'ai pas conçu spécifiquement pour valider les parens. Il parsèmera arbitrairement parens profonds tant qu'ils sont équilibrés. Cela vous permettra toutefois de commencer.

la clé est la récursion à la fois dans le regex et l'utilisation de celui-ci. Jouer avec elle, et je suis sûr que vous pouvez obtenir ce non correspondance prens. Je pense que si vous capturez ce que ce regex jette et comptez parens (c'est-à-dire test pour parens impairs dans le texte de non-match), Vous avez parens invalides et déséquilibrés.

#!/usr/bin/perl
$re = qr  /
     (                      # start capture buffer 1
        \(                  #   match an opening paren
        (                   # capture buffer 2
        (?:                 #   match one of:
            (?>             #     don't backtrack over the inside of this group
                [^()]+    #       one or more 
            )               #     end non backtracking group
        |                   #     ... or ...
            (?1)            #     recurse to opening 1 and try it again
        )*                  #   0 or more times.
        )                   # end of buffer 2
        \)                  #   match a closing paren
     )                      # end capture buffer one
    /x;


sub strip {
    my ($str) = @_;
    while ($str=~/$re/g) {
        $match=; $striped=;
        print "$match\n";
        strip($striped) if $striped=~/\(/;
        return $striped;
    }
}

while(<DATA>) {
    print "start pattern: $_";
    while (/$re/g) { 
        strip() ;
    }
}   

__DATA__
"(apple + (-0.5)) * (boy - 1)"
"((((one)two)three)four)x(one(two(three(four))))"
"a) * (b + c) / (d"
"-a * (b / 1.50)"

Sortie:

start pattern: "(apple + (-0.5)) * (boy - 1)"
(apple + (-0.5))
(-0.5)
(boy - 1)
start pattern: "((((one)two)three)four)x(one(two(three(four))))"
((((one)two)three)four)
(((one)two)three)
((one)two)
(one)
(one(two(three(four))))
(two(three(four)))
(three(four))
(four)
start pattern: "a) * (b + c) / (d"
(b + c)
start pattern: "-a * (b / 1.50)"
(b / 1.50)
4
répondu dawg 2010-04-07 19:47:45

Utiliser un automate à pile pour la mise en correspondance paranthesis http://en.wikipedia.org/wiki/Pushdown_automaton (ou tout simplement une pile ;-) )

détails pour la solution stack:

while (chr available)
    if chr == '(' then
      push '('
    else
      if chr == ')' then
        if stack.elements == 0 then
          print('too many or misplaced )')
          exit
        else
          pop //from stack
end while
if (stack.elements != 0)
  print('too many or misplaced(')

même simple: il suffit de garder un compteur au lieu de la pile.

8
répondu Victor Hurdugaci 2010-04-07 19:36:22

les expressions régulières ne peuvent être utilisées que pour reconnaître les langues régulières. Le langage des expressions mathématiques n'est pas régulier; vous aurez besoin de mettre en œuvre un analyseur réel (par exemple LR) pour le faire.

8
répondu Rob Lachlan 2017-02-11 19:57:00

je crois que vous serez mieux à mettre en place un vrai analyseur pour accomplir ce que vous êtes après.

un analyseur pour les expressions mathématiques simples est "Parsing 101", et il y a plusieurs exemples à trouver en ligne.

voici Quelques exemples:

notez que la grammaire dont vous aurez besoin pour valider les expressions est plus simple que les exemples ci-dessus, puisque les exemples implémentent également l'évaluation de l'expression.

5
répondu codeape 2010-04-07 21:56:24

vous ne pouvez pas utiliser regex pour faire des choses comme la parenthèse d'équilibre.

3
répondu Eric H. 2010-04-07 19:24:16

c'est délicat avec une seule expression régulière, mais assez facile en utilisant une approche mixte regexp/procédurale. L'idée est de construire un regexp pour l'expression simple (sans parenthèses) et ensuite de remplacer à plusieurs reprises ( simple-expression ) avec certains atomique de la chaîne (par exemple, l'identificateur). Si l'expression réduite finale correspond au même modèle' simple', l'expression originale est considérée comme valide.

Illustration (en php).

function check_syntax($str) {

    // define the grammar
    $number = "\d+(\.\d+)?";
    $ident  = "[a-z]\w*";
    $atom   = "[+-]?($number|$ident)";
    $op     = "[+*/-]";
    $sexpr  = "$atom($op$atom)*"; // simple expression

    // step1. remove whitespace
    $str = preg_replace('~\s+~', '', $str);

    // step2. repeatedly replace parenthetic expressions with 'x'
    $par = "~\($sexpr\)~";
    while(preg_match($par, $str))
        $str = preg_replace($par, 'x', $str);

    // step3. no more parens, the string must be simple expression
    return preg_match("~^$sexpr$~", $str);
}


$tests = array(
    "a * b + c",
    "-a * (b / 1.50)",
    "(apple + (-0.5)) * (boy - 1)",
    "--a *+ b @ 1.5.0",
    "-a * b + 1)",
    "a) * (b + c) / (d",
);

foreach($tests as $t)
    echo $t, "=", check_syntax($t) ? "ok" : "nope", "\n";

ce qui précède ne valide que la syntaxe, mais la même technique peut être utilisée pour construire un vrai analyseur.

3
répondu user187291 2010-04-07 22:33:43

pour la correspondance des parenthèses, et la mise en œuvre d'autres règles de validation des expressions, il est probablement plus facile d'écrire votre propre petit analyseur. Les expressions régulières ne sont pas bonnes dans ce genre de situation.

1
répondu Eric Eijkelenboom 2010-04-07 19:26:14

Ok voici ma version de la recherche de la parenthèse dans ActionScript3, en utilisant cette approche donner beaucoup de traction pour analyser la partie avant la parenthèse, à l'intérieur de la parenthèse et après la parenthèse, si une parenthèse reste à la fin vous pouvez soulever un avertissement ou refuser d'Envoyer à une fonction eval finale.

package {
import flash.display.Sprite;
import mx.utils.StringUtil;
public class Stackoverflow_As3RegexpExample extends Sprite
{
    private var tokenChain:String = "2+(3-4*(4/6))-9(82+-21)"
    //Constructor
    public function Stackoverflow_As3RegexpExample() {
        // remove the "\" that just escape the following "\" if you want to test outside of flash compiler.
        var getGroup:RegExp = new RegExp("((?:[^\(\)]+)?)   (?:\()       (  (?:[^\(\)]+)? )    (?:\))        ((?:[^\(\)]+)?)", "ix")   //removed g flag
        while (true) {
            tokenChain = replace(tokenChain,getGroup)
            if (tokenChain.search(getGroup) == -1) break; 
        }
        trace("cummulativeEvaluable="+cummulativeEvaluable)
    }
    private var cummulativeEvaluable:Array = new Array()
    protected function analyseGrammar(matchedSubstring:String, capturedMatch1:String, capturedMatch2:String,  capturedMatch3:String, index:int, str:String):String {
        trace("\nanalyseGrammar str:\t\t\t\t'"+str+"'")
        trace("analyseGrammar matchedSubstring:'"+matchedSubstring+"'")
        trace("analyseGrammar capturedMatchs:\t'"+capturedMatch1+"'  '("+capturedMatch2+")'   '"+capturedMatch3+"'")
        trace("analyseGrammar index:\t\t\t'"+index+"'") 
        var blank:String = buildBlank(matchedSubstring.length)
        cummulativeEvaluable.push(StringUtil.trim(matchedSubstring))
        // I could do soo much rigth here!
        return str.substr(0,index)+blank+str.substr(index+matchedSubstring.length,str.length-1)
    }
    private function replace(str:String,regExp:RegExp):String {
        var result:Object = regExp.exec(str)
        if (result)
            return analyseGrammar.apply(null,objectToArray(result)) 
        return str
    }
    private function objectToArray(value:Object):Array {
        var array:Array = new Array()
        var i:int = 0
        while (true) {
            if (value.hasOwnProperty(i.toString())) {
                array.push(value[i])
            } else {
                break;
            }
            i++
        }
        array.push(value.index)
        array.push(value.input)
        return array
    }
    protected function buildBlank(length:uint):String {
        var blank:String = ""
        while (blank.length != length)
            blank = blank+" "
        return blank
    }
}

}

Il devrait suivre ceci:

analyseGrammar str:             '2+(3-4*(4/6))-9(82+-21)'
analyseGrammar matchedSubstring:'3-4*(4/6)'
analyseGrammar capturedMatchs:  '3-4*'  '(4/6)'   ''
analyseGrammar index:           '3'

analyseGrammar str:             '2+(         )-9(82+-21)'
analyseGrammar matchedSubstring:'2+(         )-9'
analyseGrammar capturedMatchs:  '2+'  '(         )'   '-9'
analyseGrammar index:           '0'

analyseGrammar str:             '               (82+-21)'
analyseGrammar matchedSubstring:'               (82+-21)'
analyseGrammar capturedMatchs:  '               '  '(82+-21)'   ''
analyseGrammar index:           '0'
cummulativeEvaluable=3-4*(4/6),2+(         )-9,(82+-21)
1
répondu Guillaume Malartre 2010-04-07 22:43:18