A precedence climber as in http://eli.thegreenplace.net/2012/08/02/parsing-expressions-by-precedence-climbing/.

gistfile1.rb

require 'strscan'

# Inspired by
# http://eli.thegreenplace.net/2012/08/02/parsing-expressions-by-precedence-climbing/

# A succinct implementation of precedence climbing in Ruby

operations = {}

%w(+ -).each { |c| operations[c] = [:left, 1] }
%w(* /).each { |c| operations[c] = [:left, 2] }
%w(^).each { |c| operations[c] = [:right, 3] }

class Input
  def initialize str, operations
    @io = StringScanner.new(str)

    op_re_part = operations.keys.map { |e| Regexp.escape(e) }.join('|')
    @re = /#{op_re_part}/
    
    @last = nil
  end

  def number
    @io.scan(/\d+/).tap {
      @io.skip(/\s+/) }
  end

  def op
    @last = @io.pos

    @io.scan(@re).tap {
      @io.skip(/\s+/) } 
  end

  # Rewinds the input source before the last operation (#op) seen.
  def rewind kind
    @io.pos = @last || 0
  end

  def ends? 
    @io.eos?
  end
end

class PrecClimber
  attr_reader :operations
  def initialize operations
    @operations = operations
  end

  def climb input, current_prec=1
    expr = []
    
    expr << input.number

    while not input.ends?
      op = input.op
      assoc, prec = operations[op]

      # The next atom has either the same precedence and is 
      if prec >= current_prec
        next_prec = (assoc == :left) ? prec+1 : prec
        expr << op << climb(input, next_prec)
      else
        input.rewind :op
        return unwrap(expr)
      end
    end

    unwrap(expr)
  end

  def unwrap expr
    expr.size == 1 ? expr.first : expr
  end
end

def compute operations, num
  input = Input.new(num, operations)
  climber = PrecClimber.new(operations)
  p climber.climb input
end

compute operations, '1+2+3+4+5'
compute operations, '1+2 * 3 ^ 5 ^ 6 + 4 + 3'