右から左に結合する演算子あっさりできた

というか、さっき投稿したのにはバグが潜んでいた。

next_token = @list[i+1]
token = dest.list[dest_ptr]
while rop_end?( rs_stack, brackets_level, token, next_token )

ではnext_tokenとtokenがループ毎に更新されない。

while rop_end?( rs_stack, brackets_level, dest.list[dest_ptr], @list[i+1] )

とかにしないといけなかった。

---

先読みした次の演算子が同じ右から左の結合規則の優先度であれば、右オペレータは終了していないと判断するようにしました。

1**2**3
 1.0|
 1.0|**
 1.0 2.0|**
 1.0 2.0|** **
 1.0 2.0 3.0|** **
 1.0 2.0 3.0 **|**
 1.0 2.0 3.0 ** **|
 ( 1.0 ** ( 2.0 ** 3.0 ) )
1.0

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 } ),
	}
	
	# 右から左への結合規則の演算子の優先順位
	OPERATORS_IS_RIGHT_ASSOCIATIVE = { 4 => true }
	OPERATORS_IS_RIGHT_ASSOCIATIVE.default = false
	
	class TokenType
		def initialize( regex )
			@regex = regex
			@prev_white_list = []
		end
		
		attr_reader :regex
		attr_accessor :prev_white_list
		
		to_regexp = proc {|array| Regexp.new( 
			array.sort_by {|v| -v.size }.map{|v| Regexp.escape(v) }.join( '|' ) ) }
		
		SPACE           = new( /\s+/ )
		BINARY_OPERATOR = new( to_regexp.call( BINARY_OPERATORS.keys ) )
		UNARY_OPERATOR  = new( to_regexp.call( UNARY_OPERATORS.keys ) )
		NUM             = new( /-?[0-9]+(?:\.[0-9]+)?/ )
		LEFT_BRACKETS   = new( /\(/ )
		RIGHT_BRACKETS  = 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 += (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|
				while rop_end?( rs_stack, brackets_level, dest.list[dest_ptr], @list[i+1] )
					puts dest.inspect( dest_ptr )
					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
			
			if next_token_priority == token_priority && OPERATORS_IS_RIGHT_ASSOCIATIVE[token_priority]
				return false
			end
			
			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