4
\$\begingroup\$

Given an expression of one-letter variables ([a-z]), operators (*, +, &) and parenthesis, expand it using the following axioms:

a * b != b * a
a * b * c = (a * b) * c = a * (b * c)
a + b = b + a
a + b + c = (a + b) + c = a + (b + c)
a * (b + c) = a * b + a * c
a & b = b & a
a & (b + c) = a & b + a & c

   | Comm | Assoc | Dist
 * | NO   | YES   |     
 + | YES  | YES   | *    
 & | YES  | YES   | + *  

The user will input an expression, the syntax of the input expression is called "input form". It has the following grammar:

inputform ::= expr
var ::= [a-z] // one lowercase alphabet
expr ::= add
       | add & expr
add ::= mult
      | mult + add
mult ::= prim
       | prim * mult
       | prim mult
prim ::= var
       | ( expr )

Before That means, the order of operations is * + &, a + b * c & d + e = (a + (b * c)) & (d + e) Furthermore, the operator * can be omitted: a b (c + d) = ab(c + d) = a * b * (c + d)

Whitespace is stripped out before parsing.

Examples:

(a + b) * (c + d)
= (a + b)(c + d)
= (a + b)c + (a + b)d
= ac + bc + ad + bd
(a & b)(c & d)
= ac & ad & bc & bd
(a & b) + (c & d)
= a + c & a + d & b + c & b + d
((a & b) + c)(d + e)
= ((a & b) + c)d + ((a & b) + c)e (I'm choosing the reduction order that is shortest, but you don't need to)
= ((a & b)d + cd) + ((a & b)e + ce)
= ((ad & bd) + cd) + ((ae & be) + ce)
= (ad + cd & bd + cd) + (ae + ce & be + ce)
= ad + cd + ae + ce & ad + cd + be + ce & bd + cd + ae + ce & bd + cd + be + ce

Due to commutativity, order of some terms do not matter.

Your program will read an expression in input form, and expand the expression fully, and output the expanded expression in input form, with one space separating operators, and no spaces for multiplication. (a + bc instead of a+b * c or a + b * c or a + b c)

The fully expanded form can be written without any parens, for example, a + b & a + c is fully expanded, because it has no parens, and a(b + c) is not.

Here is an example interactive session (notice the whitespaces in input)

$ expand
> a(b + (c&d))
ab + ac & ab + ad
> x y * (wz)
xywz
> x-y+1
Syntax error
> c(a +b
Syntax error
\$\endgroup\$
  • \$\begingroup\$ The last axiom states a & (b + c) = a & b + a & c but this is not stated in your distribution table below. In contrast there it says a+(b&c)=a+b&a+c which you also do in your last example. \$\endgroup\$ – Howard Jun 5 '11 at 9:20
  • \$\begingroup\$ these stuff are too difficult to done by head \$\endgroup\$ – Ming-Tang Jun 5 '11 at 21:06
  • 1
    \$\begingroup\$ I don't think there is a unique reduction, or not all formulae can be reduced. Note: (a & b)(c+d) = (a & b)x = ax & bx = a(c+d) & b(c+d) = ac+ad & bc+bd but (a & b)(c+d) = y(c+d) = yc+yd = (a & b)c+(a & b)d = (ac & bc)+(ad & bd) = z+(ad & bd) = z+ad & z+bd = (ac & bc)+ad & (ac & bc)+bd = ac+ad & bc+ad & ac+bd & bc+bd. In contrast, if you only allow right-associativity or left-associativity and not both, then any expression with the other (given with parens) cannot be unfolded. \$\endgroup\$ – Rex Kerr Jun 6 '11 at 6:52
  • \$\begingroup\$ After finding out how Perl junctions expand, I found a solution to the associativity problem: (a+b)(c&d)(e+f)(g+(h&i)) = (a+b)u(e+f)(g+v), u = (c+d), v = (h&i), but it's too late to change the question \$\endgroup\$ – Ming-Tang Jun 16 '11 at 1:39
3
\$\begingroup\$

Ruby, 698 648

O=[A='&',B='+',C='*']
M='Syntax error'
def u(x)c=x.shift;(c.nil?)?S[0]=~/[a-z]/?(S.shift):S[0]=='('?(S.shift;o=u(O*1);S[0]==')'?(S.shift;o):abort(M)):abort(M):(o=[c];loop{o<<u(x*1);break if S[0]!=c;S.shift};o)end
def d(e,a,b)a!=e[0]?e:(i=e.index{|x|x[0]==b};(i.nil?)?e:y([b]+e[i][1..-1].map{|k|z=e*1;z[i]=k;z}))end
def y(e)e.map!{|x|(x.is_a?Array)?(y(x)):(x)};o=[e[0]];e[1..-1].map{|x|x[0]==o[0]?(o+=x[1..-1]):(o<<x)};d(d(d(o.size==2?o[1]:o,C,B),C,A),B,A)end
def j(e)(e.is_a?Array)?(e.map!{|x|j(x)};o=e.shift;e*(o=='*'?'':" #{o} ")):e;end
S=gets.gsub(/ /,'').gsub(/([a-z)])(?=[a-z(])/,'\1*\2').split(//)
k=u(O*1)
puts S!=["\n"]?(M):(j y k)

This solution consists of a basic recursive descent parser (method u) which builds an syntax tree which is then flattened (y) and transformed (d) according to the distribution axioms. The output (j) simply joins the operands again.

Unfortunately I broke the functionality when I later tried to reduce the code by restructuring. Nevertheless I think there is still some chance for golfing.

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

Scala - 1049 characters

This is not fully golfed, but it gets increasingly incomprehensible as I continue, and since the examples do not all appear to be correct, I want to leave the code at least slightly sane so it can be modified.

To be run as a script file. Empty input ends the program.

type S=String
case class R(rs: List[R], s: S)
def n(s: S)=List(" + "," & ").indexOf(s)
def pr(r:R,v:Int=2):S = if (r.rs.isEmpty) r.s else {
  val x = r.rs.map(pr(_,n(r.s))).mkString(r.s)
  if (n(r.s)>v) "("+x+")" else x
}
object P extends scala.util.parsing.combinator.RegexParsers {
  val v="[a-z]"r
  def e:Parser[R]=repsep(a,"&") ^^ {R(_," & ")}
  def a=repsep(m,"+") ^^ {R(_," + ")}
  def m=repsep(p,"\\*?"r) ^^ {R(_,"")}
  def p=v ^^ {R(Nil,_)} | "("~>e<~")" ^^ {r=>R(r::Nil,"")}
}
def up(r: R):R = r match {
  case R(x::Nil,_) => up(x)
  case _ => R(r.rs.map(up),r.s)
}
def asc(r: R) = R(r.rs.flatMap(i=>if (i.s==r.s) i.rs else List(i)),r.s)
def dis(r: R):R = {
  val q = asc(r.rs.find(i=>n(i.s)>n(r.s)).map(i => {
    val (a,b)=r.rs.span(_ ne i)
    R(i.rs.map(j=>R(a ::: j :: b.tail,r.s)),i.s)
  }).getOrElse(R(r.rs.map(dis),r.s)))
  if (q==r) r else dis(q)
}
def parse(s: S) = P.parseAll(P.e,s).map(x=>pr(dis(up(x)))).getOrElse("Syntax error")
Iterator.continually{print("> ");readLine}.
takeWhile(_.length>0).foreach(s=>println(parse(s)))
\$\endgroup\$
0
\$\begingroup\$

Haskell, 472 437 characters

import Text.Parsec
data E=V Char|O Int E E
r o=fmap$foldr1(O o)
c=char
s=sepBy1
e=r 0$s(r 1$s (r 2$s(fmap V lower<|>between(c '(')(c ')')e)(optional$c '*'))(c '+'))(c '&')
g(O a x(O b y z))|b<a=g$O b(g$O a x y)(g$O a x z)
g(O a (O b x y)z)|b<a=g$O b(g$O a x z)(g$O a y z) 
g e=e
d(V c)=[c]
d(O o x y)=d x++[" & "," + ",""]!!o++d y
x=either(const "Syntax error")d.fmap g.parse e"".filter(`notElem`" \t")
main=interact$unlines.map x.lines
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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