ArithmeticExpressionParser.rb

=begin

  First iteration of an arithmetic expression parser.
  TODO: Implement precedence.

=end

def parse(str)
  n = nil                         # Integer accumulator.
  depth = 0                       # Nest expression depth.
  left_start, left_end = 0, nil   # Substring start and end for the left-hand
                                  # side of a binary operation.
  binary_operations =             # Binary operations ordered by precedence:
    { '*' => ->(n, m){ n * m } ,  #   1. Multiplication, and
      '+' => ->(n, m){ n + m } }  #   2. Addition.
  str.chars.each_with_index do |c,i|
    # Skip over a subexpression, recording only its start and end indices.
    if c=='('
      left_start = depth==0 ? i+1 : left_start
      depth -= 1
    elsif c==')'
      depth += 1
      left_end = depth==0 ? i-1 : left_end
    elsif depth==0
      # Record an integer;
      if /[0-9]/.match(c)
        left_start ||= c
        n ||= 0
        n *= 10
        n += c.to_i
      # Otherwise match a binary operator.
      elsif binary_operations.has_key?(c)
        left_end = i-2
        # If `n` is not an integer, it is an unparsed subexpression.
        n ||= parse(str[left_start, left_end])
        # Parse the right-hand side of the binary operation.
        m = parse(str[i+1, str.length-i-1])
        # Combine them according to the operator.
        n = binary_operations[c].call(n, m)
        break
      else
        raise "Error: encountered '#{c}'"
      end
    end
  end
  # If `n` is unchanged, we may need to unwrap a layer of parentheses.
  n ||= parse(str[left_start,left_end])
end

tests =
  [ # Integer
    Proc.new { parse('123')     == 123 } ,
    # Nested expression
    Proc.new { parse('(123)')   == 123 } ,
    # Doubly-nested expression
    Proc.new { parse('((123))') == 123 } ,
    # Addition
    Proc.new { parse('1+2+3')   == 6   } ,
    # Multiplication
    Proc.new { parse('1*2*3')   == 6   } ,
    # Precedence
    Proc.new { parse('2*3+1')   == 7   } ]

puts tests.map { |t| t.call() }