-
Notifications
You must be signed in to change notification settings - Fork 0
/
rpn.jl
118 lines (109 loc) · 3.37 KB
/
rpn.jl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
module rpn
export to_rpn, from_rpn
# eh, trying to do this super-genericly isn't reasonable
# considering that it all depends on the internals of Julia
# and the foibles of Friedman expressions
# what is Julia function for unary minus?
# * same as for regular subtraction
# what does :(a - b - c) and :(a / b / c) give us?
# * expression as binary tree
# what does :(1) give us?
# * Int64
# what does :(-1) give us?
# * Int64
if (VERSION.major, VERSION.minor) <= (0, 3)
my_int = int
else
my_int = (x -> parse(Int, x))
end
fn_tag = Dict([(:+, '+'),
(:-, '-'),
(:*, '*'),
(:/, '/'),
(:^, '^')])
inv_fn_tag = Dict(collect(zip(values(fn_tag), keys(fn_tag))))
function to_rpn(a)
# in general, it is assumed that a is a valid expression
if isa(a, Integer) || isa(a, Int64) || isa(a, Int128) || isa(a, BigInt)
if a >= 0
return string(a, " ")
else
return string(-a, " !")
end
elseif isa(a, Expr)
if a.head != :call
error(string("Cannot parse expression head: ", a.head))
end
if a.args[1] in [:+, :*]
if length(a.args) == 2
return to_rpn(a.args[2])
elseif length(a.args) == 3
return string(to_rpn(a.args[3]), to_rpn(a.args[2]), fn_tag[a.args[1]])
else
# enforce leftwise association
return to_rpn(Expr(a.head,
a.args[1],
Expr(a.head, a.args[1 : end-1]...),
a.args[end]))
end
elseif a.args[1] in [:/, :^]
if length(a.args) != 3
error("Illegal number of arguments (/^)")
else
return string(to_rpn(a.args[3]), to_rpn(a.args[2]), fn_tag[a.args[1]])
end
elseif a.args[1] == :-
if length(a.args) == 2
return string(to_rpn(a.args[2]), "!")
elseif length(a.args) == 3
return string(to_rpn(a.args[3]), to_rpn(a.args[2]), fn_tag[a.args[1]])
else
error("Illegal number of arguments (-)")
end
else
error(string("Unrecognized operation: ", a.args[1]))
end
else
error(string("Unrecognized type: ", typeof(a)))
end
end
function from_rpn(a::String)
digits = "0123456789"
stack = Any[]
in_integer = false
for c in a
if c in digits
if in_integer
stack[1] = stack[1] * 10 + my_int(string(c))
else
unshift!(stack, big(my_int(string(c))))
in_integer = true
end
elseif c == ' '
in_integer = false
elseif haskey(inv_fn_tag, c)
if length(stack) < 2
error(string("Not enough arguments on stack: ", c))
else
splice!(stack, 1:2, [Expr(:call,
inv_fn_tag[c],
stack[1],
stack[2])])
end
elseif c == '!'
if length(stack) < 1
error(string("Not enough arguments on stack: ", c))
else
stack[1] = Expr(:call, :-, stack[1])
end
else
error(string("Unrecognized character: ", c))
end
end
if length(stack) != 1
# error("Unbalanced RPN expression")
error(string("Unbalanced RPN expression", stack))
end
return stack[1]
end
end # module rpn