Bolo <malavoi@gmail.com> writes:
Bonjour à tous,
j'essaye de faire une méthode pour convertir une expression infix et
prefix
ca passe pas
Ou est mon problème ?
merci
def parse_simple(expr, opers=%w(+ - * /))
return expr if opers.empty?
return parse_simple(expr, opers[1..-1]) unless expr.include?
(opers.first)
"(#{opers.first} " +
expr.split(opers.first).map {|e|
p e
parse_simple(e, opers[1..-1]).strip
}.join(" ") +
")"
end
def parse(expr, exprs = [])
while expr.gsub!(/\(([^\(\)]+)\)/) {"expr:#{(exprs <<
parse_simple($1)).size - 1}"}; end
expr = parse_simple(expr)
while expr.gsub!(/expr:(\d+)/) {exprs[$1.to_i]}; end
expr
end
p "2 * 5 + 1 deviens "+ parse("2 * 5 + 1") +" doit etre (+ 1 (* 2
5))"
(class Array
# Why did Matz remove these useful functions?
(def remove(element)
(result = (self . clone))
(result . delete(element))
result
end)
(def append(*args)
(result = (self . clone))
(args . each { | other | (result . concat(other)) })
result
end)
(def butlast(n = 1)
(self . slice(0 .. -(n + 1)))
end)
(def rest(n = 1)
(self . slice(n .. -1))
end)
(def second
(if (1 < (self . length))
(self . at(1))
else
nil
end)
end)
(def third
(if (2 < (self . length))
(self . at(2))
else
nil
end)
end)
(def fourth
(if (3 < (self . length))
(self . at(3))
else
nil
end)
end)
(def fifth
(if (4 < (self . length))
(self . at(4))
else
nil
end)
end)
(def sixth
(if (5 < (self . length))
(self . at(5))
else
nil
end)
end)
(def seventh
(if (6 < (self . length))
(self . at(6))
else
nil
end)
end)
(def eighth
(if (7 < (self . length))
(self . at(7))
else
nil
end)
end)
(def ninth
(if (8 < (self . length))
(self . at(8))
else
nil
end)
end)
(def tenth
(if (9 < (self . length))
(self . at(9))
else
nil
end)
end)
end)
(class SimpleScanner
(attr_accessor :text)
(def initialize(text)
(@text = ((text . split(" ")) . reverse))
self
end)
(ALL_DIGITS = (Regexp . new("^[0-9]+$")))
(def getToken
(token = (@text . last))
(result =
(if (ALL_DIGITS . match(token))
(token . to_i)
else
token
end))
# (printf "getToken --> %p\n",result)
result
end)
(def advance
(@text . pop)
self
end)
end)
(class SimpleExpressionParser
# expr ::= term
# expr ::= term +|- expr
# term ::= fact
# term ::= fact *|/ term
# fact ::= ( expr ) | number
(attr_accessor :forceBinary)
(attr_accessor :scanner)
(def initialize(scanner,forceBinary = false)
(@forceBinary = forceBinary)
(@scanner = scanner)
self
end)
(def parse
(if (@scanner . getToken)
(parseExpression)
else
:EOF
end)
end)
(def parseExpression
(token = (@scanner . getToken))
(if ((token == "(") or (Numeric === token))
(term1 = (parseTerm))
(token = (@scanner . getToken))
(if (["+","-"] . member?(token))
(op = token)
(@scanner . advance)
(term2 = (parseExpression))
(if forceBinary
[op,term1,term2]
elsif ((Array === term2) and (op == (term2 . first)))
([op,term1] . append(term2 . rest))
else
[op,term1,term2]
end)
else
term1
end)
else
(raise sprintf("Invalid token at the start of an expression: %p",token))
end)
end)
(def parseTerm
(token = (@scanner . getToken))
(if ((token == "(") or (Numeric === token))
(factor1 = (parseFactor))
(token = (@scanner . getToken))
(if (["*","/"] . member?(token))
(op = token)
(@scanner . advance)
(factor2 = (parseTerm))
(if forceBinary
[op,factor1,factor2]
elsif ((Array === factor2) and (op == (factor2 . first)))
([op,factor1] . append(factor2 . rest))
else
[op,factor1,factor2]
end)
else
factor1
end)
else
(raise sprintf("Invalid token at the start of a term: %p",token))
end)
end)
(def parseFactor
(token = (@scanner . getToken))
(if (token == "(")
(@scanner . advance)
(expr = (parseExpression))
(token = (@scanner . getToken))
(if (token == ")")
(@scanner . advance)
expr
else
(raise sprintf("Invalid token after the expression; expected a closing parenthesis, not: %p",token))
end)
elsif (Numeric === token)
(@scanner . advance)
token
else
(raise sprintf("Invalid token at the start of a factor: %p",token))
end)
end)
end)
(def atomp(obj)
(not (Array === obj))
end)
(def genInfix(rexp)
(if (atomp rexp)
(print rexp)
else
(print "(")
(op = (rexp . first))
(firstTime = true)
((rexp . rest) . each { | arg |
(if firstTime
(firstTime = false)
else
(print op)
end)
(genInfix arg)
})
(print ")")
end)
end)
(def genPrefix2(rexp)
(if (atomp rexp)
(print rexp)
else
(op = (rexp . first))
(if (((rexp . rest) . length) > 2)
(raise "genPrefix2 can process only binary operations")
end)
(print " ")
(print op)
(print " ")
(genPrefix2 (rexp . second))
(print " ")
(genPrefix2 (rexp . third))
end)
end)
(def genPrefix(rexp)
(if (atomp rexp)
(print rexp)
else
(op = (rexp . first))
(print "(")
(print op)
((rexp . rest) . each { | arg |
(print " ")
(genPrefix arg)
})
(print ")")
end)
end)
(def genSuffix2(rexp)
(if (atomp rexp)
(print rexp)
else
(op = (rexp . first))
(if (((rexp . rest) . length) > 2)
(raise "genSuffix2 can process only binary operations")
end)
(print " ")
(genSuffix2 (rexp . second))
(print " ")
(genSuffix2 (rexp . third))
(print " ")
(print op)
end)
end)
(def genSuffix(rexp)
(if (atomp rexp)
(print rexp)
else
(op = (rexp . first))
(print "(")
((rexp . rest) . each { | arg |
(genSuffix arg)
(print " ")
})
(print op)
(print ")")
end)
end)
(genInfix ["+",["*",2,5,["-",49,5]],1])
(print "\n")
(genPrefix2 ["+",["*",2,["*",5,["-",49,5]]],1])
(print "\n")
(genPrefix ["+",["*",2,5,["-",49,5]],1])
(print "\n")
(genSuffix2 ["+",["*",2,["*",5,["-",49,5]]],1])
(print "\n")
(genSuffix ["+",["*",2,5,["-",49,5]],1])
(print "\n")
(print "\n")
(e = "2 * 5 * ( 49 - 5 ) + 1")
(p = ((SimpleExpressionParser . new(SimpleScanner . new(e),true)) . parse))
(printf "parsed expression = %p\n",e)
(printf "parse tree = %p\n",p)
(genInfix p)
(print "\n")
(genPrefix2 p)
(print "\n")
(genSuffix2 p)
(print "\n")
(print "\n")
(e = "2 * 5 * ( 49 - 5 ) + 1")
(p = ((SimpleExpressionParser . new(SimpleScanner . new(e),false)) . parse))
(printf "parsed expression = %p\n",e)
(printf "parse tree = %p\n",p)
(genInfix p)
(print "\n")
(genPrefix p)
(print "\n")
(genSuffix p)
(print "\n")
------------------------------------------------------------------------
irb(main):055:0> (load"/home/pjb/src/ruby/infix.rb")
((2*5*(49-5))+1)
+ * 2 * 5 - 49 5 1
(+ (* 2 5 (- 49 5)) 1)
2 5 49 5 - * * 1 +
((2 5 (49 5 -) *) 1 +)
parsed expression = "2 * 5 * ( 49 - 5 ) + 1"
parse tree = ["+", ["*", 2, ["*", 5, ["-", 49, 5]]], 1]
((2*(5*(49-5)))+1)
+ * 2 * 5 - 49 5 1
2 5 49 5 - * * 1 +
parsed expression = "2 * 5 * ( 49 - 5 ) + 1"
parse tree = ["+", ["*", 2, 5, ["-", 49, 5]], 1]
((2*5*(49-5))+1)
(+ (* 2 5 (- 49 5)) 1)
((2 5 (49 5 -) *) 1 +)
=> true
--
__Pascal Bourguignon__
