【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パーサーも出来るのでは!?