Convert from Infix Notation to Prefix Notation

Question

Given an arithmetic expression, which can include parentheses (()), exponents (^), division (/) and multiplication (*), addition (+) and subtraction (-) (in that order of operation), such as

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

output the same expression in prefix notation.

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

Spaces are optional in the input as well as the output. You may assume that all operators are left-associative and that all of the numbers in the expression are single digit integers (i.e. [0-9]).

This is a code golf challenge, so the shortest solution wins.

Answer 1

Ruby 1.9 - 134

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

Pretty evil, but it works:

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

Answer 2

Python, 222 chars

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

Similar to the Ruby one, except Python doesn't let you redefine the global ops, only ops of a class.

Answer 3

Perl 6 (146|150)

The easiest way to do this is to just swap out the subroutines that implement the operators for new ones.

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))␤

The absolute minimum amount of bytes for doing it this way is:

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 bytes, although it makes more sense to count graphemes in Perl 6.

This assumes that "output the same expression in prefix notation" could just refer to the result of the expression, not necessarily the output of the program.

You would have to add say  in front of the expression to get the program to print it to STDOUT. (150 bytes)

Answer 4

Unix TMG, 189 bytes

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;

The solution is almost straight from the manual for the language, with only basic golfing.

Expanded:

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;