How many of lines of code for infix-to-prefix?

dzorz · on Aug 24, 2008

Solution in python that parses infix expression from string and returns a list of tokens in prefix form.

    def parse(s):
        for operator in ["+-", "*/"]:
            depth = 0
            for p in xrange(len(s) - 1, -1, -1):
                if s[p] == ')': depth += 1
                if s[p] == '(': depth -= 1
                if not depth and s[p] in operator:
                    return [s[p]] + parse(s[:p]) + parse(s[p+1:])
        s = s.strip()
        if s[0] == '(':
            return parse(s[1:-1])
        return [s]
    print parse("1+3* 4/haha-5*(2+3.14  ) * (4+5)")

Edit: grammer

mhartl · on Aug 24, 2008

Edit: grammer

I think you need one more edit. :-)

abstractbill · on Aug 23, 2008

Common Lisp: http://abstractnonsense.com/math.html

It also handles function calls; sin(x) becomes (sin x). For example:

  * (infix-to-prefix '(1 + sin(3 + x) * 42))
  (+ 1 (* (SIN (+ 3 X)) 42))

If you want the input to be a string, just use read-from-string and add parens at each end of the input string.

gojomo · on Aug 24, 2008

If you don't mind a regex-heavy approach, here's a single-method version in Ruby that handles precedence correctly and maintains the ability to pass in operators:

  def in_to_pre_fix(expr, opers=%w(*/ +-))
    subex = "\\s*(?:(?:<([^>]+)>)|([\\w]+))\\s*"
    while expr !~ /^<[^>]*>$/ and expr.sub!(/(?:^|\()([^)(]*)(?:\)|$)/) { | m |
      opers.each { | oper | 
        while m.sub!(Regexp.new("#{subex}([#{Regexp.quote(oper)}])#{subex}"),
          '<\3 \1\2 \4\5>'); end }
      m.tr_s("() "," ").strip() }; end
    expr.delete("<>")
  end

(I'm new to Ruby, so it may not be idiomatic or preferred whitespace-style.)

marketer · on Aug 24, 2008

Another python, but recursive:

  def doit(expr):
    expr=''.join(expr.split())
    if expr.startswith('('):
        (left,size) = doit(expr[1:])
        size+=2
    else:
        left = re.compile('(\w+)').match(expr).groups(0)[0]
        size = len(left)
    rest = expr[size:]
    if rest=='' or rest[0]==')':
        return left,size
    op = re.compile('([*/+-])').match(rest).groups(0)[0]
    right,size2 = doit(rest[1:])
    return '(%s %s %s)'%(op, left, right) ,size+size2+1

dzorz · on Aug 24, 2008

It doesn't work correctly. Example:

    print parse_expr("1+2/3/4-5*6")

Result:

    (+ 1 (/ 2 (/ 3 (- 4 (* 5 6)))))

marketer · on Aug 24, 2008

Yeah, it doesn't take into account operator precedence :(