Module: Purple::Infix

Defined in:
lib/purple/infix.rb

Defined Under Namespace

Modules: PrecedenceTable

Class Method Summary collapse

Class Method Details

.process_infix(unordered) ⇒ Object

apply associativity rules and order of precedence to an sexp.

e.g. this input:

[ [:int, 5], :-, [:int, 2], :-, [:int, 1] ]

becomes:

[ :-, [:-, [:int, 5], [:int, 2]], [:int, 1] ]



10
11
12
 
# File 'lib/purple/infix.rb', line 10

def self.process_infix(unordered)
  rpn(shunting_yard unordered)
end

.rpn(input) ⇒ Object 



44
45
46
47
48
49
50
51
52
53
54
55
 
# File 'lib/purple/infix.rb', line 44

def self.rpn(input)
  results = []
  input.each do |object|
    if PrecedenceTable.infix_operator? object
      r, l = results.pop, results.pop
      results << [object, l, r]
    else
      results << object
    end
  end
  results.first
end

.shunting_yard(input) ⇒ Object

given an infix expression, apply precedence and associativity result is in RPN en.wikipedia.org/wiki/Shunting-yard_algorithm



60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
 
# File 'lib/purple/infix.rb', line 60

def self.shunting_yard(input)
  [].tap do |rpn|
    operator_stack = []
    input.each do |object|
      if PrecedenceTable.infix_operator? object
        op1 = object
        op1_left = PrecedenceTable.lookup(op1).associativity ==  :left
        op1_prec = PrecedenceTable.lookup(op1).precedence
        rpn << operator_stack.pop while (op2 = operator_stack.last) &&
                                        (op2_prec = PrecedenceTable.lookup(op2).precedence) &&
                                        (op1_left ? op1_prec <= op2_prec : op1_prec < op2_prec)
        operator_stack << op1
      else
        rpn << object
      end
    end
    rpn << operator_stack.pop until operator_stack.empty?
  end
end