# Convert from Infix Notation to Prefix Notation

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.

• Are + and - the same precedence, or is + higher than -? I.e., is 3+4-5+6 = (((3+4)-5)+6) or ((3+4)-(5+6))? – Keith Randall Jan 12 '12 at 20:12
• Also, you left out division in your list of operations. – PhiNotPi Jan 12 '12 at 20:23
• are parentheses optional in output? – Ali1S232 Jan 12 '12 at 20:34
• @KeithRandall * and / have the same precedence, as do + amd -. – Peter Olson Jan 12 '12 at 21:49
• @Gajet No, they're not. – Peter Olson Jan 12 '12 at 21:53

## 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))  ## 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. ## 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)

## 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);