Operator precedence without eval, in 20 lines of Ruby

Here's the question. You get a string, "2+3*4". Return its value. The answer's 14, not 20, because * binds tighter than +. And you may not use eval.

eval("2+3*4") gives you 14 and disqualifies you in the same breath: it runs whatever it's handed, so on a string from a form field that's arbitrary code execution in your process, with your credentials loaded. The question isn't "can you evaluate arithmetic", it's "can you evaluate arithmetic when the input is hostile". So the string never becomes code. It becomes data, and you reduce the data.

The whole calculator, in twenty lines

operation = "2+3*4"
operator_levels = [ %w[* /], %w[+ -] ]
operator_pattern = %r{([+\-*/])}

ops = operation.split(operator_pattern)
ops.map! { |op| Integer(op, exception: false) || op }

operator_levels.each do |operators|
  loop do
    operator = (ops & operators).first   # the next operator of this level, leftmost first
    break unless operator

    operator_index = ops.index(operator)
    left_operand_index = operator_index - 1

    ops.delete_at(operator_index)
    operand = ops.delete_at(operator_index)
    ops[left_operand_index] = ops[left_operand_index].public_send(operator, operand)

    p ops                                # trace: the state after each reduction
  end
end

ops.first # => 14

No grammar, no tokenizer class, no AST, just one flat array that gets shorter until a single number is left. The p ops prints [2, "+", 12] and then [14], because the first pass consumes every * and / before the second pass ever sees the +.

Split, but keep the separators

String#split normally throws the separator away. Wrap the pattern in a capturing group and it keeps it:

"2+3*4".split(%r{[+\-*/]})     # => ["2", "3", "4"]
"2+3*4".split(%r{([+\-*/])})   # => ["2", "+", "3", "*", "4"]

That single pair of parentheses is the whole tokenizer, and the result alternates operand, operator, operand, which is exactly the shape the reduction loop assumes.

Numbers become Integers, operators stay Strings

Integer("3", exception: false)   # => 3
Integer("+", exception: false)   # => nil

["2", "+", "3"].map { |op| Integer(op, exception: false) || op }   # => [2, "+", 3]
["2", "+", "3"].map(&:to_i)                                        # => [2, 0, 3]

Integer(str, exception: false) hands back nil instead of raising when the string isn't a number, so || op keeps the token. The obvious alternative is the trap: to_i never fails, it returns 0 when it can parse nothing, so it silently turns every operator into a number and destroys the expression. Integer() is the strict parser.

After the map! the array mixes types on purpose: Integer means operand, String means operator. The type is the tag, and the whole design rests on that.

Precedence is an array, not a grammar

A single left-to-right pass gives you 20, because it adds 2 + 3 before it sees the *. The usual fixes, recursive descent with one method per level or a shunting-yard stack, both bury precedence inside control flow. Here it's data: [ %w[* /], %w[+ -] ], groups in binding order, and the outer each runs one full pass per group, so group one is entirely consumed before group two is looked at. That's what "higher precedence" means, and adding exponentiation and modulo is two edits, both of them declarations:

operator_levels = [ %w[**], %w[* / %], %w[+ -] ]
operator_pattern = %r{(\*\*|[+\-*/%])}   # `**` first, so it wins over a single `*`

The loop body doesn't change at all. "2+3**2*2" now reduces to 20 and "7%4+1" to 4, and changing the precedence of % is moving a string.

The leftmost operator of the current level

ops = [2, "+", 3, "*", 4, "-", 5, "*", 6]

ops & %w[* /]           # => ["*"]
ops & %w[+ -]           # => ["+", "-"]
(ops & %w[+ -]).first   # => "+"

Array#& returns the elements present in both arrays, in receiver order, with duplicates removed. Receiver order means the first element is the operator of this level standing earliest in the expression. Deduplication means two * collapse into one entry, so .first answers "which kind of operator do I handle next", not "how many are there", and the loop runs until the intersection comes back empty.

Picking the leftmost every time also buys left associativity: "10-4-3" comes out as 3, which is (10 - 4) - 3 and not the 9 of 10 - (4 - 3), with no code mentioning associativity.

Collapsing three cells into one

ops = [2, "+", 3, "*", 4]

operator_index = ops.index("*")            # => 3
left_operand_index = operator_index - 1    # => 2

ops.delete_at(operator_index)              # removes "*"
operand = ops.delete_at(operator_index)    # => 4
ops[left_operand_index] = ops[left_operand_index].public_send("*", operand)

ops   # => [2, "+", 12]

The second delete_at reuses the first one's index, which looks like a bug and isn't. Once the operator's gone, the right operand has slid down into the slot it occupied, so operator_index now points straight at it. The left operand never moves, so operator_index - 1, computed before either deletion, is still valid after both. Three cells in, one cell out.

The token is the method name

2.public_send("+", 3)   # => 5

In Ruby + is an ordinary method on Integer, so the string that came out of split is already the method name. No case statement, no lambda table. The token is the code.

That looks like the dangerous part, and it isn't. The security boundary is the regex, not public_send: the only strings that can reach it are the four ([+\-*/]) can produce, because split can't emit a separator the pattern didn't match, and the boundary moves the day you widen the pattern. public_send is still the right habit, because 2.send("puts", "hi") really does print, Kernel#puts being private on every object.

Where it breaks, and how to fix it

Twenty lines is a whiteboard answer, so name its limits. Set operation to each of these:

"-2+3"      # NoMethodError: undefined method '-' for an instance of String
"(2+3)*4"   # => "(23)3)3)3)"
"10/4"      # => 2
"2 + 3 * 4" # => 14, by accident

A leading operator makes split emit an empty first field, and "" isn't a number, so it survives the map! as a String and gets asked to subtract. Parentheses aren't in the pattern, so they stay glued to their neighbors and String#+ quietly produces nonsense. 10/4 is 2 because both sides are Integer. And "2**3".split(%r{([+\-*/])}) is ["2", "*", "", "*", "3"], two matches with an empty field wedged between them, which is why the wider pattern above alternates \*\* first.

The spaces case works by luck: Integer() tolerates leading and trailing whitespace, so "2 + 3 * 4" reduces to 14 unstripped. It won't tolerate whitespace inside the digits though, Integer("1 000", exception: false) is nil, so call delete(" ") up front.

Here's the version that handles all of it, reduction loop untouched:

OPERATOR_LEVELS = [ %w[* /], %w[+ -] ]
TOKEN_PATTERN   = %r{([+\-*/()])}
METHOD_FOR      = { "+" => :+, "-" => :-, "*" => :*, "/" => :quo }

def calculate(source)
  normalize(evaluate(tokenize(source.delete(" "))))
end

def tokenize(expression)
  tokens = expression.split(TOKEN_PATTERN)
  tokens.map! { |token| Integer(token, exception: false) || token }
  fold_unary_minus(tokens)
end

def fold_unary_minus(tokens)
  folded = []
  index  = 0

  while index < tokens.size
    if tokens[index] == "" && tokens[index + 1] == "-" && tokens[index + 2].is_a?(Integer)
      folded << -tokens[index + 2]
      index += 3
    elsif tokens[index] == ""
      index += 1
    else
      folded << tokens[index]
      index += 1
    end
  end

  folded
end

def evaluate(tokens)
  while (close_index = tokens.index(")"))
    open_index = tokens[0...close_index].rindex("(")
    tokens[open_index..close_index] = [ reduce(tokens[(open_index + 1)...close_index]) ]
  end

  reduce(tokens)
end

def reduce(ops)
  OPERATOR_LEVELS.each do |operators|
    loop do
      operator = (ops & operators).first
      break unless operator

      operator_index     = ops.index(operator)
      left_operand_index = operator_index - 1

      ops.delete_at(operator_index)
      operand = ops.delete_at(operator_index)
      ops[left_operand_index] = ops[left_operand_index].public_send(METHOD_FOR.fetch(operator), operand)
    end
  end

  ops.first
end

def normalize(value)
  return value unless value.is_a?(Rational)

  value.denominator == 1 ? value.numerator : value.to_f
end

calculate("2+3*4")       # => 14
calculate("(2+3)*4")     # => 20
calculate("10/4")        # => 2.5
calculate("-3+2*(1+1)")  # => 1
calculate("1/(10/4)")    # => 0.4

Three things there are worth pointing at. split emits "" exactly where an operator has no left operand, so that empty field is the unary-minus signal and fold_unary_minus needs no lookbehind and no state machine. The slice evaluate hands to reduce runs from the first ) back to the ( that rindex finds, so by construction it holds no brackets and reduce sees the same flat array it always did. And / goes through quo, staying an exact Rational until normalize runs once at the end, which is why calculate("1/(10/4)") is 0.4 and not 0.

Related quizzes

• Precedence rules: how Ruby groups x || y && "Rails".
• for precedence: what for does to the loop variable's scope.
• gsub precedence: the replacement argument wins over the block.