Mathematical Expression Parser in Ruby

calc.rb

#
# 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