Create a gist now

Instantly share code, notes, and snippets.

@rubenwardy /calc.rb
Last active Jan 11, 2016

What would you like to do?
Mathematical Expression Parser in Ruby
#
# Written by rubenwardy
# License: WTFPL
#
# $ ruby calc.rb
#
# Turns a string such as "( 0 - (6) + ( 6 ^ 2 - 4 * 1 * 5 ) ^ (1 / 2) ) / ( 2 * 1)"
# into a binary syntax tree, and then into Reverse Polish Notation, and then executes it.
#
# String is typed in the terminal during program execution
#
#
# Tree Node
#
class STNode
def initialize(value, left = nil, right = nil)
@left = left
@right = right
@value = value
end
def crawl(obj)
res = ""
if @left then
res += @left.crawl(obj) + " "
end
if @right then
res += @right.crawl(obj) + " "
end
res += @value
res.strip!
if obj then
obj.submit(@value)
end
return res
end
end
#
# Run a tree
#
class Executor
def initialize
@stack = []
@failed = false
end
def pop
@stack.pop
end
def push(val)
@stack.push(val)
end
def submit(value)
value.strip!
#print "'" + value + "' "
#debug()
if value == '+' then
one = pop
two = pop
if one == nil or two == nil then
puts "Failed to execute +"
@failed = true
return nil
end
push(two + one)
elsif value == '*' then
one = pop
two = pop
if one == nil or two == nil then
puts "Failed to execute *"
@failed = true
return nil
end
push(two * one)
elsif value == '/' then
one = pop
two = pop
if one == nil or two == nil then
puts "Failed to execute /"
@failed = true
return nil
end
push(two / one)
elsif value == '-' then
one = pop
two = pop
if one == nil or two == nil then
puts "Failed to execute -"
@failed = true
return nil
end
push(two - one)
elsif value == '^' then
one = pop
two = pop
if one == nil or two == nil then
puts "Failed to execute ^"
@failed = true
return nil
end
push(two ** one)
elsif /\A[-+]?\d+\z/ === value
push(value.to_f)
else
puts "Unrecognised symbol " + value
@failed = true
end
end
def debug
print "stack:"
@stack.each do |i|
print " " + i.to_s
end
puts
end
def result
if @failed then
return nil
end
@stack.pop
end
end
#
# Turn a string into a tree
#
def processString(input)
input.strip!
if input[0] == '(' and input[-1] == ')' then
is_right = true
level = 0
input[0..-2].split("").each do |c|
if c == '(' then
level += 1
end
if c == ')' then
level -= 1
end
if level == 0 then
is_right = false
break
end
end
if is_right then
input = input[1..-2]
end
end
level = 0
output = ""
#print "\tInput: " + input
input.split("").each do |c|
if c == '(' then
level += 1
end
if level == 0 then
output += c
else
output += "_"
end
if c == ')' then
level -= 1
end
end
if level != 0 then
puts "Syntax Error"
return nil
end
#puts (" " * (60 - input.length)) + "=> " + output
idx = output.index("+")
if idx == nil then
idx = output.index("-")
if idx == nil then
idx = output.index("*")
if idx == nil then
idx = output.index("/")
if idx == nil then
idx = output.index("^")
if idx == nil then
node = STNode.new(input, nil, nil)
else
node = STNode.new("^", processString(input[0..(idx -1)]), processString(input[(idx+1)..-1]))
end
else
node = STNode.new("/", processString(input[0..(idx -1)]), processString(input[(idx+1)..-1]))
end
else
node = STNode.new("*", processString(input[0..(idx -1)]), processString(input[(idx+1)..-1]))
end
else
node = STNode.new("-", processString(input[0..(idx -1)]), processString(input[(idx+1)..-1]))
end
else
node = STNode.new("+", processString(input[0..(idx -1)]), processString(input[(idx+1)..-1]))
end
end
#
# API Functions
#
def unit(input, output)
tree = processString(input)
if not tree then
puts input + ": FAILED"
return
end
res = tree.crawl(nil)
if res == output then
puts input + (" " * (60 - input.length)) + ": PASSED"
elsif not res then
puts input + (" " * (60 - input.length)) + ": FAILED"
else
puts input + (" " * (60 - input.length)) + ": FAILED, " + res
end
end
def run(input)
tree = processString(input)
ex = Executor.new()
if tree then
tree.crawl(ex)
end
ex.result()
end
#
# MAIN PROGRAM
#
puts "======================================================================"
puts "============================= UNIT TESTS ============================="
puts "======================================================================"
unit("1 + 1", "1 1 +")
unit("2 + (1 + 1)", "2 1 1 + +")
unit("2 + (3 - 1)", "2 3 1 - +")
unit("10000 / 10000", "10000 10000 /")
unit("1 + (2 * 3) / 3", "1 2 3 * 3 / +")
unit("2 ^ 2", "2 2 ^")
unit("( 0 - 6 + ( 6 ^ 2 - 4 * 1 * 5 ) ^ (1 / 2) ) / ( 2 * 1)", "0 6 - 6 2 ^ 4 1 5 * * - 1 2 / ^ + 2 1 * /")
puts "======================================================================"
puts "======================================================================"
while true do
puts
print "Enter Expression: "
inp = gets.chomp
if not inp or inp == "" then
break
end
res = run(inp)
if res then
puts "= " + res.to_s
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment