main.rb

# 以下の BNF で表される数式が書かれたファイルを受け取り、数式をパースし、抽象構文木をJSON形式でファイルに出力します。
#
# expression ::= term | term "+" expression | term "-" expression
# term ::= factor | factor "*" term | factor "/" term
# factor ::= number | "(" expression ")"
# number ::= ("0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9")+

#
# Usage: 
# $ ruby main.rb src.txt dst.json
#
class ExpressionParser
  class ParseError < StandardError; end
  class Node; end

  class BinaryOperator < Node
    def initialize(left, operator, right)
      @left = left
      @operator = operator
      @right = right
    end

    def to_json
      %({"operator": "#{@operator}", "left": #{@left.to_json}, "right": #{@right.to_json}})
    end
  end

  class Integer < Node
    def initialize(value)
      @value = value
    end

    def to_json
      "#{@value}"
    end
  end

  ADD_SUB_OPERATOR = %w(+ -)
  MUL_DIV_OPERATOR = %w(* /)
  OPEN_PARENTHESES = '('
  CLOSE_PARENTHESES = ')'
  DIGIT = %w(0 1 2 3 4 5 6 7 8 9)

  def initialize(expression)
    @pointer = 0
    @expression = expression
  end

  def parse
    parse_expression!
  end

  private

  def parse_expression!
    left = parse_term!
    return left if parse_end?

    operator = pointed_character
    return left unless ADD_SUB_OPERATOR.include?(operator)

    @pointer += 1
    right = parse_expression!
    BinaryOperator.new(left, operator, right)
  end

  def parse_term!
    left = parse_factor!
    return left if parse_end?

    operator = pointed_character
    return left unless MUL_DIV_OPERATOR.include?(operator)

    @pointer += 1
    right = parse_term!
    BinaryOperator.new(left, operator, right)
  end

  def parse_factor!
    if pointed_character == OPEN_PARENTHESES
      @pointer += 1
      expression = parse_expression!
      raise ParseError unless pointed_character == CLOSE_PARENTHESES
      @pointer += 1
      return expression
    else
      parse_number!
    end
  end

  def parse_number!
    raise ParseError unless DIGIT.include?(pointed_character)

    value = pointed_character.to_i
    @pointer += 1

    while DIGIT.include?(pointed_character)
      value *= 10
      value += pointed_character.to_i
      @pointer += 1
    end

    Integer.new(value)
  end

  def pointed_character
    @expression[@pointer]
  end

  def parse_end?
    @pointer == @expression.length
  end
end

unless ARGV.size == 2
  puts 'usage: ruby main.rb SRC DST'
  exit 1
end

src_file = File.open(ARGV[0], 'r')
dst_file = File.open(ARGV[1], 'w')

expression = src_file.readline.chomp
ast = ExpressionParser.new(expression).parse.to_json
dst_file.puts ast

src_file.close
dst_file.close