Postfix to Infix (#148)

Ruby
41

Since Pastie doesn’t seem to be so reliable (at least today):

###########################################

Ruby quiz #148

Ruby Quiz - Postfix to Infix (#148)

Eric D.

02/12/2007

It removes unnecesary ().

ruby postfix_to_infix.rb ‘56 34 213.7 + * 678 -’

56*(34+213.7)-678

=13193.2

ruby postfix_to_infix.rb ‘1 56 35 + 16 9 - / +’

1+(56+35)/(16-9)

=14

ruby postfix_to_infix.rb ‘1 2+ 4* 5*’

(1+2)45

=60

You can omit spaces between operands and operators

ruby postfix_to_infix.rb ‘1 2+ 4* 5+ 3-’

(1+2)*4+5-3

=14

ruby postfix_to_infix.rb ‘1 2+ 3 4 + +’

1+2+3+4

=10

ruby postfix_to_infix.rb ‘1 2 - 3 4 - -’

1-2-(3-4)

=0

You can use either ** or ^

which actually raises troubles while parsing : is “**” == “* *” or

“**”==“^” ?

ruby postfix_to_infix.rb ‘2 2 ^ 2 ^’

(2^2)^2

=16

ruby postfix_to_infix.rb ‘2 2 ** 2 **’

(2**2)**2

=16

ruby postfix_to_infix.rb ‘2 3 4 ** **’

234

=2417851639229258349412352

ruby postfix_to_infix.rb ‘2 3 ** 4 **’

(2**3)**4

=4096

It raises when something’s missing

ruby postfix_to_infix.rb ‘1 2+ 4* 5+ 3’

postfix_to_infix.rb:94:in `convert_to_infix’: ArgumentError

No UnaryOperation yet

class Operation
attr_reader :operator, :operands
attr_writer :with_parentheses
def initialize(operator, *operands)
@operator=operator
@operands=operands
@with_parentheses=false
add_parentheses_to_operands_if_necessary!
end

def has_parentheses?
@with_parentheses
end
end

class BinaryOperation<Operation
@@precedence_over={
‘+’ =>[‘’,‘’],
#no need to put () before -
‘-’ =>[‘’,‘- +’],
‘*’ => [‘- +’,‘- +’],
‘/’ => [‘- +’,‘- + * /’],
‘**’=>[‘- + * / ^ **’,‘- + * /’],
‘^’=>[‘- + * / ^ **’,‘- + * /’]
}

def to_s
operands.collect{|operand| if operand.is_a?(Operation) &&
operand.has_parentheses? then
“(#{operand})”
else
operand
end
}.join(operator)
end

private

def add_parentheses_to_operands_if_necessary!
operands.each_with_index{|operand,i|
operators_with_lower_priority=@@precedence_over[operator][i].split(’
')
operand.with_parentheses=operators_with_lower_priority.any?{|o|
operand.operator == o} if operand.is_a?(BinaryOperation)
}
end
end

class Postfix<String
def split_into_operands_and_operators
self.scan(/([\w.]+|*+|+|/|-|^)/).flatten
end

def to_infix
@to_infix||=convert_to_infix
end

def evaluate
eval(self.to_infix.gsub(/^/,‘**’))
end

private

def convert_to_infix
stack=[]
self.split_into_operands_and_operators.each{|term|
if term=~/^[\w.]+$/ then
stack<<term
else
right_operand,left_operand=stack.pop,stack.pop
stack<<BinaryOperation.new(term,left_operand,right_operand)
end
}
raise ArgumentError unless stack.size==1
stack.first.to_s
end
end

p=Postfix.new(ARGV[0])
puts p.to_infix
puts “=#{p.evaluate}”

###########################################

see Parked at Loopia for colored syntaxing

Thanks again,

Eric

42

On Dec 3, 2007 3:44 PM, Eric DUMINIL [email protected] wrote:

ruby postfix_to_infix.rb ‘56 34 213.7 + * 678 -’

ruby postfix_to_infix.rb ‘1 2 - 3 4 - -’

=4096

class Operation
@with_parentheses
‘**’=>[‘- + * / ^ **’,‘- + * /’],
}.join(operator)
end

    stack<<term

p=Postfix.new(ARGV[0])

:right => {'and'=>-1, '='=>0 ,'+'=>2, '-'=>3, '*'=>4, '/'=>5}
    end

puts Benchmark.measure {
parenthesize(stack.last, 0, :right)
where N = 10000 i have benchmark:

0.282000 0.000000 0.282000
0.313000 0.000000 0.313000

OOO = “/±"
COM = "+”

def postfix_to_infix(expression)
terms = []
expression.split(/\s/).each do |p|
terms << p
if OOO.include?(p)
terms << [terms.slice!(-1), terms.slice!(-2), terms.slice!(-1)]
end
end
peval(terms[0])
end

def peval(terms, parent_o = nil, is_right = false)
return [terms, terms.to_f] unless terms.class == Array

o = terms[0]
a, a_val = peval(terms[1], o)
b, b_val = peval(terms[2], o, true)

sval = [a, o, b].join(’ ')
nval = a_val.send(o, b_val)

if (OOO.index(o) > OOO.index(parent_o || o)) ||
(!COM.include?(o) && OOO.index(o) == OOO.index(parent_o || o) &&
is_right)
sval = ‘(’ + sval + ‘)’
end

[sval, nval]
end

res = postfix_to_infix(ARGV[0])
puts res[0], res[1]

% ruby /tmp/rt.rb ‘56 34 213.7 + * 678 -’
56 * (34 + 213.7) - 678
13193.2

Some tests:

56 * (34 + 213.7) - 678 == 56 * (34 + 213.7) - 678 → pass
2 + 3 == 2 + 3 → pass
1 + (56 + 35) / (16 - 9) == 1 + (56 + 35) / (16 - 9) → pass
1 + 2 + 3 + 4 == 1 + 2 + 3 + 4 → pass
1 - 2 - (3 - 4) == 1 - 2 - (3 - 4) → pass
5 - (1 - 2 - (3 - 4)) == 5 - (1 - 2 - (3 - 4)) → pass
5 / (1 / 2 / (3 / 4)) == 5 / (1 / 2 / (3 / 4)) → pass
2 / 7 / 9 == 2 / 7 / 9 → pass
2 / (7 / 9) == 2 / (7 / 9) → pass

43

A pretty simplistic regex-based solution that doesn’t minimize
parentheses:

#!/usr/bin/env ruby

str = ARGV[0].split(/[^.\d+-*/]/).join(’ ')

while str !~ /^(.)$/
str.sub!(/([^ ]+) ([^ ]+) ([+-/])/, ‘(\1\3\2)’)
end

puts str.gsub(/([+-/])/, ’ \1 ').sub(/^((.))$/, ‘\1’)

44

2007/12/3, Artem V. [email protected]:>

The final task is: having information about operators priorities,
commutativity/non-commutativity, and associativity type (left or
right) construct OP_STRENGTH

Errr … “commutativity/non-commutativity” →
“associativity/non-associativity”

Artem

45

On 12/2/07, Daniel M. [email protected] wrote:

esau:/tmp$ ruby asrq148.rb ‘2 3 -’

I think you only changed ‘Token’ to Term, and missed the ‘tok’=>‘term’
sub.
That’s the only way I get what you show.

Anyway, Here’s an updated version wihch handles the associativity test
cases.

#postfix to infix

ruby quix #148

Adam S.

v2

Converts postfix to infix notation

uses ruby’s operators & precedence rules

$Operators = {
‘&&’=>'0 ', ‘||’=>'0 ',
‘==’=>'1 ', ‘===’=>'1 ', ‘<=>’=>'1 ',
‘<=’=>'2 ', ‘>=’=>'2 ', ‘<’ =>'2 ', ‘>’=>'2 ',
‘^’ =>'3 ', ‘|’ =>'3 ',
‘&’ =>'4 ',
‘<<’=>‘5L’, ‘>>’=>‘5L’,
‘+’ =>'6 ', ‘-’ =>‘6L’,
‘*’ =>'7 ', ‘/’ =>‘7L’, ‘%’=> ‘7L’,
‘**’=>‘8R’,
:term=>'10 ’
}

class Term
attr_reader :precedence, :dir
def initialize str, groupPrec=nil
@s = str
@precedence = $Operators[str]||groupPrec||$Operators[:term]
@dir = @precedence[-1].chr
@precedence = @precedence.to_i
end
def isOp
@precedence != $Operators[:term].to_i
end
def parenthesize
@s=“(#{@s})”
end
def to_s
@s
end
end

class Infix
def initialize rpn
stack=[]
rpn.split.each do |t|
term = Term.new(t)
if term.isOp
rval = stack.pop
lval = stack.pop
raise “Empty Stack” unless lval && rval
lval.parenthesize if lval.precedence < term.precedence or
term.dir==‘R’&& lval.precedence == term.precedence
rval.parenthesize if rval.precedence < term.precedence or
term.dir==‘L’&& rval.precedence == term.precedence
phrase = “#{lval} #{term} #{rval}”
term = Term.new(phrase,term.precedence)
#p term
end
stack.push term
end
@expr = stack.pop
raise “Extra terms” unless stack.size==0
end
def to_s
@expr.to_s
end
end

def test
puts Infix.new(‘2 3 +’).to_s == ‘2 + 3’
puts Infix.new(‘56 34 213.7 + * 678 -’).to_s == ‘56 * (34 + 213.7) -
678’
puts Infix.new(‘1 56 35 + 16 9 - / +’).to_s == ‘1 + (56 + 35) / (16 -
9)’
puts Infix.new(‘1 2 + 3 4 + +’).to_s == ‘1 + 2 + 3 + 4’
puts Infix.new(‘1 2 - 3 4 - -’) .to_s == ‘1 - 2 - (3 - 4)’
puts Infix.new(‘2 2 ** 2 **’).to_s == ‘(2 ** 2) ** 2’
puts Infix.new(‘2 2 2 ** **’).to_s == ‘2 ** 2 ** 2’
puts Infix.new(‘1 2 3 4 5 + + + +’).to_s == ‘1 + 2 + 3 + 4 + 5’
puts Infix.new(‘1 2 3 4 5 / / - -’).to_s == ‘1 - (2 - 3 / (4 /
5))’
puts Infix.new(‘3 5 * 5 8 * /’).to_s == ‘3 * 5 / (5 * 8)’
puts Infix.new(‘3 5 + 5 8 + -’).to_s == ‘3 + 5 - (5 + 8)’
puts Infix.new(‘a b == c 1 + 2 < &&’).to_s == ‘a == b && c + 1 < 2’
puts Infix.new(‘1 2 << 4 <<’).to_s == ‘1 << 2 << 4’
puts Infix.new(‘1 2 4 << <<’).to_s == ‘1 << (2 << 4)’
end

if FILE == $0
if ARGV.empty?
test
else
puts Infix.new(ARGV.join(’ ')).to_s
end
end

46

Hi,

Didn’t have much time for this, so here’s a partial solution.
What I haven’t done is work on ARGV and the bracket removal code is
pretty basic
produces
1+(56+35)/(16-9) - good
1+(2+(3+4)) - needs work…

Cheers,
Dave

eqn= %w[1 56 35 + 16 9 - / +]
ops= %w[+ - * /]

stack= []

eqn.each do |e|
if ops.include? e
b= stack.pop || 0
a= stack.pop || 0
if stack.empty?
stack= [a, e.to_sym, b]
else
stack << [a, e.to_sym, b]
end
else
stack << e
end
end

def disp item, depth
str=’’
if item.class== Array
inner= item.inject(’’) {|sum, e| sum << (disp e, depth+1)}
inner= “(#{inner})” unless ([:*, :/].include? item[1]) || depth==0
str << inner
else
str << item.to_s
end
str
end

puts disp(stack,0)

47

On Dec 2, 9:16 pm, Daniel M. [email protected] wrote:

Data structures? We don’t need no stinkin’ data structures.

Postfix expression to infix expression via regular expressions.

Hi,

as no one have replied to this so far, I think I must express my
admiration to your solution. Bravo Daniel! :slight_smile:

48

Greetings -
I know this has been a while, but if you still have your JAVA solution
to outfix → infix, I would be very interested in seeing it!
Thanks

Christian von Kleist wrote in post #594997:

On Nov 30, 2007 8:28 AM, Ruby Q. [email protected] wrote:

    16
    $ ruby postfix_to_infix.rb '2 3 +'

the minimum of what is needed. For example, prefer these results:
$ ruby postfix_to_infix.rb ‘1 56 35 + 16 9 - / +’
(1 + ((56 + 35) / (16 - 9)))

Posting equations and your output is not a spoiler.

I had this as an assignment for a class once, in Java, so I’ll sit
this one out. Fun quiz!