【Ruby】【アルゴリズム】数式解析（字句解析・構文解析）。右結合あり。操車場アルゴリズム

スタックの勉強をしたときから気になっている、
XMLパーサーの実装（Hamlとか）にチャレンジしてみようと。
　
まずは高らかに宣戦布告（師匠に）。

今日はパーサーを作ります！！！

あら、、、
パーサーの作り方はどっかで調べたの？

う。。。

調べてもあんまり発見できず。
スタックを使ったらなんとかならないかなーくらいのイメージなんですが。

スタックは使うけど、
まず字句解析して次に構文解析して、最後に意味解析するのが普通の流れ。
単純なHTMLを単にパースしたいだけなら、意味解析は不要やろうけど。

うひょー。。。。
早くも負けそう

まじめにやりだすと、これまた深い世界なので、吐かないようにね、、

だって。

ビット演算も深淵を垣間見ました。。。

それよりももっと深いよ。

　
だって！
やばい！

字句解析・構文解析とは。

Wikiを読んで勉強。

なるほど。
まずは数式の解析が簡単そうだ。
演算子があるという点では、XMLパーサーとは違ったポイントがあるかもしれない。

逆ポーランド記法はこの間実装できたし、
まずは数式解析からやってみるぞ！

字句解析

http://saltheads.blog134.fc2.com/blog-entry-60.html
こちらのサイトを参考に。

ポイントは、"+"と"-"が単項演算子or二項演算しかを判断しているところ。

あとプログラムでべき乗を書くときは、
「2^3」じゃなくて「2**3」です！（嵌った）

require 'strscan'

def  lexical_analysis(str)
  s = StringScanner.new((str+" ").gsub!(/ /, ""))
  arr = []
  may_sign = true
  sign = ""
  while !s.eos?
    #次にマイナスがきたら単項演算子
    # +と-と数値 以外の場合は,次が単項演算子プラスマイナスの可能性
    if s.scan(/(\*\*)/)
      arr << s[0]
      may_sign = true
    end
    if s.scan(/(\*|\/|\%|\(|\))/) 
      arr << s[0]
      may_sign = true
    end
    if s.scan(/(\+|\-)/)
      if may_sign
        sign = s[0]
      else
        arr << s[0]
      end
    end
    if s.scan(/(\d+)/)
      arr << sign + s[0]
      sign = ""
      may_sign = false
    end
  end
  arr
end
p lexical_analysis "3 + 4 * 2 / ( -1 - 5 ) ** -2 ** 3

　
　
■実行結果

["3", "+", "4", "*", "2", "/", "(", "-1", "-", "5", ")", "**", "-2", "**", "3"]

よし。

構文解析

操車場アルゴリズムを元に実装

操車場アルゴリズム（そうしゃじょうあるごりずむ）は、計算機科学において、中置記法の数式を構文解析する技法である。

https://ja.wikipedia.org/wiki/%E6%93%8D%E8%BB%8A%E5%A0%B4%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

wikiを素直に実装

def left_associate?(operator)
  return false if operator == "**"
  true
end
def shunting_yard(arr)
  #大きいほど優先高
  priority = {"*"=>3, "/"=>3, "%"=>3, "+"=>2, "-"=>2, "**"=>4}
  result = []
  stack = [] #演算子トークン
  arr.each do |data|
    if data =~ /((\d+)|(\+\d+)|(\-\d+))/ #数値の場合
      result << data 
    elsif data =~ /(\()/ #左括弧の場合
      stack << data
    elsif data =~ /(\))/ #右括弧の場合
      exist = false
      while stack.length != 0
        a = stack.pop
        if a == "("
          exist = true
          break
        else
          result << a
        end
      end
      raise "kakko error" if !exist
    else #演算子の場合
      if stack.length != 0 && stack.last !="("
        if (left_associate?(data) && (priority[data] <= priority[stack.last])) or
            (!left_associate?(data) && (priority[data] < priority[stack.last]))
          result << stack.pop
        end
      end
      stack << data
    end 
  end
  #トークン読み込みが完了。
  return result if stack.nil?
  # 演算子トークンが残っている場合resultに移動する
  stack.reverse!
  stack.each do |ope|
    raise "kakko error" if ope =='(' || ope == ')'
    result << ope
  end
  result
end

#先ほどの字句解析の結果を引数に
p reverse_polish_notation = shunting_yard(["3", "+", "4", "*", "2", "/", "(", "-1", "-", "5", ")", "**", "-2", "**", "3"])

　
■実行結果

["3", "4", "2", "*", "-1", "5", "-", "-2", "3", "**", "**", "/", "+"]

よし

逆ポーランド法で計算

これは前やったから余裕

def _calc(num1, num2, operator)
  raise "argument is not correct" if num1.nil? || num2.nil?
  a = num1.to_f ; b = num2.to_f
  return a + b if operator == "+"
  return a - b if operator == "-" || operator == "\u2212"
  return a * b if operator == "*"
  return a / b if operator == "/"
  return a % b if operator == "%"
  return a ** b if operator == "**"
  raise "operator is not correct"
end
def calculate(datas)
  num_stack = []
  datas.each do |data|
    if data =~ /\d/
      num_stack << data 
    else
      a = num_stack.pop
      b = num_stack.pop
      num_stack << _calc(b, a, data)
    end
  end
    raise "argument is not correct" if num_stack.length != 1
    num_stack
end

コード全量

require 'strscan'

def  lexical_analysis(str)
  s = StringScanner.new((str+" ").gsub!(/ /, ""))
  arr = []
  may_sign = true
  sign = ""
  while !s.eos?
    #次にマイナスがきたら単項演算子
    # +と-と数値 以外の場合は,次が単項演算子プラスマイナスの可能性
    if s.scan(/(\*\*)/)
      arr << s[0]
      may_sign = true
    end
    if s.scan(/(\*|\/|\%|\(|\))/) 
      arr << s[0]
      may_sign = true
    end
    if s.scan(/(\+|\-)/)
      if may_sign
        sign = s[0]
      else
        arr << s[0]
      end
    end
    if s.scan(/(\d+)/)
      arr << sign + s[0]
      sign = ""
      may_sign = false
    end
  end
  arr
end

def left_associate?(operator)
  return false if operator == "**"
  true
end
def shunting_yard(arr)
  #大きいほど優先される
  priority = {"*"=>3, "/"=>3, "%"=>3, "+"=>2, "-"=>2, "**"=>4}
  result = []
  stack = [] #演算子トークン
  arr.each do |data|
    if data =~ /((\d+)|(\+\d+)|(\-\d+))/
      result << data 
    elsif data =~ /(\()/ #左括弧の場合
      stack << data
    elsif data =~ /(\))/ #右括弧の場合
      exist = false
      while stack.length != 0
        a = stack.pop
        if a == "("
          exist = true
          break
        else
          result << a
        end
      end
      raise "kakko error" if !exist
    else #演算子の場合
      if stack.length != 0 && stack.last !="("
        if (left_associate?(data) && (priority[data] <= priority[stack.last])) or
            (!left_associate?(data) && (priority[data] < priority[stack.last]))
          result << stack.pop
        end
      end
      stack << data
    end 
  end
  #トークン読み込みが完了. 演算子トークンが残っている場合resultに移動する
  return result if stack.nil?

  stack.reverse!
  stack.each do |ope|
    raise "kakko error" if ope =='(' || ope == ')'
    result << ope
  end
  result
end

def _calc(num1, num2, operator)
  raise "argument is not correct" if num1.nil? || num2.nil?
  a = num1.to_f ; b = num2.to_f
  return a + b if operator == "+"
  return a - b if operator == "-" || operator == "\u2212"
  return a * b if operator == "*"
  return a / b if operator == "/"
  return a % b if operator == "%"
  return a ** b if operator == "**"
  raise "operator is not correct"
end
def calculate(datas)
  num_stack = []
  datas.each do |data|
    if data =~ /\d/
      num_stack << data 
    else
      a = num_stack.pop
      b = num_stack.pop
      num_stack << _calc(b, a, data)
    end
  end
    raise "argument is not correct" if num_stack.length != 1
    num_stack
end

arr = lexical_analysis ("  3 + 4 * 2 / ( 1 - 5 ) ** 2 ** 3")
rpn =  reverse_polish_notation = shunting_yard(arr)
p calculate(rpn)   #<= wikiに載ってる問題

question = [
  "2+3*4",
  "2*3+4",
  "2*3*4",
  "(-5)",
  "(3+4)",
  "2*(3+4)",
  "2+(3-4)*5",
  "(3-4)*5",
  "(-3-4)*5",
  "(3-4)*(-5)",
  "(-3-4)*-5",
  "(-3-4)*-5-35",
  "(-3-4)*-5*2",
  "2*(3+4)",
  "2/3",
  "(3*8)/(8-2)",
]

question.each do |q|
  p calculate ( shunting_yard ( lexical_analysis( q ) ) ) 
   #<= 参照URLに載っている問題
end

　
■実行結果

[3.0001220703125]
[14.0]
[10.0]
[24.0]
["-5"]
[7.0]
[14.0]
[-3.0]
[-5.0]
[-35.0]
[5.0]
[35.0]
[0.0]
[70.0]
[14.0]
[0.6666666666666666]
[4.0]

ふー。
ここまで出来たらXMLパーサーも出来るのでは！？