Class: Calculus::Parser

Inherits:
StringScanner
  • Object
show all
Defined in:
lib/calculus/parser.rb

Overview

Parses string with expression or equation and builds postfix notation. It supprorts following operators (ordered by precedence from the highest to the lowest):

:sqrt, :exp

root and exponent operations. Could be written as \sqrt[degree]{radix} and x^y.

:div, :mul

division and multiplication. There are set of syntaxes accepted. To make division operator you can use num/denum or \frac{num}{denum}. For multiplication there accepted * and also two TeX symbols: \cdot and \times.

:plus, :minus

summation and substraction. Here you can use plain + and -

:eql

equals sign it has the lowest priority so it to be calculated in last turn.

Also it is possible to use parentheses for grouping. There are plain (, ) acceptable and also \(, \) which are differ only for latex diplay. Parser doesn’t distinguish these two styles so you could give expression with visually unbalanced parentheses (matter only for image generation. Consider the example:

Parser.new("(2 + 3) * 4").parse   #=> [2, 3, :plus, 4, :mul]
Parser.new("(2 + 3\) * 4").parse  #=> [2, 3, :plus, 4, :mul]

This two examples will yield the same notation, but make issue during display.

Numbers could be given as a floats and as a integer

Parser.new("3 + 4.0 * 4.5e-10")   #=> [3, 4.0, 4.5e-10, :mul, :plus]

Symbols could be just alpha-numeric values with optional subscript index

Parser.new("x_3 + y * E")         #=> ["x_3", "y", "E", :mul, :plus]

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(source) ⇒ Parser

Initialize parser with given source string. It could simple (native expression like 2 + 3 * (4 / 3), but also in TeX style <tt>2 + 3 cdot frac43.



50
51
52
53
54
 
# File 'lib/calculus/parser.rb', line 50

def initialize(source)
  @operators = {:sqrt => 3, :exp => 3, :div => 2, :mul => 2, :plus => 1, :minus => 1, :eql => 0}

  super(source.dup)
end

Instance Attribute Details

#operators ⇒ Object

Returns the value of attribute operators.



45
46
47
 
# File 'lib/calculus/parser.rb', line 45

def operators
  @operators
end

Instance Method Details

#fetch_token ⇒ Object

Fetch next token from source string. Skips any whitespaces matching regexp /\s+/ and returs nil at when meet the end of string.

Raises ParseError when encounter invalid character sequence.



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
132
133
134
135
136
137
138
139
140
141
 
# File 'lib/calculus/parser.rb', line 93

def fetch_token
  skip(/\s+/)
  return nil if(eos?)

  token = nil
  scanning = true
  while(scanning)
    scanning = false
    token = case
            when scan(/=/)
              :eql
            when scan(/\*|\\times|\\cdot/)
              :mul
            when scan(/\\frac\s*(?<num>\{(?:(?>[^{}])|\g<num>)*\})\s*(?<denom>\{(?:(?>[^{}])|\g<denom>)*\})/)
              num, denom = [self[1], self[2]].map{|v| v.gsub(/^{|}$/, '')}
              string[pos, 0] = "(#{num}) / (#{denom}) "
              scanning = true
            when scan(/\//)
              :div
            when scan(/\+/)
              :plus
            when scan(/\^/)
              :exp
            when scan(/-/)
              :minus
            when scan(/sqrt/)
              :sqrt
            when scan(/\\sqrt\s*(?<deg>\[(?:(?>[^\[\]])|\g<deg>)*\])?\s*(?<rad>\{(?:(?>[^{}])|\g<rad>)*\})/)
              deg = (self[1] || "2").gsub(/^\[|\]$/, '')
              rad = self[2].gsub(/^{|}$/, '')
              string[pos, 0] = "(#{rad}) sqrt (#{deg}) "
              scanning = true
            when scan(/\(|\\left\(/)
              :open
            when scan(/\)|\\right\)/)
              :close
            when scan(/[\-\+]? [0-9]+ ((e[\-\+]?[0-9]+)| (\.[0-9]+(e[\-\+]?[0-9]+)?))/x)
              matched.to_f
            when scan(/[\-\+]?[0-9]+/)
              matched.to_i
            when scan(/([a-z0-9]+(?>_[a-z0-9]+)?)/i)
              matched
            else
              raise ParserError, "Invalid character at position #{pos} near '#{peek(20)}'."
            end
  end

  return token
end

#parse ⇒ Object

Run parse cycle. It builds postfix notation (aka reverse polish notation). Returns array with operations with operands.

Parser.new("2 + 3 * 4").parse               #=> [2, 3, 4, :mul, :plus]
Parser.new("(\frac{2}{3} + 3) * 4").parse   #=> [2, 3, :div, 3, :plus, 4, :mul]

Raises:

  • (ArgumentError) 


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
 
# File 'lib/calculus/parser.rb', line 61

def parse
  exp = []
  stack = []
  while true
    case token = fetch_token
    when :open
      stack.push(token)
    when :close
      exp << stack.pop while operators.keys.include?(stack.last)
      stack.pop if stack.last == :open
    when :plus, :minus, :mul, :div, :exp, :sqrt, :eql
      exp << stack.pop while operators.keys.include?(stack.last) && operators[stack.last] >= operators[token]
      stack.push(token)
    when Numeric, String
      exp << token
    when nil
      break
    else
      raise ArgumentError, "Unexpected symbol: #{token.inspect}"
    end
  end
  exp << stack.pop while stack.last && stack.last != :open
  raise ArgumentError, "Missing closing parentheses: #{stack.join(', ')}" unless stack.empty?
  exp
end