Ruby: postfix expressions

This entry is going to use the tokenizer from Ruby and Fiber and present the code that evaluates the expressions.

The evaluator

We start with a first test that describes what kind of API we want.

test_evaluator.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

require 'test/unit'
require 'stringio'

require 'evaluator'

class TokenizerTests < Test::Unit::TestCase

  def test_addition
    
    assert_equal [7], @evaluator.compute(StringIO.new('3 4 +'))
    
  end

  def setup
    @evaluator = Evaluator.new
  end
  
end

The Evaluator class should have a compute method which returns the result of the expression evaluation. The expression is given as an IO stream. The result is the stack (an Array) because an expression could produce several results. For instance 3 1 + 5 7 - produces two results (4 and -2).

The compute method is going to call the tokenizer’s next method pushing operands on its stack and sending operators to itself to apply the operation.

evaluator.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

require 'tokenizer'

class Evaluator

  def initialize
    @stack = []
  end
  
  def compute expr
    
    @tokenizer = Tokenizer.new(expr)
    
    loop do
      
      type, token = @tokenizer.next
      
      break unless token

      case type
      
        when :error
          @stack.clear
          @stack << [:error, token]
          break
          
        when :operator
          break if self.send(token) == :error
        
        when :operand
          @stack << token
          
      end
      
    end

    expr.close
    
    @stack
    
  end
  
  private
  
  def pop_operands
    
    if @stack.length < 2
      @stack.clear
      @stack << [:error, "Missing operands at line #{@tokenizer.lineno}"]
      return :error
    end
    
    b = @stack.pop
    a = @stack.pop
    
    return a, b
    
  end
  
  [:+, :-, :*, :/].each do |op|
  
    define_method(op) do
    
      a, b = pop_operands
    
      return :error if a == :error
    
      @stack << a.send(op, b)
      
    end
    
  end
  
end
require 'tokenizer'

class Evaluator

  def initialize
    @stack = []
  end
  
  def compute expr
    
    @tokenizer = Tokenizer.new(expr)
    
    loop do
      
      type, token = @tokenizer.next
      
      break unless token

      case type
      
        when :error
          @stack.clear
          @stack << [:error, token]
          break
          
        when :operator
          break if self.send(token) == :error
        
        when :operand
          @stack << token
          
      end
      
    end

    expr.close
    
    @stack
    
  end
  
  private
  
  [:+, :-, :*, :/].each do |op|
  
    define_method(op) do
    
      a, b = pop_operands
    
      return :error if a == :error
    
      @stack << a.send(op, b)
      
    end
    
  end
  
end

Line 11 creates the tokenizer. Next starts an endless loop.

Line 15 asks for the next token, if the token is nil the code breaks the loop (line 17).

At line 19 we check the token type to decide what to do:

After line 42 we are going to add the operators methods that are only visible to the compute method.

Because all operators require two operands we add a common method that checks and returns the operands (pop_operands).

evaluator.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

  def pop_operands
    
    if @stack.length < 2
      @stack.clear
      @stack << [:error, "Missing operands at line #{@tokenizer.lineno}"]
      return :error
    end
    
    b = @stack.pop
    a = @stack.pop
    
    return a, b
    
  end
  
  def +
    
    a, b = pop_operands
    
    return :error if a == :error
    
    @stack << a + b
    
  end

The test should pass now.

$> ruby  test_evaluator.rb
Loaded suite /tmp/release/fiber/test_evaluator
Started
.

Finished in 0.000513458 seconds.
------
1 tests, 1 assertions, 0 failures, 0 errors, 0 pendings, 0 omissions, 0 notifications
100% passed
------
1947.58 tests/s, 1947.58 assertions/s

We can add tests for all the operators.

test_evaluator.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

  def test_substraction
    
    assert_equal [9], @evaluator.compute(StringIO.new('11 2 -'))
    
  end

  def test_mutliplication
    
    assert_equal [33], @evaluator.compute(StringIO.new('3 11 *'))
    
  end

  def test_division
    
    assert_equal [7], @evaluator.compute(StringIO.new('21 3 /'))
    
  end

Operators implementation follow the same pattern as addition.

evaluator.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

  def -
    
    a, b = pop_operands
    
    return :error if a == :error
    
    @stack << a - b
    
  end
  
  def *
    
    a, b = pop_operands
    
    return :error if a == :error
    
    @stack << a * b
    
  end
  
  def /
    
    a, b = pop_operands
    
    return :error if a == :error
    
    @stack << a / b
    
  end

Make the run:

$> ruby  test_evaluator.rb
Loaded suite /tmp/release/fiber/test_evaluator
Started
....

Finished in 0.000902319 seconds.
------
4 tests, 4 assertions, 0 failures, 0 errors, 0 pendings, 0 omissions, 0 notifications
100% passed
------
4433.02 tests/s, 4433.02 assertions/s

Testing error cases

For tests completeness we also need to write tests for error cases.

test_evaluator.rb
1
2
3
4
5
6
7
8
9
10
11

  def test_missing_operand_error
    assert_equal :error, @evaluator.compute(StringIO.new('3 +'))[0][0]
  end
  
  def test_invalid_number_error
    assert_equal :error, @evaluator.compute(StringIO.new('3.5 2 +'))[0][0]
  end
  
  def test_invalid_token_error
    assert_equal :error, @evaluator.compute(StringIO.new('22 a +'))[0][0]
  end

The assertions look strange because we store errors in arrays and push them on the stack…

$> ruby  test_evaluator.rb
Loaded suite /tmp/release/fiber/test_evaluator
Started
.......

Finished in 0.001408466 seconds.
------
7 tests, 7 assertions, 0 failures, 0 errors, 0 pendings, 0 omissions, 0 notifications
100% passed
------
4969.95 tests/s, 4969.95 assertions/s

Using the evaluator

We can use the evaluator on a command line with a simple evaluate method or pass it a string to evaluate.

eval_console.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

require 'stringio'
require 'evaluator'

def evaluate

  evaluator = Evaluator.new
  
  print "> "

  $stdin.each_line do |line|
  
    puts evaluator.compute(StringIO.new(line))

    print "> "
  
  end
  
end
  
source = "
  1 3 + 2 * 5 -
  21 3 / 6 +
  33 * 6 +
"

puts Evaluator.new.compute(StringIO.new(source))

The evaluate method (line 4) creates an Evaluator end loops reading lines from the console (line 10). Each line is passed to the Evaluator. We could pass the $stdin object to the evaluator but we want to prompt the user after each line.

After line 20 we evaluate a string.

$> ruby  eval_console.rb
3
435

Conclusion

The interesting part here is the way the operators are implemented: the tokenizer returns symbols used as messages send to the evaluator itself.

The operators implementation shows some kind of code duplication and the tests are pretty ugly to read. We present some improvements in the next entry (Postfix expressions revisited) that are very rubish…