Parsing/RPN/Ruby
< Parsing
Code for parsing and evaluating RPN expressions. See
<lang ruby>class RPNExpression
# Set up the table of known operators
Operator = Struct.new(:precedence, :associativity, :english, :ruby_operator)
class Operator
def left_associative?; associativity == :left; end
def <(other)
if left_associative?
precedence <= other.precedence
else
precedence < other.precedence
end
end
end
Operators = {
"+" => Operator.new(2, :left, "ADD", "+"),
"-" => Operator.new(2, :left, "SUB", "-"),
"*" => Operator.new(3, :left, "MUL", "*"),
"/" => Operator.new(3, :left, "DIV", "/"),
"^" => Operator.new(4, :right, "EXP", "**"),
}
# create a new object
def initialize(str)
@expression = str
@infix_tree = nil
@value = nil
end
attr_reader :expression
# convert an infix expression into RPN
def self.from_infix(expression)
debug "\nfor Infix expression: #{expression}\nTerm\tAction\tOutput\tStack"
rpn_expr = []
op_stack = []
tokens = expression.split
until tokens.empty?
term = tokens.shift
if Operators.has_key?(term)
op2 = op_stack.last
if Operators.has_key?(op2) and Operators[term] < Operators[op2]
rpn_expr << op_stack.pop
debug "#{term}\t#{Operators[op2].english}\t#{rpn_expr}\t#{op_stack}\t#{op2} has higher precedence than #{term}"
end
op_stack << term
debug "#{term}\tPUSH OP\t#{rpn_expr}\t#{op_stack}"
elsif term == "("
op_stack << term
debug "#{term}\tOPEN_P\t#{rpn_expr}\t#{op_stack}"
elsif term == ")"
until op_stack.last == "("
rpn_expr << op_stack.pop
debug "#{term}\t#{Operators[rpn_expr.last].english}\t#{rpn_expr}\t#{op_stack}\tunwinding parenthesis"
end
op_stack.pop
debug "#{term}\tCLOSE_P\t#{rpn_expr}\t#{op_stack}"
else
rpn_expr << term
debug "#{term}\tPUSH V\t#{rpn_expr}\t#{op_stack}"
end
end
until op_stack.empty?
rpn_expr << op_stack.pop
end
obj = self.new(rpn_expr.join(" "))
debug "RPN = #{obj.to_s}"
obj
end
# calculate the value of an RPN expression def eval return @value unless @value.nil?
debug "\nfor RPN expression: #{expression}\nTerm\tAction\tStack"
stack = []
expression.split.each do |term|
if Operators.has_key?(term)
a, b = stack.pop(2)
raise ArgumentError, "not enough operands on the stack" if b.nil?
a = a.to_f if term == "/"
op = (term == "^" ? "**" : term)
stack.push(a.method(op).call(b))
debug "#{term}\t#{Operators[term].english}\t#{stack}"
else
begin
number = Integer(term) rescue Float(term)
rescue ArgumentError
raise ArgumentError, "cannot handle term: #{term}"
end
stack.push(number)
debug "#{number}\tPUSH\t#{stack}"
end
end
@value = stack.pop
debug "Value = #@value"
@value
end
private # convert an RPN expression into an AST def to_infix_tree return @infix_tree unless @infix_tree.nil?
debug "\nfor RPN expression: #{expression}\nTerm\tAction\tStack"
stack = []
expression.split.each do |term|
if Operators.has_key?(term)
a, b = stack.pop(2)
raise ArgumentError, "not enough operands on the stack" if b.nil?
op = InfixNode.new(term)
op.left = a
op.right = b
stack.push(op)
debug "#{term}\t#{Operators[term].english}\t#{stack.inspect}"
else
begin
Integer(term) rescue Float(term)
rescue ArgumentError
raise ArgumentError, "cannot handle term: #{term}"
end
stack.push(InfixNode.new(term))
debug "#{term}\tPUSH\t#{stack.inspect}"
end
end
@infix_tree = stack.pop
end
public
# express the AST as a string
def to_infix
expr = to_infix_tree.to_s
debug "Infix = #{expr}"
expr
end
# express the AST as a string, but in a form that allows Ruby to evaluate it
def to_ruby
expr = to_infix_tree.to_ruby
debug "Ruby = #{expr}"
expr
end
def to_s expression end
private
class InfixNode
def initialize(value)
@value = value
@left = nil
@right = nil
end
attr_reader :value
attr_accessor :left, :right
def leaf?
left.nil? and right.nil?
end
def to_s; to_string(false); end def to_ruby; to_string(true); end
def to_string(to_ruby)
result = []
result << display_child(left, to_ruby, (to_ruby and value == "/"))
result << (to_ruby ? Operators[value].ruby_operator : value)
result << display_child(right, to_ruby)
result.join(" ")
end
def display_child(child, to_ruby, need_float = false)
result = if child.leaf?
child.value
elsif Operators[child.value].precedence < Operators[value].precedence
"( #{child.to_string(to_ruby)} )"
else
child.to_string(to_ruby)
end
result += ".to_f" if need_float
result
end
def inspect
str = "node[#{value}]"
str << "<left=#{left.inspect}, right=#{right.inspect}>" unless leaf?
str
end
end
end
def debug(msg)
puts msg if $DEBUG
end
require 'test/unit'
class TestRPNExpression < Test::Unit::TestCase
def setup @rpn_expr = "3 4 2 * 1 5 - 2 3 ^ ^ / +" @infix_expr = "3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3" @ruby_expr = "3 + 4 * 2.to_f / ( 1 - 5 ) ** 2 ** 3" @value = 3.0001220703125 end
def test_eval rpn = RPNExpression.new @rpn_expr value = rpn.eval assert_equal @value, value end
def test_rpn_to_infix rpn = RPNExpression.new @rpn_expr infix = rpn.to_infix assert_equal @infix_expr, infix assert_equal @value, eval(rpn.to_ruby) end
def test_infix_to_rpn rpn = RPNExpression.from_infix @infix_expr assert_equal @rpn_expr, rpn.to_s end
def test_other_expressions old_debug = $DEBUG $DEBUG = false
rpn = ["56 34 213.7 + * 678 -", "1 56 35 + 16 9 - / +"] infix = ["56 * ( 34 + 213.7 ) - 678", "1 + ( 56 + 35 ) / ( 16 - 9 )"] value = ["13193.2", "14.0"]
[0, 1].each do |idx|
obj = RPNExpression.new rpn[idx]
assert_equal value[idx], "%.1f" % obj.eval
assert_equal infix[idx], obj.to_infix
assert_equal value[idx], "%.1f" % eval(obj.to_ruby)
obj = RPNExpression.from_infix infix[idx]
assert_equal rpn[idx], obj.to_s
end
$DEBUG = old_debug
end
end</lang>
Running with $DEBUG on (ruby -d rpn.rb) gives:
Run options:
# Running tests:
for RPN expression: 3 4 2 * 1 5 - 2 3 ^ ^ / +
Term Action Stack
3 PUSH [3]
4 PUSH [3, 4]
2 PUSH [3, 4, 2]
* MUL [3, 8]
1 PUSH [3, 8, 1]
5 PUSH [3, 8, 1, 5]
- SUB [3, 8, -4]
2 PUSH [3, 8, -4, 2]
3 PUSH [3, 8, -4, 2, 3]
^ EXP [3, 8, -4, 8]
^ EXP [3, 8, 65536]
/ DIV [3, 0.0001220703125]
+ ADD [3.0001220703125]
Value = 3.0001220703125
.
for Infix expression: 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Term Action Output Stack
3 PUSH V ["3"] []
+ PUSH OP ["3"] ["+"]
4 PUSH V ["3", "4"] ["+"]
* PUSH OP ["3", "4"] ["+", "*"]
2 PUSH V ["3", "4", "2"] ["+", "*"]
/ MUL ["3", "4", "2", "*"] ["+"] * has higher precedence than /
/ PUSH OP ["3", "4", "2", "*"] ["+", "/"]
( OPEN_P ["3", "4", "2", "*"] ["+", "/", "("]
1 PUSH V ["3", "4", "2", "*", "1"] ["+", "/", "("]
- PUSH OP ["3", "4", "2", "*", "1"] ["+", "/", "(", "-"]
5 PUSH V ["3", "4", "2", "*", "1", "5"] ["+", "/", "(", "-"]
) SUB ["3", "4", "2", "*", "1", "5", "-"] ["+", "/", "("] unwinding parenthesis
) CLOSE_P ["3", "4", "2", "*", "1", "5", "-"] ["+", "/"]
^ PUSH OP ["3", "4", "2", "*", "1", "5", "-"] ["+", "/", "^"]
2 PUSH V ["3", "4", "2", "*", "1", "5", "-", "2"] ["+", "/", "^"]
^ PUSH OP ["3", "4", "2", "*", "1", "5", "-", "2"] ["+", "/", "^", "^"]
3 PUSH V ["3", "4", "2", "*", "1", "5", "-", "2", "3"] ["+", "/", "^", "^"]
RPN = 3 4 2 * 1 5 - 2 3 ^ ^ / +
..
for RPN expression: 3 4 2 * 1 5 - 2 3 ^ ^ / +
Term Action Stack
3 PUSH [node[3]]
4 PUSH [node[3], node[4]]
2 PUSH [node[3], node[4], node[2]]
* MUL [node[3], node[*]<left=node[4], right=node[2]>]
1 PUSH [node[3], node[*]<left=node[4], right=node[2]>, node[1]]
5 PUSH [node[3], node[*]<left=node[4], right=node[2]>, node[1], node[5]]
- SUB [node[3], node[*]<left=node[4], right=node[2]>, node[-]<left=node[1], right=node[5]>]
2 PUSH [node[3], node[*]<left=node[4], right=node[2]>, node[-]<left=node[1], right=node[5]>, node[2]]
3 PUSH [node[3], node[*]<left=node[4], right=node[2]>, node[-]<left=node[1], right=node[5]>, node[2], node[3]]
^ EXP [node[3], node[*]<left=node[4], right=node[2]>, node[-]<left=node[1], right=node[5]>, node[^]<left=node[2], right=node[3]>]
^ EXP [node[3], node[*]<left=node[4], right=node[2]>, node[^]<left=node[-]<left=node[1], right=node[5]>, right=node[^]<left=node[2], right=node[3]>>]
/ DIV [node[3], node[/]<left=node[*]<left=node[4], right=node[2]>, right=node[^]<left=node[-]<left=node[1], right=node[5]>, right=node[^]<left=node[2], right=node[3]>>>]
+ ADD [node[+]<left=node[3], right=node[/]<left=node[*]<left=node[4], right=node[2]>, right=node[^]<left=node[-]<left=node[1], right=node[5]>, right=node[^]<left=node[2], right=node[3]>>>>]
Infix = 3 + 4 * 2 / ( 1 - 5 ) ^ 2 ^ 3
Ruby = 3 + 4 * 2.to_f / ( 1 - 5 ) ** 2 ** 3
.
Finished tests in 0.012002s, 333.2831 tests/s, 999.8494 assertions/s.
4 tests, 12 assertions, 0 failures, 0 errors, 0 skips