Anonymous user
Arithmetic evaluation: Difference between revisions
added Ruby solution.
(→ast standard library module: Shorten long line and works in Python 2.X and 3.X) |
(added Ruby solution.) |
||
Line 1,843:
>>> eval(code_object)
16</lang>
=={{header|Ruby}}==
Function to convert infix arithmetic expression to binary tree. The resulting tree knows how to print and evaluate itself. Assumes expression is well-formed (matched parens, all operators have 2 operands). Source: http://www.seas.gwu.edu/~csci131/fall96/exp_to_tree.html
<lang ruby>$op_priority = {"+" => 0, "-" => 0, "*" => 1, "/" => 1}
$op_function = {
"+" => lambda {|x, y| x + y},
"-" => lambda {|x, y| x - y},
"*" => lambda {|x, y| x * y},
"/" => lambda {|x, y| x / y}}
class TreeNode
attr_accessor :info, :left, :right
def initialize(info)
@info = info
end
def leaf?
@left.nil? and @right.nil?
end
def to_s(order)
if leaf?
@info
else
left_s, right_s = @left.to_s(order), @right.to_s(order)
strs = case order
when :prefix then [@info, left_s, right_s]
when :infix then [left_s, @info, right_s]
when :postfix then [left_s, right_s, @info]
else []
end
"(" + strs.join(" ") + ")"
end
end
def eval
if !leaf? and operator?(@info)
$op_function[@info].call(@left.eval, @right.eval)
else
@info.to_f
end
end
end
def tokenize(exp)
exp
.gsub('(', ' ( ')
.gsub(')', ' ) ')
.split(' ')
end
def operator?(token)
$op_priority.keys.include?(token)
end
def pop_connect_push(op_stack, node_stack)
temp = op_stack.pop
temp.right = node_stack.pop
temp.left = node_stack.pop
node_stack.push(temp)
end
def infix_exp_to_tree(exp)
tokens = tokenize(exp)
op_stack, node_stack = [], []
tokens.each do |token|
if operator?(token)
# clear stack of higher priority operators
while not (op_stack.empty? or
op_stack.last.info == "(" or
$op_priority[op_stack.last.info] < $op_priority[token])
pop_connect_push(op_stack, node_stack)
end
op_stack.push(TreeNode.new(token))
elsif token == "("
op_stack.push(TreeNode.new(token))
elsif token == ")"
while op_stack.last.info != "("
pop_connect_push(op_stack, node_stack)
end
# throw away the '('
op_stack.pop
else
node_stack.push(TreeNode.new(token))
end
end
while not op_stack.empty?
pop_connect_push(op_stack, node_stack)
end
node_stack.last
end</lang>
Testing:
<lang ruby>exp = "1 + 2 - 3 * (4 / 6)"
puts("Original: " + exp)
tree = infix_exp_to_tree(exp)
puts("Prefix: " + tree.to_s(:prefix))
puts("Infix: " + tree.to_s(:infix))
puts("Postfix: " + tree.to_s(:postfix))
puts("Result: " + tree.eval.to_s)</lang>
Output:
<pre>Original: 1 + 2 - 3 * (4 / 6)
Prefix: (- (+ 1 2) (* 3 (/ 4 6)))
Infix: ((1 + 2) - (3 * (4 / 6)))
Postfix: ((1 2 +) (3 (4 6 /) *) -)
Result: 1.0</pre>
=={{header|Scala}}==
| |||