142 lines
2.8 KiB
Crystal
142 lines
2.8 KiB
Crystal
abstract class Expression
|
|
abstract def eval
|
|
end
|
|
|
|
class IntLiteral < Expression
|
|
property value
|
|
|
|
def initialize (@value : Int32)
|
|
end
|
|
|
|
def eval
|
|
@value
|
|
end
|
|
|
|
def to_s (io)
|
|
io << @value.to_s
|
|
end
|
|
end
|
|
|
|
alias UnFun = Int32 -> Int32
|
|
alias BinFun = Int32, Int32 -> Int32
|
|
|
|
class UnOp < Expression
|
|
getter operand : Expression, op : String
|
|
@function : UnFun
|
|
|
|
def initialize (@operand, @op, &block : UnFun)
|
|
@function = block
|
|
end
|
|
|
|
def eval
|
|
@function.call @operand.eval
|
|
end
|
|
|
|
def to_s (io)
|
|
io << @op
|
|
@operand.to_s io
|
|
end
|
|
end
|
|
|
|
class BinOp < Expression
|
|
getter left : Expression, right : Expression, op : String
|
|
@function : BinFun
|
|
|
|
def initialize (@left, @right, @op, &block : BinFun)
|
|
@function = block
|
|
end
|
|
|
|
def eval
|
|
@function.call @left.eval, @right.eval
|
|
end
|
|
|
|
def to_s (io)
|
|
io << "("
|
|
@left.to_s io
|
|
io << " " << @op << " "
|
|
@right.to_s io
|
|
io << ")"
|
|
end
|
|
end
|
|
|
|
class Parser
|
|
UNOPS = {
|
|
'-' => { func: UnFun.new {|a| -a } }
|
|
}
|
|
BINOPS = {
|
|
'+' => { prio: 2, func: BinFun.new {|a, b| a + b } },
|
|
'-' => { prio: 2, func: BinFun.new {|a, b| a - b } },
|
|
'*' => { prio: 1, func: BinFun.new {|a, b| a * b } },
|
|
'/' => { prio: 1, func: BinFun.new {|a, b| a // b } }
|
|
}
|
|
@chars : Array(Char)
|
|
|
|
def initialize (s)
|
|
@chars = s.chars
|
|
end
|
|
|
|
def consume (ch)
|
|
raise "'#{ch}' expected" unless @chars.present? && @chars.first == ch
|
|
@chars.shift
|
|
end
|
|
|
|
def skip_spaces
|
|
while @chars.present? && @chars.first.whitespace?
|
|
@chars.shift
|
|
end
|
|
end
|
|
|
|
def parse_unit
|
|
skip_spaces
|
|
raise "Unexpected end of input" if @chars.empty?
|
|
case @chars.first
|
|
when '('
|
|
consume '('
|
|
res = parse_binop prio: 2
|
|
consume ')'
|
|
res
|
|
when .in? UNOPS.keys
|
|
op = @chars.shift
|
|
UnOp.new parse_unit, op.to_s, &UNOPS[op][:func]
|
|
when '0'..'9'
|
|
n = 0
|
|
while @chars.present? && @chars.first.in? '0'..'9'
|
|
n = n * 10 + @chars.shift.to_i
|
|
end
|
|
IntLiteral.new n
|
|
else
|
|
raise "Unexpected '#{@chars.first}'"
|
|
end
|
|
end
|
|
|
|
def parse_binop (prio)
|
|
left = if prio == 0
|
|
parse_unit
|
|
else
|
|
parse_binop prio-1
|
|
end
|
|
loop do
|
|
skip_spaces
|
|
return left if @chars.empty?
|
|
op = @chars.first
|
|
opdata = BINOPS[op]?
|
|
return left if !opdata || opdata[:prio] != prio
|
|
consume op
|
|
right = parse_binop prio-1
|
|
left = BinOp.new left, right, op.to_s, &opdata[:func]
|
|
end
|
|
end
|
|
|
|
def parse
|
|
res = parse_binop prio: 2
|
|
skip_spaces
|
|
raise "Unexpected '#{@chars.first}'" unless @chars.empty?
|
|
res
|
|
end
|
|
end
|
|
|
|
formula = "1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5 - 22/(7 + 2*(3 - 1)) - 1)) + -1*-1"
|
|
ast = Parser.new(formula).parse
|
|
print "Original: ", formula, "\n"
|
|
print "Parsed: ", ast, "\n"
|
|
print "Result: ", ast.eval, "\n"
|