10
\$\begingroup\$

Dealing with equations in the absence of a good equation editor is messy and unpleasant. For example, if I wanted to express an integral and its solution, it might look something like this:

Integral[x^3 e^(-m x^2 b /2), dx] = -((2 + bmx^2)/(b^2*e^((bmx^2)/2)*m^2))

At integrals.wolfram.com, this is called "input form." No one likes to see an equation in "input form." The ideal way of visualizing this equation would be:

enter image description here

(Wolfram calls this "traditional form")

For this codegolf, write a program that will take some equation in "input form" as input and visualize that equation in an ascii representation of "traditional form." So, for this example we might get something like this:

       /\      3
       |      x
       | ------------  dx = 
       |       2
      \/   (m x  b)/2
          e

              2
     2 + b m x
-(-----------------)
            2
   2  (b m x )/2  2
  b  e           m

Requirements:

  1. Don't shuffle, simplify or rearrange the input in any way. Render it in exactly the same form it was described by the input.
  2. Support the four basic mathematical operations (+,-,*,/). When not multiplying two adjacent numbers the * symbol is implied and should be omitted.
  3. Support for integration (as shown in the example above) is not required. Being able to support input with functions like Integrate[...] or Sqrt[...] is a bonus.
  4. Support powers as shown in the example above (the nth root can be modeled by raising to the 1/nth power).
  5. Redundant parenthesis (like those around the denomentator and numerator of the large fraction in the example above) should be omitted.
  6. The expression in the denominator and numerator of a fraction should be centered above and below the horizontal division line.
  7. You can choose whether or not to start a new line after an equal sign. In the example above, a new line is started.
  8. Order of operations must be exactly the same in the output as it is in the input.

Some examples of input and associated output for testing your solution:

Input:

1/2 + 1/3 + 1/4

Output:

1   1   1
- + - + -
2   3   4

Input:

3x^2 / 2 + x^3^3

Output:

   2     3
3 x     3
---- + x   
 2

Input:

(2 / x) / (5 / 4^2)

Output:

2
-
x
--
5
--
 2
4

Input:

(3x^2)^(1/2)

Output:

    2 1/2
(3 x )
\$\endgroup\$
  • \$\begingroup\$ Your question should generally have a tag expressing what kind of contest it is. I've taken the liberty of adding one because you said "codegolf" in the text. \$\endgroup\$ – dmckee Apr 7 '11 at 0:57
  • 3
    \$\begingroup\$ This problem is too nebulous to be code-golf. You don't say what constructs must be supported, or what they have to look like. Would just supporting +, -, *, and / be enough? Does Sigma have to be supported? What about greek letters? The possible solutions to the question as you've posed it could be too varied in functionality to be compared for code-length. \$\endgroup\$ – MtnViewMark Apr 7 '11 at 2:31
  • \$\begingroup\$ @MtnViewMark, I added some "Requirements"...let me know if the golf is better now. \$\endgroup\$ – Ami Apr 7 '11 at 2:49
  • \$\begingroup\$ @Ami - yes, much. \$\endgroup\$ – MtnViewMark Apr 7 '11 at 4:20
  • \$\begingroup\$ I agree with MtnViewMark, this seems very open ended and vague. Perhaps you would be better to limit the input and output to a well defined set of testcases for the purposes of golfing. Have you done a reference implementation? \$\endgroup\$ – gnibbler Apr 7 '11 at 4:22
10
\$\begingroup\$

Python 2, 1666 chars

The layout is actually pretty easy - it's the parsing of the input that's a royal pain. I'm still not sure it is completely correct.

import re,shlex
s=' '
R=range

# Tokenize.  The regex is because shlex doesn't treat 3x and x3 as two separate tokens.  The regex jams a space in between.                                                 
r=r'\1 \2'
f=re.sub
x=shlex.shlex(f('([^\d])(\d)',r,f('(\d)([^\d])',r,raw_input())))
T=[s]
while T[-1]:T+=[x.get_token()]
T[-1]=s

# convert implicit * to explicit *                                                                                                                                          
i=1
while T[i:]:
 if(T[i-1].isalnum()or T[i-1]in')]')and(T[i].isalnum()or T[i]in'('):T=T[:i]+['*']+T[i:]
 i+=1

# detect unary -, replace with !                                                                                                                                            
for i in R(len(T)):
 if T[i]=='-'and T[i-1]in'=+-*/^![( ':T[i]='!'
print T

# parse expression: returns tuple of op and args (if any)                                                                                                                   
B={'=':1,',':2,'+':3,'-':3,'*':4,'/':4,'^':5}
def P(t):
 d,m=0,9
 for i in R(len(t)):
  c=t[i];d+=c in'([';d-=c in')]'
  if d==0and c in B and(B[c]<m or m==B[c]and'^'!=c):m=B[c];r=(c,P(t[:i]),P(t[i+1:]))
 if m<9:return r
 if'!'==t[0]:return('!',P(t[1:]))
 if'('==t[0]:return P(t[1:-1])
 if'I'==t[0][0]:return('I',P(t[2:-1]))
 return(t[0],)

# parenthesize a layout                                                                                                                                                     
def S(x):
 A,a,b,c=x
 if b>1:A=['/'+A[0]+'\\']+['|'+A[i]+'|'for i in R(1,b-1)]+['\\'+A[-1]+'/']
 else:A=['('+A[0]+')']
 return[A,a+2,b,c]

# layout a parsed expression.  Returns array of strings (one for each line), width, height, centerline                                                                      
def L(z):
 p,g=z[0],map(L,z[1:])
 if p=='*':
  if z[1][0]in'+-':g[0]=S(g[0])
  if z[2][0]in'+-':g[1]=S(g[1])
 if p=='^'and z[1][0]in'+-*/^!':g[0]=S(g[0])
 if g:(A,a,b,c)=g[0]
 if g[1:]:(D,d,e,f)=g[1]
 if p in'-+*=,':
  C=max(c,f);E=max(b-c,e-f);F=C+E;U=[s+s+s]*F;U[C]=s+p+s;V=3
  if p in'*,':U=[s]*F;V=1
  return([x+u+y for x,u,y in zip((C-c)*[s*a]+A+(E-b+c)*[s*a],U,(C-f)*[s*d]+D+(E-e+f)*[s*d])],a+d+V,F,C)
 if'^'==p:return([s*a+x for x in D]+[x+s*d for x in A],a+d,b+e,c+e)
 if'/'==p:w=max(a,d);return([(w-a+1)/2*s+x+(w-a)/2*s for x in A]+['-'*w]+[(w-d+1)/2*s+x+(w-d)/2*s for x in D],w,b+e+1,b)
 if'!'==p:return([' -  '[i==c::2]+A[i]for i in R(b)],a+2,b,c)
 if'I'==p:h=max(3,b);A=(h-b)/2*[s*a]+A+(h-b+1)/2*[s*a];return(['  \\/|/\\  '[(i>0)+(i==h-1)::3]+A[i]for i in R(h)],a+3,h,h/2)
 return([p],len(p),1,0)

print'\n'.join(L(P(T[1:-1]))[0])

For the big input in the question, I get:

 /\         2                     2 
 |     - m x  b          2 + b m x  
 |     --------    = - -------------
 |  3      2                    2   
\/ x  e         dx         b m x    
                           ------   
                        2     2    2
                       b  e       m 

Here's some more tricky test cases:

I:(2^3)^4
O:    4
  / 3\ 
  \2 / 

I:(2(3+4)5)^6
O:             6
  (2 (3 + 4) 5) 

I:x Integral[x^2,dx] y
O:   /\ 2     
  x  | x  dx y
    \/        

I:(-x)^y
O:     y
  (- x) 

I:-x^y
O:     y
  (- x)

That last one is wrong, some precedence error in the parser.

\$\endgroup\$
  • \$\begingroup\$ shouldn't the baseline of the integral argument be verically centered after the integral? Currently it looks more like a subscript to the integral. \$\endgroup\$ – Joey Apr 14 '11 at 20:49
  • \$\begingroup\$ Not hard to change, but it would waste some space. I currently make the integral sign just big enough to span its argument (with a 3 high minimum). \$\endgroup\$ – Keith Randall Apr 14 '11 at 21:29
  • \$\begingroup\$ Slight golf: Use tabs instead of double spaces. \$\endgroup\$ – CalculatorFeline Mar 15 '16 at 16:09

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.