12
\$\begingroup\$

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.

\$\endgroup\$
5
  • 2
    \$\begingroup\$ 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))? \$\endgroup\$ Jan 12, 2012 at 20:12
  • \$\begingroup\$ Also, you left out division in your list of operations. \$\endgroup\$
    – PhiNotPi
    Jan 12, 2012 at 20:23
  • \$\begingroup\$ are parentheses optional in output? \$\endgroup\$
    – Ali1S232
    Jan 12, 2012 at 20:34
  • \$\begingroup\$ @KeithRandall * and / have the same precedence, as do + amd -. \$\endgroup\$ Jan 12, 2012 at 21:49
  • \$\begingroup\$ @Gajet No, they're not. \$\endgroup\$ Jan 12, 2012 at 21:53

4 Answers 4

13
\$\begingroup\$

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))
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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)

\$\endgroup\$
0
0
\$\begingroup\$

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;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.