Conversion de la notation Infix en notation Prefix

12

Étant donné une expression arithmétique, qui peut inclure des parenthèses ( ()), des exposants ( ^), une division ( /) et une multiplication ( *), une addition ( +) et une soustraction ( -) (dans cet ordre de fonctionnement), telles que

a ^ (2 / 3) * 9 * 3 - 4 * 6

sortie la même expression en notation préfixe.

(- (* (* (^ a (/ 2 3)) 9) 3) (* 4 6))

Les espaces sont facultatifs à l'entrée comme à la sortie. Vous pouvez supposer que tous les opérateurs sont associatifs à gauche et que tous les nombres de l'expression sont des entiers à un chiffre (c'est-à-dire [0-9]).

Il s'agit d'un défi de golf de code, donc la solution la plus courte l'emporte.

Peter Olson
la source
1
+ Et - ont-ils la même priorité, ou est-il + supérieur à -? C'est-à-dire, est 3+4-5+6 = (((3+4)-5)+6)ou ((3+4)-(5+6))?
Keith Randall
De plus, vous avez omis la division dans votre liste d'opérations.
PhiNotPi
les parenthèses sont-elles facultatives en sortie?
Ali1S232
@KeithRandall *et /ont la même priorité, comme le fait +amd -.
Peter Olson
@Gajet Non, ils ne le sont pas.
Peter Olson

Réponses:

13

Rubis 1,9 - 134

%w[** / * + -].map{|o|String.send(:define_method,o){|n|"(#{o=='**'??^:o} #{self} #{n})"}}
puts eval gets.gsub(/\w/,'?\0').gsub ?^,'**'

Assez mal, mais ça marche:

$ echo 'a ^ (2 / 3) * 9 * 3 - 4 * 6' | ruby sol.rb
(- (* (* (^ a (/ 2 3)) 9) 3) (* 4 6))
eregon
la source
3

Python, 222 caractères

class A:
 def __init__(s,x):s.v=x
for x in('pow^','mul*','div/','add+','sub-'):exec('A.__'+x[:3]+'__=lambda s,y:A("('+x[3]+'"+s.v+y.v+")")')
import re
print eval(re.sub('(\\w)','A("\\1")',raw_input().replace('^','**'))).v

Similaire à Ruby, sauf que Python ne vous permet pas de redéfinir les opérations globales, uniquement les opérations d'une classe.

Keith Randall
la source
2

Perl 6 (146 | 150)

La façon la plus simple de procéder consiste à remplacer simplement les sous-programmes qui implémentent les opérateurs par de nouveaux.

sub infix:«+»   ($a,$b) { "(+ $a $b)" }
sub infix:«-»   ($a,$b) { "(- $a $b)" }
sub infix:«*»   ($a,$b) { "(* $a $b)" }
sub infix:['/'] ($a,$b) { "(/ $a $b)" } # stupid highlighter
sub infix:«**»  ($a,$b) { "(^ $a $b)" }

# currently there seems to be a bug that
# prevents this from modifying the parser correctly
# probably because there is already a different operator with this name
# which has nothing to do with exponentiation
my &infix:«^» := &[**];

say 'a' ** (2 / 3) * 9 * 3 - 4 * 6;
# (- (* (* (^ a (/ 2 3)) 9) 3) (* 4 6))␤

Le nombre minimal absolu d'octets pour le faire de cette façon est:

sub infix:<+>{"(+ $^a $^b)"}␤  #   29
sub infix:<->{"(- $^a $^b)"}␤  # + 29
sub infix:<*>{"(* $^a $^b)"}␤  # + 29
sub infix:<**>{"(^ $^a $^b)"}␤ # + 30
sub infix:</>{"(/ $^a $^b)"}␤  # + 29

146 octets, bien qu'il soit plus logique de compter les graphèmes en Perl 6.

Cela suppose que « sortir la même expression en notation de préfixe » pourrait simplement faire référence au résultat de l'expression, pas nécessairement à la sortie du programme.

Vous devez ajouter say devant l'expression pour que le programme l'imprime sur STDOUT. (150 octets)

Brad Gilbert b2gills
la source
0

Unix TMG , 189 octets

p:ignore(<< >>)parse(e);e:q(t,a);t:q(x,m);x:q(r,h);q:proc(x,y)x k:y/d x={<(>2 3 1<)>}b\k;r:o(!<<+-*/^()>>)|<(>e<)>;a:o(<<+->>);m:o(<<*/>>);h:o(<<^>>);o:proc(n)smark any(n)scopy;d:;b:bundle;

La solution est presque directement tirée du manuel de la langue, avec seulement le golf de base.

Étendu:

prog:  ignore(<< >>) parse(expr);
expr:  q(term, addop);
term:  q(fact, mulop);
fact:  q(prim, expop);
q:     proc(x,y) x k: y/done x ={ <(> 2 3 1 <)> } b\k;
prim:  op(!<<+-*/^()>>) | <(> expr <)>;
addop: op(<<+->>);
mulop: op(<<*/>>);
expop: op(<<^>>);
op:    proc(n) smark any(n) scopy;
done:  ;
b:     bundle;
Andriy Makukha
la source