Expression evaluator with Shunting-Yard algorithm

Question

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]

Answer 1

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