Analyser une expression Scala
Scala n'est pas un langage très couramment utilisé ici. La plupart de ceux qui le connaissent l'aiment [la citation nécessaire] , mais certains y vont :\quand ils rencontrent ses opérateurs définis par l'utilisateur, disant qu'ils sont trop compliqués.
Cependant, ils sont régis par un ensemble de règles très simples, décrites ici . Leur priorité dépend du premier caractère. Voici la liste pour cela (priorité la plus élevée à la plus basse):
* / %
+ -
:
= !
< >
&
^
|
(all letters)
Donc ça
a + b ^? c less a ==> b | c
serait le même que ça
((a + b) ^? c) less ((a ==> b) | c)
Votre tâche consiste à transformer une telle expression (uniquement les applications infixées) en une structure arborescente ou une chaîne avec toutes les sous-expressions entre parenthèses.
Contribution
Une chaîne ou plusieurs caractères donnés en argument à une fonction, lus à partir de STDIN, donnés comme arguments de ligne de commande ou en utilisant l'une des autres méthodes d'entrée par défaut . Cette chaîne est l'expression à analyser.
Production
Vous pouvez effectuer l'une des opérations suivantes, imprimées sur STDOUT, renvoyées par une fonction ou l'une des autres méthodes de sortie par défaut :
- La même chaîne mais avec des parenthèses en dehors de chaque sous-expression (l'expression la plus externe peut ou non être entre parenthèses). Par exemple,
expr op expr2 op2 expr3->(expr op expr2) op2 expr3. Si vous le souhaitez, vous pouvez également mettre entre parenthèses les atomes ((((expr) op (expr2)) op2 (expr3))) - Une liste multidimensionnelle, où chaque expression serait divisée en l'argument de gauche, l'opérateur / méthode et l'argument de droite. Par exemple,
expr op expr2 op2 expr3->[['expr','op','expr2'],'op2','expr3'] - Une structure arborescente équivalente aux 2 représentations ci-dessus. Vous avez eu l'idée.
Règles
- Tous les opérateurs utilisés sont binaires, infixes et associatifs à gauche.
- L'analyse va de gauche à droite.
- Il y aura toujours un ou plusieurs espaces entre les arguments et les opérateurs.
- Les opérateurs peuvent être constitués de l'un des symboles mentionnés ci-dessus (
*/%+-:=!<>&^|) et de lettres majuscules ou minuscules ([A-Za-z]). Ce seront un ou plusieurs personnages. - Les arguments des méthodes peuvent être d'autres expressions ou des identificateurs alphabétiques (
[A-Za-z]). - C'est du code-golf , donc le code le plus court gagne!
Cas de test
Plus à venir bientôt
Input -> Output
a -- blah /\ foo -> a -- (blah /\ foo)
same ** fst *^ chr *& operators -> ((same ** fst) *^ chr) *& operators
Lots Of SpAceS // here -> Lots Of (SpAceS // here)
Not : confusing * At / ALL iS it -> (Not : ((confusing * At) / ALL)) iS it
This *isnot* valid ** Scala -> (This *isnot* valid) ** Scala
Réponses
Gelée , 59 octets
Ḳ¹ƇµḊm2ZḢeⱮ€ØẠṭ“*/%“+-“:“=!“<>“&“^“|”¤i€1ỤḢḤ+-,2œṖ⁸W€2¦ẎµÐL
Un lien monadique acceptant une liste de caractères qui produit une liste contenant l'expression entre crochets sous forme de listes imbriquées [expr, op, expr]où expret opsont des listes de caractères.
Essayez-le en ligne!
Comment?
Ḳ¹Ƈµ...µÐL - Link: list of characters, E
Ḳ - split at spaces
Ƈ - keep those which are truthy under:
¹ - identity (falsey for empty lists)
µ...µÐL - repeat the monadic link (below) until no change occurs
Ḋm2ZḢeⱮ€ØẠṭ“...”¤i€1ỤḢ - link, wrap three at highest precedence operator: list
Ḋ - deueue
m2 - mod-2 slice -> gets operators
Z - transpose
Ḣ - head -> first characters of operators
¤ - nilad followed by link(s) as a nilad:
ØẠ - letters "A..Za..z"
“...” - ["*/%","+-",":","=!","<>","&","^","|"]
ṭ - tack -> ["*/%","+-",":","=!","<>","&","^","|","A..Za..z"]
€ - for each (1st character):
Ɱ - map accross (the lists of characters) with:
e - exists in?
i€1 - first (1-based) index of 1 in each (0 if no 1 found)
Ụ - grade-up (list of 1-based indices sorted by value)
Ḣ - head
- continued below...
Ḥ+-,2œṖ⁸W€2¦Ẏ - ...continued
Ḥ - double -> index, I, of operator in original list
-,2 - [-1,2]
+ - add -> [I-1, I+2]
⁸ - chain's left argument, the list
œṖ - partition (the list) at indices ([I-1, I+2])
€2¦ - apply to the secod element (the [expr, op, expr])
W - wrap in a list
Ẏ - tighten
JavaScript (ES6), 180 ... 155 152 octets
Renvoie une liste multidimensionnelle. L'expression la plus externe est entre parenthèses, de même que les atomes.
f=(i,a=i.split(/ +/))=>"w | ^ & <> =! : +- */%".split` `.some(p=>a.map((s,j)=>i=!!s.match(`^[\\${p}]`)&j?j:i)|i)?[f(i=a.splice(i),a),i.shift(),f(a,i)]:a
Essayez-le en ligne!
Comment?
Il s'agit d'un algorithme récursif. À chaque itération, nous recherchons le dernier opérateur avec la priorité la plus faible , divisons l'expression à cette position et traitons les appels récursifs sur les deux parties résultantes. Nous arrêtons la récursion lorsque nous atteignons un atome.
Afin de diviser l'expression et d'isoler l'opérateur, nous utilisons une combinaison de splice()et shift()comme indiqué dans l'exemple suivant, où des entiers sont utilisés au lieu d'opérateurs et d'opérandes.
a = [ 0, 1, 2, 3, 4, 5, 6 ];
i = 3;
i = a.splice(i); // --> a[] = [ 0, 1, 2 ] (left expression)
// i[] = [ 3, 4, 5, 6 ] (operator + right expression)
i.shift(); // --> operator = 3
// i[] = [ 4, 5, 6 ] (right expression)
Commenté
f = ( // f is a recursive function taking:
i, // i = input string on the 1st iteration,
// and then some non-empty array
a = i.split(/ +/) // a[] = input string split on spaces
) => // NB: operators are expected at odd positions
"w | ^ & <> =! : +- */%" // this string describes the groups of operators,
// from lowest to highest precedence
.split` ` // split it
.some(p => // for each pattern p:
a.map((s, j) => // for each string s at position j in a[]:
i = // update i:
!!s.match( // see if s matches p; the '\' is required for
`^[\\${p}]` // 'w' and '^', and harmless for the other ones
) & j ? // if there's a match and j is odd:
j // update i to j
: // else:
i // leave i unchanged
) // end of map()
| i // make some() succeed if i is a number
) ? // end of some(); if successful:
[ // build a new array consisting of:
f( // the result of a recursive call ...
i = a.splice(i), a // ... with the left expression
), //
i.shift(), // followed by the operator
f( // followed by the result of a recursive call ...
a, i // ... with the right expression
) //
] // end of new array
: // else:
a // just return a[]
Rétine , 111 octets
,2,`\S+
{$&} ~(K`*/%¶-+¶:¶!=¶<>¶&¶\^¶|¶\w )L$`.+
+0`{([^{}]+)}( +[$&][^ {}]$* +){([^{}]+)}¶{($$1)$$2($$3)}
{|}
Essayez-le en ligne! Le lien comprend des cas de test et un pied de page supprimant les parenthèses. Explication:
,2,`\S+
{$&}
Enveloppez uniquement les variables entre accolades.
~(
)
Évaluez les étapes incluses et exécutez le résultat sous forme de script sur l'entrée encapsulée.
K`*/%¶-+¶:¶!=¶<>¶&¶\^¶|¶\w
Remplacez temporairement l'entrée par une liste de classes de caractères. Notez que - + en particulier est dans cet ordre en raison du fonctionnement des classes de caractères. Les classes de caractères sont répertoriées par ordre décroissant de priorité.
L$`.+
Faites une boucle sur chaque classe de caractères de la liste.
+0`{([^{}]+)}( +[$&][^ {}]$* +){([^{}]+)}¶{($$1)$$2($$3)}
Recherchez le premier opérateur commençant par cette classe, mettez ses paramètres entre parenthèses et mettez la sous-expression entre accolades.
{|}
Retirez les accolades maintenant englobantes.
Le code réellement généré ressemble à ceci:
+0`{([^{}]+)}( +[\w][^ {}]* +){([^{}]+)}
Faites correspondre un terme accolé, puis l'opérateur, puis un autre terme accolé.
{($1)$4($5)}
Mettez les termes des deux côtés de l'opérateur entre parenthèses et mettez la sous-expression entre accolades.
La version précédente de 126 octets acceptait tout caractère autre qu'un espace, une parenthèse ou un caractère opérateur précédemment défini comme opérateur de priorité la plus élevée:
.+
($&)
~(K`a-z¶|¶\^¶&¶<>¶!=¶:¶-+¶*/%¶^ ()
L$`.+ +0i`\(((([^ ()]+ +){2})$*[^ ()]+)( +[$&][^ ()]$* +)([^()]+)\)¶(($$1)$$4($$5))
Essayez-le en ligne! Le lien comprend des cas de test et un pied de page supprimant les parenthèses. Explication:
.+
($&)
Mettez toute l'expression entre parenthèses.
~(
Évaluez les étapes restantes et exécutez le résultat sous forme de script sur l'entrée encapsulée.
K`a-z¶|¶\^¶&¶<>¶!=¶:¶-+¶*/%¶^ ()
Remplacez temporairement l'entrée par une liste de classes de caractères. Notez que c'est -+en particulier dans cet ordre en raison du fonctionnement des classes de caractères. Les classes de caractères sont répertoriées par ordre de priorité croissant.
L$`.+
Faites une boucle sur chaque classe de caractères de la liste.
+0i`\(((([^ ()]+ +){2})$*[^ ()]+)( +[$&][^ ()]$* +)([^()]+)\)¶(($$1)$$4($$5))
Trouvez la plus grande sous-expression possible qui contient un opérateur commençant par cette classe et placez les deux arguments entre parenthèses.
Le code réellement généré ressemble à ceci:
+0i`\(((([^ ()]+ +){2})*[^ ()]+)( +[a-z][^ ()]* +)([^()]+)\)
Faites correspondre a (, puis un nombre pair de termes, puis un terme, puis l'opérateur, puis tous les termes restants, puis a ).
(($1)$4($5))
Mettez les termes des deux côtés de l'opérateur entre parenthèses.
Perl 5 , 292 149 137 octets
(12 derniers octets perdus avec le pourboire de Nahuel Fouilleul dans les commentaires ci-dessous)
sub{$_=pop;s/ +/ /g;for$o(qw(\*\/% +- : =! <> & \^ | \w)){1while s/\S+ +[$o]\S* +\S+/push@s,$&;"$#s,"/e}1while s/\d+,/($s[$&])/;/.(.*)./}
Essayez-le en ligne!
sub {
$_=pop; #put input string in $_ s/ +/ /g; #trim away unneeded spaces for $o ( #loop through operators
qw(\*\/% +- : =! <> & \^ | \w) #...in order of precedence
) {
1 while s/\S+\s+[$o]\S*\s+\S+ #find first such operator and /push@s,$&; "$#s," #replace its sub-expression with /ex #a tag of id plus comma #and continue until no more #of current operator } 1 while s/\d+,/($s[$&])/; #replace all tags with their
#subexpressions, now in parens
/.(.*)./ #remove first+last char, return rest
}
Charbon , 82 68 67 octets
≔⮌Φ⪪Ｓ ιθＦ⪪⁺“ ∨μ[Ek✂◧‽_U⁹�A\”α.«Ｗ⊖Ｌθ¿№ι↥§§θ⊖κ⁰⊞θＥ³⊟θＦ²⊞υ⊟θＷυ⊞θ⊟υ»⭆θι
Essayez-le en ligne! Le lien est vers la version verbeuse du code. Génère la représentation Python d'une liste imbriquée. Explication:
≔⮌Φ⪪Ｓ ιθ
Divisez la chaîne d'entrée sur des espaces et filtrez les chaînes vides (correspondant à des séries d'espaces). Inversez le résultat afin que la liste puisse être traitée en extrayant des termes.
Ｆ⪪⁺“ ∨μ[Ek✂◧‽_U⁹�A\”α.«
Concaténez la chaîne littérale compressée */%.-+.:.!=.<>.&.^.|.avec l'alphabet majuscule, divisez en .s et bouclez sur chaque classe de caractères.
Ｗ⊖Ｌθ
Tant qu'il reste des opérateurs à traiter:
¿№ι↥§§θ⊖κ⁰
L'opérateur actuel en majuscules commence-t-il par un caractère de la classe actuelle?
⊞θＥ³⊟θ
Si tel est le cas, extrayez l'opérateur et ses paramètres dans leur propre sous-liste, puis repoussez cette liste en tant que paramètre de gauche de l'opérateur suivant.
Ｆ²⊞υ⊟θ
Sinon, déplacez l'opérateur et son paramètre de gauche dans une liste temporaire.
Ｗυ⊞θ⊟υ
Une fois que tous les opérateurs ont été traités, déplacez tous les opérateurs et paramètres enregistrés vers la liste principale, en vidant également à nouveau la liste temporaire.
»⭆θι
Stringify la liste résultante.
85 70 octets pour un format lisible par l'homme (avec parenthèses):
≔⮌Φ⪪Ｓ ιθＦ⪪⁺“ ∨μ[Ek✂◧‽_U⁹�A\”α.«Ｗ⊖Ｌθ¿№ι↥§§θ⊖κ⁰⊞θ⪫()⪫Ｅ³⊟θ Ｆ²⊞υ⊟θＷυ⊞θ⊟υ»θ
Essayez-le en ligne! Le lien est vers la version verbeuse du code. Explication: Comme ci-dessus, mais après avoir extrait les trois éléments dans un tableau, le tableau est joint par des espaces, puis mis entre parenthèses avant d'être repoussé dans la liste, ce qui signifie que le résultat final peut être directement imprimé.
Scala , 308 octets
Je suis sûr que ce n'est pas le moyen le plus court de le faire, mais voici une solution dans Scala :)
s=>{def g(q:Seq[String]):String=if(q.size<2)q(0)else{val o=Seq("*/%","+-",":","!=","<>","&","^","|").zipWithIndex
val t=1.to(q.size-1,2).map(r=>o.map(a=>(r,if(a._1.contains(q(r)(0)))a._2 else 8))).map(_.minBy(_._2)).reverse.maxBy(_._2)._1
"("+g(q.take(t))+")"+q(t)+"("+g(q.drop(t+1))+")"}
g(s.split("\\s+"))}
Essayez-le en ligne!