Expression evaluator with Shunting-Yard algorithm

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  @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|

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

StackExchange Code Review Q#156478, answer score: 2