Refactoring feedback for Reverse Polish Notation (RPN) or Postfix Notation

Question

One of the pre-work exercises for Dev Bootcamp is an RPN calculator. I made it work but would like refactoring feedback. Any and all help to make this code cleaner is greatly appreciated.

class RPNCalculator
  def evaluate(rpn)
    a = rpn.split(' ')
    array = a.inject([]) do |array, i|    
      if i =~ /\d+/ 
        array << i.to_i
      else
        b = array.pop(2)
        case 
          when i == "+" then array << b[0] + b[1]  
          when i == '-' then array << b[0] - b[1]  
          when i == '*' then array << b[0] * b[1]  
          when i == '/' then array << b[0] / b[1]  
        end
      end
    end
    p array.pop
  end
end

calc = RPNCalculator.new
calc.evaluate('1 2 +')   # => 3
calc.evaluate('2 5 *')   # => 10
calc.evaluate('50 20 -') # => 30
calc.evaluate('70 10 4 + 5 * -') # => 0

score 2 · Accepted Answer · answered Jul 02 '13 at 08:34

2

class RPNCalculator
  def evaluate rpn
    array = rpn.split(" ").inject([]) do |array, i|    
      if i =~ /\d+/ 
        array << i.to_i
      else
        b = array.pop(2)
        array << b[0].send(i, b[1])
      end
    end
    p array.pop
  end
end

answered Jul 02 '13 at 08:34

sawa

165,429
45
277
381

Thank you very much for showing me a fantastic use for the Object#send method. – ltrainpr Jul 12 '13 at 04:51

score 1 · Answer 2 · answered Jul 02 '13 at 05:08

I tend to prefer avoiding case..when in favor of lookup tables. So I'd change your code to:

class RPNCalculator
  def evaluate(rpn)
    a = rpn.split(' ')
    array = a.inject([]) do |array, i|    
      if i =~ /\d+/ 
        array << i.to_i
      else
        array << array.pop(2).reduce(op(i))
      end
    end
    p array.pop
  end

  private

  def op(char)
    {'+'=>:+, '-'=>:-, '/'=>:/, '*'=>:*}[char]
  end
end

I also don't believe you should only be popping off 2 operands. "1 2 3 +" would be valid RPN, evaluating to 6. The entire stack should be reduced. This also avoids the mutation, which is a good thing, as it follows a more functional style.

class RPNCalculator
  def evaluate(rpn)
    a = rpn.split(' ')
    array = a.inject([]) do |array, i|    
      if i =~ /\d+/ 
        [*array, i.to_i]
      else
        [array.reduce(op(i))]
      end
    end
    p array.pop
  end

  private

  def op(char)
    {'+'=>:+, '-'=>:-, '/'=>:/, '*'=>:*}[char]
  end
end

I removed the other mutation here too, by using [*arr, value] instead of actually modifying the array.

Finally, I'd avoid printing directly from your #evaluate method and just return the number. I'd also (again) avoid the mutation:

class RPNCalculator
  def evaluate(rpn)
    a = rpn.split(' ')
    stack = a.inject([]) do |stack, i|    
      if i =~ /\d+/ 
        [*stack, i.to_i]
      else
        [stack.reduce(op(i))]
      end
    end
    stack.last
  end

  private

  def op(char)
    {'+'=>:+, '-'=>:-, '/'=>:/, '*'=>:*}[char]
  end
end

I renamed 'array' to 'stack', since it is a parser stack and is less generic than just array.

Thank you d11, this is very helpful. Can you help me understand what you mean by mutation and how to avoid it? — ltrainpr, Jul 02 '13 at 13:27
Hi d11wtq. Thank you very much for the feedback, but this code doesn't work for RPN "70 10 4 + 5 * -" which should evaluate to zero. — ltrainpr, Jul 12 '13 at 05:10
@Itrainpr you can put two binary operators in immediate succession like that? o_O It should evaluate `((70 + 10 + 4) * 5) -`, which leaves a dangling `-`. — d11wtq, Jul 12 '13 at 11:47
Yes you can (according to Wikipedia examples). I think the issue lies "1 2 3 +" being valid RPN. I haven't found any proof to support that being valid RPN. I believe it needs to be "1 2 3 + +" — ltrainpr, Jul 13 '13 at 05:31
Wow, old post, but to clarify: `70 10 4 + 5 * -` usually evaluates as `((70 * (10 + 4)) - 5)`. Take a look at the `dc` unix calculator, `forth` or `factor` languages. The result should be 0 as @Itrainpr said. `1 2 3 +` should leave `1 5` on the stack. — fede s., Mar 24 '16 at 16:01

Refactoring feedback for Reverse Polish Notation (RPN) or Postfix Notation

2 Answers2