4 ms·

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

23 points by emmett 18y ago

abstractbill 18y ago
Common Lisp: http://abstractnonsense.com/math.html 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.
dzorz 18y ago
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 18y ago
  Edit: grammer I think you need one more edit. :-)
deleted 18y ago
[deleted]
marketer 18y ago
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 18y ago
  It doesn't work correctly. Example: print parse_expr("1+2/3/4-5*6") Result: (+ 1 (/ 2 (/ 3 (- 4 (* 5 6)))))
  - marketer 18y ago
    Yeah, it doesn't take into account operator precedence :(
deleted 18y ago
[deleted]
gojomo 18y ago
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.)

23 points by emmett 18y ago

Common Lisp: http://abstractnonsense.com/math.html 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.

dzorz 18y ago

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 18y ago
Edit: grammer I think you need one more edit. :-)

deleted 18y ago

[deleted]

marketer 18y ago

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 18y ago
It doesn't work correctly. Example: print parse_expr("1+2/3/4-5*6") Result: (+ 1 (/ 2 (/ 3 (- 4 (* 5 6)))))
- marketer 18y ago
  Yeah, it doesn't take into account operator precedence :(

deleted 18y ago

[deleted]

gojomo 18y ago

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