7
\$\begingroup\$

I am especially concerned about:

  • Correctness: Does my algorithm always output the correct answer given a correct input?
  • Readability: Is my algorithm easy to understand for an experienced Ruby programmer (or, in other words: how many WTFs does a experienced Ruby programmer say while reading my code?)

Performance is not a main goal (if I had performance as a main goal, I wouldn't use Ruby), yet I want to know if I did something really bad somewhere in my code.

My method to transform a string into a list of symbols (which is called symbolize) is really poor but it doesn't matter. It does not need to be reviewed. And yes, it accepts only positive numbers.

Shunting-Yard implementation

class ShuntingYard
  def initialize
    @precedence = {
      "(" => 0,
      ")" => 0,
      "+" => 1,
      "-" => 1,
      "*" => 2,
      "/" => 2,
      "^" => 3,
    }

    @associativity = {
      "+" => :left,
      "-" => :left,
      "*" => :left,
      "/" => :left,
      "^" => :right
    }
  end

  def symbolize input
    stripped = input.lstrip

    if stripped.size == 0 then
      []
    elsif is_operator stripped[0] then
      [stripped[0]].concat symbolize stripped[1..-1]
    else
      n = stripped[/\d+(\.\d+)?/, 0]
      [n.to_f].concat symbolize stripped[n.size..-1] 
    end
  end

  def parse input
    @stack = []
    @rpn = []

    (symbolize input).each do |symbol|
      shunt symbol
    end

    @rpn.concat @stack.reverse
  end

  def shunt symbol
    if not is_operator symbol then
      @rpn << symbol
    elsif symbol == "(" then
      @stack << symbol
    elsif symbol == ")" then
      until @stack.last == "("
        @rpn << @stack.pop
      end

      @stack.pop
    elsif @stack.empty? or @stack.last == "(" then
      @stack << symbol
    elsif is_higher_or_right symbol then
      @stack << symbol
    else 
      until @stack.empty? or (is_higher_or_right symbol)
        @rpn << @stack.pop
      end

      @stack << symbol
    end
  end

  def is_higher_or_right symbol
    higher = @precedence[symbol] > @precedence[@stack.last]
    equal = @precedence[symbol] == @precedence[@stack.last]
    right = @associativity[symbol] == :right

    higher or (equal and right)
  end

  def is_operator symbol
    not not @precedence[symbol]
  end
end

Interpreter implementation 

class Interpreter
  def initialize
    @eval = {
      "+" => lambda { |a, b| a + b },
      "-" => lambda { |a, b| a - b },
      "*" => lambda { |a, b| a * b },
      "/" => lambda { |a, b| a / b },
      "^" => lambda { |a, b| a ** b },
    }
  end

  def evaluate input
    result = []

    (ShuntingYard.new.parse input).each do |symbol|
      result << (if @eval[symbol] then
                  right = result.pop
                  left = result.pop
                  @eval[symbol].call left, right
                else
                  symbol
                end)
    end

    result.pop
  end
end

Some tests to easily run it all

inputs = {
  "15 * 2 - 30 / 3 + 7" => 27,
  "5 + ((1 + 2) * 4) - 3" => 14,
  "10 * (30 / (2 * 3 + 4) + 15)" => 180,
  "25 + (14 - (25 * 4 + 40 - (20 / 2 + 10)))" => -81,
}

interpeter = Interpreter.new

inputs.each do |input, expected|
  puts "Got:      #{input}"
  puts "Expected: #{expected}"
  puts "Result:   #{interpeter.evaluate input}"
  puts
end

For completeness, I am using this Ruby interpreter

ruby 2.3.1p112 (2016-04-26) [x86_64-linux-gnu]
\$\endgroup\$

1 Answer 1

Reset to default
2
\$\begingroup\$

This is a strong question with easy-to-read code. I'm impressed with it.

I will pick on formatting some, because that's easier than the substantive, but I don't get the feeling that there's are many real issues with this code.

Vertical whitespace in methods

It is my opinion that vertical whitespace in code is of limited value, makes the boundaries between methods less visually apparent, and can usually be replaced with stronger mechanisms for revealing meaning.

  def symbolize input
    stripped = input.lstrip

    if stripped.size == 0 then
      []
    ...
  end

Here, the purpose of the vertical whitespace is not apparent to me, so I cannot comment on what might replace it. Some alternatives:

  • Move the related lines into a method, or
  • Use a comment to indicate why the lines are special, or
  • Just get rid of the whitespace

Use parentheses when defining methods

Whether or not you use parentheses when calling methods, use them when defining methods. Prefer:

  def shunt(symbol)

to:

  def shunt symbol

Reasons:

  • If I recall, there are some argument declarations that just won't work without parentheses anyhow.
  • The parentheses help clue the eye in that a method declaration is happening.
  • At least one standards guide recommends this.

Omit then on most ifs

With a multi-line if (most if expressions):

    (ShuntingYard.new.parse input).each do |symbol|
      result << (if @eval[symbol]
                  right = result.pop
                  left = result.pop
                  @eval[symbol].call left, right
                else
                  symbol
                end)

If the parentheses around the if...else...end were driven by the then, then the parentheses can (and should) now be removed.

Use #map

This iterative code builds a new array based on an enumeration:

    result = []

    (ShuntingYard.new.parse input).each do |symbol|
      result << (if @eval[symbol] then
                  right = result.pop
                  left = result.pop
                  @eval[symbol].call left, right
                else
                  symbol
                end)

This could use #map instead (note: untested):

    result = (ShuntingYard.new.parse input).map do |symbol|
      if @eval[symbol]
        right = result.pop
        eft = result.pop
        @eval[symbol].call left, right
      else
        symbol
      end
    end
\$\endgroup\$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.