Operator precedence without eval, in 20 lines of Ruby

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

The one-liner works and is disqualified in the same breath:

eval("2+3*4")   # => 14

eval compiles and runs whatever it is handed. On a string that came from a form field, a query parameter or a chat message, that is arbitrary code execution in your process, with your database credentials loaded. The interview question is not "can you evaluate arithmetic". It is "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 thing

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. One flat array that gets shorter until a single number is left. The rest of this article takes it apart piece by piece.

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. The result alternates operand, operator, operand, operator, operand, which is exactly the shape the reduction loop assumes.

The backslash in [+\-*/] escapes the hyphen so it is a literal - and not a character range. Using %r{} instead of // avoids having to escape the slash as well.

Numbers become Integers, operators stay Strings

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

tokens.map { |op| Integer(op, exception: false) || op }   # => [2, "+", 3, "*", 4]

Integer(str, exception: false) returns nil instead of raising when the string is not a number, so || op keeps the original token:

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

The obvious alternative is wrong:

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

tokens.map(&:to_i)   # => [2, 0, 3, 0, 4]
"+".to_i             # => 0

to_i never fails. It parses as far as it can and returns 0 when it can parse nothing, which silently turns every operator into a number and destroys the expression. Integer() is the strict parser. Use it whenever the input is untrusted and a non-number is a real possibility, not a formality.

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

Precedence is an array

operator_levels = [ %w[* /], %w[+ -] ]

That is the idea the rest of the code exists to serve. Precedence is not encoded in a grammar or in the structure of the algorithm. It is data: a list of groups, highest binding first. The outer each runs one full pass per group. Everything in group one is consumed before group two is looked at, which is exactly what "higher precedence" means.

Adding a level is one array entry. 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 the order of the receiver, with duplicates removed. Two properties matter here. The receiver order means the first element of the result is the operator of this level that appears earliest in the expression. The deduplication means two * in the expression collapse to one entry, so .first answers "which kind of operator do I handle next", not "how many are there". The loop handles the count by running until the intersection is empty.

Taking the leftmost operator on every iteration is what gives left associativity for free:

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

Run that through the loop and the trace is [6, "-", 3] then [3]. (10 - 4) - 3 is 3. 10 - (4 - 3) would be 9. Nothing in the code mentions associativity. It falls out of always picking the leftmost match.

The three-cell splice

Once you know the operator, Array#index finds its position, and the three cells around it collapse into one:

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

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

ops.delete_at(operator_index)               # => "*"
ops                                         # => [2, "+", 3, 4]

operand = ops.delete_at(operator_index)     # => 4
ops                                         # => [2, "+", 3]

ops[left_operand_index] = ops[left_operand_index].public_send("*", operand)
ops                                         # => [2, "+", 12]

The second delete_at uses the same index as the first. After the operator is removed, the right operand has slid down into the slot the operator occupied, so operator_index now points at it. The left operand never moves, so operator_index - 1 computed before the deletions is still valid after them. Three cells in, one cell out, array shorter by two.

Array#index returns the first match, which is why duplicate operators are not a problem: each pass of the loop consumes the leftmost one, then the next iteration finds the next leftmost.

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 mapping "+" to an addition, no lambda table. The token is the code.

That looks like the dangerous part, and it is worth being precise about why it is not. The security boundary is the regex, not public_send. The only strings that can ever reach public_send are the four the pattern ([+\-*/]) can produce, because split cannot emit a separator the pattern did not match. If you later widen that pattern, or read the operator from anywhere else, the boundary moves with it.

public_send is still the right habit over send, because it costs nothing and it stops the private API from being reachable if the boundary ever leaks:

2.public_send("puts", "hi")   # NoMethodError: private method 'puts' called for an instance of Integer
2.send("puts", "hi")          # prints hi

Reach for send when you deliberately want a private method. Everywhere else, especially anywhere a method name is derived from input, public_send.

The trace

The p ops inside the loop prints the array after every reduction. For "2+3*4":

[2, "+", 12]
[14]

Two reductions. The first pass over %w[* /] folds 3 * 4 into 12 and then finds no more multiplicative operators. The second pass folds 2 + 12 into 14. ops.first is 14.

Why two passes beat one

A single left-to-right pass gives 20: it adds 2 + 3 before it ever sees the *. The usual fix is a recursive descent parser with one method per precedence level, or a shunting-yard stack. Both work. Both are more code than this, and both bury the precedence table inside control flow.

Here the precedence table is visible in one line and the algorithm is indifferent to its contents. 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 does not change at all. With those two lines swapped in, "2+3**2*2" tokenizes as ["2", "+", "3", "**", "2", "*", "2"] and reduces to 20, and "7%4+1" reduces to 4. That is the property worth demonstrating in an interview: the thing most likely to change lives in data, not in code.

Where it breaks

The 20-line version is a whiteboard answer, and a good answer names its own limits. Wrapped as a method so the failures are easy to reproduce:

OPERATOR_LEVELS = [ %w[* /], %w[+ -] ]
OPERATOR_PATTERN = %r{([+\-*/])}

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

  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(operator, operand)
    end
  end

  ops.first
end

Unary minus. A leading operator makes split emit an empty first field, and the empty string is not a number, so it survives the map! as a String:

"-2+3".split(OPERATOR_PATTERN)   # => ["", "-", "2", "+", "3"]
calculate("-2+3")                # NoMethodError: undefined method '-' for an instance of String

Parentheses. The pattern does not match them, so they stay glued to their neighbors and the operands are no longer numbers. String#* and String#+ then happily produce nonsense instead of an error:

"(2+3)*4".split(OPERATOR_PATTERN)   # => ["(2", "+", "3)", "*", "4"]
calculate("(2+3)*4")                # => "(23)3)3)3)"

Integer division. 4 is an Integer, so / is integer division:

calculate("10/4")   # => 2

Exponentiation. ** is two separate * matches with an empty field between them, and it is not in operator_levels anyway:

"2**3".split(OPERATOR_PATTERN)   # => ["2", "*", "", "*", "3"]
calculate("2**3")                # TypeError: String can't be coerced into Integer

Spaces survive, by accident. This one is worth checking rather than assuming. The tokens keep their padding, but Integer() tolerates leading and trailing whitespace, so the operands still parse:

"2 + 3 * 4".split(OPERATOR_PATTERN)   # => ["2 ", "+", " 3 ", "*", " 4"]
Integer("2 ", exception: false)       # => 2
calculate("2 + 3 * 4")                # => 14

Whitespace inside a number is still fatal, and relying on the accident is a bad idea. Strip it:

Integer("1 000", exception: false)   # => nil

Extending it to a real calculator

The video demonstrates a fuller calculator: "(2+3)*4" gives 20, "10/4" gives 2.5, and "-3+2*(1+1)" gives 1. What follows is our own implementation of that behavior, not a transcription of the video's source. Four changes, and the reduction loop is untouched:

1. Strip whitespace up front.
2. Add ( and ) to the token pattern, and reduce the innermost parenthesized run first.
3. Fold a minus into the number after it when there is no left operand, which is exactly the case where split produced an empty field.
4. Route / through quo for exact arithmetic, and normalize the result at the very end.

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("4/2")         # => 2
calculate("-3+2*(1+1)")  # => 1
calculate("10 - 4 - 3")  # => 3
calculate("2*-3")        # => -6
calculate("1/(10/4)")    # => 0.4

Three details in there are worth pointing at.

fold_unary_minus uses the empty field as its signal. split emits "" exactly where an operator has no left operand, at the start of the string and directly after ( or another operator:

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

So the rule "an empty field, then -, then a number, becomes a negative number" needs no lookbehind and no state machine. Empty fields that are not followed by a minus are dropped.

evaluate finds the first ), scans backwards with rindex for the ( that matches it, and replaces the whole slice including both brackets with the reduced value. That slice can contain no brackets by construction, so reduce sees a flat array exactly like the original algorithm did. The while repeats until no ) is left.

Division goes through quo, which returns an exact Rational, so 10 / 4 is (5/2) rather than 2 and no precision is lost in intermediate steps. normalize runs once at the end: a Rational with denominator 1 becomes an Integer, anything else becomes a Float. That is why 4/2 prints 2 and 10/4 prints 2.5. Keeping the exactness until the last moment is what makes calculate("1/(10/4)") return 0.4 instead of 0.

Why this answers the question well

Four things an interviewer is listening for, and this version has all of them.

It refuses eval for the right reason, and can say what the reason is: the input is untrusted, and the fix is that it never becomes code.

It puts the varying part in data. Precedence is an array of arrays, the operator dispatch is a hash, and the algorithm reads the same regardless of what is in them.

It knows where it breaks. Unary minus, parentheses, integer division and ** are all named, with the mechanism for each, before anyone asks.

It extends without rewriting. Parentheses, negative numbers and exact division were three helpers around the same reduction loop.

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.