数式計算スクリプトをいじり中
また数式計算スクリプトをいじくってます。
右から左に結合する演算子とか、関数とか、変数とか、式の最適化とか色々やってみたいのです!
クラス構造を少し変更して、逆ポーランド記法→中置記法の変換を追加してみました。
class Calc class Operator def initialize( priority, proc ) @priority = priority @proc = proc end attr_reader :priority, :proc end BINARY_OPERATORS = { '**' => Operator.new( 4, proc{|a,b| a**b } ), '*' => Operator.new( 2, proc{|a,b| a*b } ), '/' => Operator.new( 2, proc{|a,b| a/b } ), '%' => Operator.new( 2, proc{|a,b| a%b } ), '+' => Operator.new( 1, proc{|a,b| a+b } ), '-' => Operator.new( 1, proc{|a,b| a-b } ), } UNARY_OPERATORS = { '+' => Operator.new( 5, proc{|a| +a } ), '-' => Operator.new( 3, proc{|a| -a } ), } class TokenType def initialize( regex ) @regex = regex @prev_white_list = [] end attr_reader :regex attr_accessor :prev_white_list to_regex = proc {|array| Regexp.new( array.sort_by {|v| -v.size }.map{|v| Regexp.escape(v) }.join( '|' ) ) } SPACE = TokenType.new( /\s+/ ) BINARY_OPERATOR = TokenType.new( to_regex.call( BINARY_OPERATORS.keys ) ) UNARY_OPERATOR = TokenType.new( to_regex.call( UNARY_OPERATORS.keys ) ) NUM = TokenType.new( /-?[0-9]+(?:\.[0-9]+)?/ ) LEFT_BRACKETS = TokenType.new( /\(/ ) RIGHT_BRACKETS = TokenType.new( /\)/ ) [NUM, UNARY_OPERATOR, LEFT_BRACKETS].each do |i| i.prev_white_list = [nil, LEFT_BRACKETS, BINARY_OPERATOR, UNARY_OPERATOR] end [BINARY_OPERATOR, RIGHT_BRACKETS].each do |i| i.prev_white_list = [NUM, RIGHT_BRACKETS] end def operator? self == BINARY_OPERATOR || self == UNARY_OPERATOR end def inspect { SPACE => 'SPACE', BINARY_OPERATOR => 'BINARY_OPERATOR', UNARY_OPERATOR => 'UNARY_OPERATOR', NUM => 'NUM', LEFT_BRACKETS => 'LEFT_BRACKETS', RIGHT_BRACKETS => 'RIGHT_BRACKETS' }[self] end end TOKEN_TYPES = class TokenType [SPACE, BINARY_OPERATOR, UNARY_OPERATOR, NUM, LEFT_BRACKETS, RIGHT_BRACKETS] end class Token def initialize( type, val = nil ) @type = type @val = val end attr_reader :type, :val def operator case @type when TokenType::BINARY_OPERATOR BINARY_OPERATORS[@val] when TokenType::UNARY_OPERATOR UNARY_OPERATORS[@val] end end end class Error < RuntimeError ; end def calculate( expr ) tokens = lex( expr ).to_postfix_notation p tokens.to_infix_notation return tokens.calculate end private def lex( expr ) tokens = InfixNotationTokens.new i = 0 prev_type = nil while expr[i] find = nil TOKEN_TYPES.each do |token_type| find = ( /\A#{token_type.regex}/ =~ expr[i..-1] ) unless token_type == TokenType::SPACE find = nil if find && !token_type.prev_white_list.include?( prev_type ) end next unless find case token_type when TokenType::BINARY_OPERATOR, TokenType::UNARY_OPERATOR tokens.list << Token.new( token_type, $& ) when TokenType::NUM tokens.list << Token.new( token_type, $&.to_f ) when TokenType::LEFT_BRACKETS, TokenType::RIGHT_BRACKETS tokens.list << Token.new( token_type ) end i += find + $&.size prev_type = token_type unless token_type == TokenType::SPACE break end raise Error, '構文エラーです' unless find end return tokens end class Tokens def initialize @list = [] end attr_accessor :list def inspect( ptr = nil ) ret = '' @list.each_with_index do |t,i| ret += ' ' if i != 0 ret += '| ' if ptr && i == ptr case t.type when TokenType::LEFT_BRACKETS ret += '(' when TokenType::RIGHT_BRACKETS ret += ')' when TokenType::UNARY_OPERATOR ret += t.val.to_s + '@' else ret += t.val.to_s end end ret += ' |' if ptr && @list.size == ptr return ret end end class InfixNotationTokens < Tokens def to_postfix_notation dest = PostfixNotationTokens.new dest_ptr = 0 prev_type = nil rs_stack = [] brackets_level = 0 rop_exit = proc do |i| next_token = @list[i+1] token = dest.list[dest_ptr] while rop_end?( rs_stack, brackets_level, token, next_token ) rs_stack.pop dest_ptr += 1 end end @list.each_with_index do |token, i| case token.type when TokenType::NUM dest.list.insert( dest_ptr, token ) dest_ptr += 1 if prev_type && prev_type.operator? # 右オペランドの場合 rop_exit.call( i ) end when TokenType::BINARY_OPERATOR, TokenType::UNARY_OPERATOR dest.list.insert( dest_ptr, token ) rs_stack.push( brackets_level ) when TokenType::LEFT_BRACKETS brackets_level += 1 when TokenType::RIGHT_BRACKETS raise Error, '不正な閉じカッコです' unless brackets_level > 0 brackets_level -= 1 rop_exit.call( i ) else raise Error, '不明なトークンです' end prev_type = token.type puts dest.inspect( dest_ptr ) end raise Error, '式が途中で終了しています' unless dest.list.size == dest_ptr raise Error, 'カッコが閉じられていません' unless brackets_level == 0 return dest end private # 右オペランドは終了している? def rop_end?( rs_stack, brackets_level, token, next_token ) return false unless rs_stack.last == brackets_level return true unless next_token && token return true unless [next_token, token].all? {|v| v.type.operator? } next_token_priority = next_token.operator.priority token_priority = token.operator.priority return next_token_priority <= token_priority end end class PostfixNotationTokens < Tokens def calculate stack = [] @list.each do |token| case token.type when TokenType::NUM stack.push( token.val ) when TokenType::BINARY_OPERATOR raise Error, 'オペランドが足りません' unless stack.size >= 2 b = stack.pop a = stack.pop raise Error, '不明な演算子です' unless BINARY_OPERATORS.key?( token.val ) stack.push BINARY_OPERATORS[token.val].proc.call( a, b ) when TokenType::UNARY_OPERATOR raise Error, 'オペランドが足りません' unless stack.size >= 1 a = stack.pop raise Error, '不明な演算子です' unless UNARY_OPERATORS.key?( token.val ) stack.push UNARY_OPERATORS[token.val].proc.call( a ) else raise Error, '不明なトークンです' end end raise Error, 'オペランドが足りないか、余っています' unless stack.size == 1 return stack[0] end def to_infix_notation dest = InfixNotationTokens.new stack = [] # 演算子が挿入されるべき位置 @list.each do |token| case token.type when TokenType::NUM dest.list << token stack.push( dest.list.size ) when TokenType::BINARY_OPERATOR raise Error, 'オペランドが足りません' unless stack.size >= 2 stack.pop pos = stack.pop dest.list.insert( pos, token ) dest.list.insert( stack.last || 0, Token.new( TokenType::LEFT_BRACKETS ) ) dest.list.insert( dest.list.size, Token.new( TokenType::RIGHT_BRACKETS ) ) stack.push( dest.list.size ) when TokenType::UNARY_OPERATOR raise Error, 'オペランドが足りません' unless stack.size >= 1 stack.pop dest.list.insert( stack.last || 0, token ) dest.list.insert( stack.last || 0, Token.new( TokenType::LEFT_BRACKETS ) ) dest.list.insert( dest.list.size, Token.new( TokenType::RIGHT_BRACKETS ) ) stack.push( dest.list.size ) else raise Error, '不明なトークンです' end end raise Error, 'オペランドが足りないか、余っています' unless stack.size == 1 return dest end end end calc = Calc.new while s = gets begin puts calc.calculate( s.chomp ) rescue Calc::Error => e puts "Error: #{e}" end end