Gray Soft / Tags / For Fun

22

SEP
2014

A Regex Can't Match Balanced Parentheses

Can we do math with regular expressions?

#!/usr/bin/env ruby -w

def build_preparation_regex(number_regex, ops)
  %r{
    (?<number>             #{number_regex}                                   ){0}
    (?<operator>           [#{ops.map(&Regexp.method(:escape)).join}]        ){0}
    (?<term_operator_term> \g<term> \s* \g<operator> \s* \g<term>            ){0}
    (?<term>               \g<number> | \( \s* \g<term_operator_term> \s* \) ){0}

    \g<term_operator_term>(?=\s*\z|[^)])
  }x
end

NUMBER_REGEX               = %r{
  -?            # an optional minus
  \d+           # an integer
  (?: \. \d+)?  # an optional fractional bit
}x
PREPARE_MULT_AND_DIV_REGEX = build_preparation_regex(NUMBER_REGEX, %w[* /])
PREPARE_ADD_AND_SUB_REGEX  = build_preparation_regex(NUMBER_REGEX, %w[* / + -])
CHECK_REGEX                = %r{
  \A                   # the start of the expression
  (?<term>             # a term, which is:
    #{NUMBER_REGEX}    # a number
    |                  # or
    \( \s*             # a parenthesized group of
      \g<term>         # a term
      \s* [*/+\-] \s*  # an operator
      \g<term>         # and another term
    \s* \)             # the end of the parenthesized group
  )
  \z                   # the end of the expression
}x
MATH_REGEX                 = %r{
  \( \s*
  (?<left>     #{NUMBER_REGEX} )
  \s*
  (?<operator> [*/+\-]         )
  \s*
  (?<right>    #{NUMBER_REGEX} )
  \s* \)
}x

verbose = ARGV.delete("-v")
problem = ARGV.first.strip or abort "USAGE:  #{$PROGRAM_NAME} MATH_EXPRESSION"
steps   = [ ]

[PREPARE_MULT_AND_DIV_REGEX, PREPARE_ADD_AND_SUB_REGEX].each do |preparation|
  loop do
    steps << problem.dup if verbose
    problem.sub!(preparation) { |term| "(#{term})" } or break
  end
end

problem =~ CHECK_REGEX or abort "Error:  Invalid expression"

solution = problem.dup
loop do
  steps << solution.dup if verbose
  solution.sub!(MATH_REGEX) {
    $~[:left].to_f.public_send($~[:operator], $~[:right].to_f)
  } or break
end

puts steps.uniq[0..-2] if verbose
puts solution.sub(/\.0+\z/, "")

19

SEP
2014

"You can't parse [X]HTML with regex."

The only explanation I'll give for the following code it to provide this link to my favorite Stack Overflow answer.

#!/usr/bin/env ruby -w

require "open-uri"

URL    = "http://stackoverflow.com/questions/1732348/" +
         "regex-match-open-tags-except-xhtml-self-contained-tags"
PARSER = %r{
  (?<doctype_declaration>
    <!DOCTYPE\b (?<doctype> [^>]* ) >
  ){0}
  (?<comment>
    <!-- .* -->
  ){0}

  (?<script_tag>
    < \s* (?<tag_name> script ) \s* (?<attributes> [^>]* > )
      (?<script> .*? )
    < \s* / \s* script \s* >
  ){0}
  (?<self_closed_tag>
    < \s* (?<tag_name> \w+ ) \s* (?<attributes> [^>]* / \s* > )
  ){0}
  (?<unclosed_tag>
    < \s*
    (?<tag_name> link | meta | br | input | hr | img ) \b
    \s*
    (?<attributes> [^>]* > )
  ){0}
  (?<open_tag>
    < \s* (?<tag_name> \w+ ) \s* (?<attributes> [^>]* > )
  ){0}
  (?<close_tag>
    < \s* / \s* (?<tag_name> \w+ ) \s* >
  ){0}

  (?<attribute>
    (?<attribute_name> [-\w]+ )
    (?: \s* = \s* (?<attribute_value> "[^"]*" | '[^']*' | [^>\s]+ ) )? \s*
  ){0}
  (?<attribute_list>
    \g<attribute>
    (?= [^>]* > \z )  # attributes keep a trailing > to disambiguate from text
  ){0}

  (?<text>
    (?! [^<]* /?\s*> \z )  # a guard to prevent this from parsing attributes
    [^<]+
  ){0}

  \G
  (?:
    \g<doctype_declaration>
    |
    \g<comment>
    |
    \g<script_tag>
    |
    \g<self_closed_tag>
    |
    \g<unclosed_tag>
    |
    \g<open_tag>
    |
    \g<attribute_list>
    |
    \g<close_tag>
    |
    \g<text>
  )
  \s*
}mix

def parse(html)
  stack = [{attributes: [ ], contents: [ ], name: :root}]
  loop do
    html.sub!(PARSER, "") or break
    if $~[:doctype_declaration]
      add_to_tree(stack.last, "DOCTYPE", $~[:doctype].strip)
    elsif $~[:script_tag]
      add_to_stack(stack, $~[:tag_name], $~[:attributes], $~[:script])
    elsif $~[:self_closed_tag] || $~[:unclosed_tag] || $~[:open_tag]
      add_to_stack(stack, $~[:tag_name], $~[:attributes], "", $~[:open_tag])
    elsif $~[:close_tag]
      stack.pop
    elsif $~[:text]
      stack.last[:contents] << $~[:text]
    end
  end
  stack.pop
end

def add_to_tree(branch, name, value)
  if branch.include?(name)
    branch[name]  = [branch[name]] unless branch[name].is_a?(Array)
    branch[name] << value
  else
    branch[name] = value
  end
end

def add_to_stack(stack, tag_name, attributes_html, contents, open = false)
  tag = { attributes: parse_attributes(attributes_html),
          contents:   [contents].reject(&:empty?),
          name:       tag_name }
  add_to_tree(stack.last, tag_name, tag)
  stack.last[:contents] << tag
  stack                 << tag if open
end

def parse_attributes(attributes_html)
  attributes = { }
  loop do
    attributes_html.sub!(PARSER, "") or break
    add_to_tree(
      attributes,
      $~[:attribute_name],
      ($~[:attribute_value] || $~[:attribute_name]).sub(/\A(["'])(.*)\1\z/, '\2')
    )
  end
  attributes
end

def convert_to_bbcode(node)
  if node.is_a?(Hash)
    name = node[:name].sub(/\Astrike\z/, "s")
    "[#{name}]#{node[:contents].map { |c| send(__method__, c) }.join}[/#{name}]"
  else
    node
  end
end

html = open(URL, &:read).strip
ast  = parse(html)
puts ast["html"]["body"]["div"]
  .find { |div| div[:attributes]["class"] == "container"      }["div"]
  .find { |div| div[:attributes]["id"]    == "content"        }["div"]["div"]
  .find { |div| div[:attributes]["id"]    == "mainbar"        }["div"]
  .find { |div| div[:attributes]["id"]    == "answers"        }["div"]
  .find { |div| div[:attributes]["id"]    == "answer-1732454" }["table"]["tr"]
  .first["td"]
  .find { |div| div[:attributes]["class"] == "answercell"     }["div"]["p"]
  .first[:contents]
  .map(&method(:convert_to_bbcode))  # to reach a wider audience
  .join