Arithmetic evaluation: Difference between revisions
→{{header|FreeBASIC}}
m ({{out}}) |
|||
Line 1,764:
<lang FreeBASIC>
'Arithmetic evaluation
'
'Create a program which parses and evaluates arithmetic expressions.
'
'Requirements
'
' * An abstract-syntax tree (AST) for the expression must be created from parsing the
' input.
' * The AST must be used in evaluation, also, so the input may not be directly evaluated
' (e.g. by calling eval or a similar language feature.)
' * The expression will be a string or list of symbols like "(1+3)*7".
' * The four symbols + - * / must be supported as binary operators with conventional
' precedence rules.
' * Precedence-control parentheses must also be supported.
'
'Standard mathematical precedence should be followed:
'
' Parentheses
' Multiplication/Division (left to right)
' Addition/Subtraction (left to right)
'
' test cases:
' 2*-3--4+-0.25 : returns -2.25
' 1 + 2 * (3 + (4 * 5 + 6 * 7 * 8) - 9) / 10 : returns 71
enum
false = 0
true = -1
end enum
enum Symbol
unknown_sym
minus_sym
plus_sym
lparen_sym
rparen_sym
number_sym
mul_sym
div_sym
unary_minus_sym
unary_plus_sym
done_sym
eof_sym
end enum
type Tree
as Tree ptr leftp, rightp
op as
value as double
end type
dim shared sym as
dim shared tokenval as double
dim shared usr_input as string
declare function expr(byval p as integer) as Tree ptr
function isdigit(byval ch as string) as long
return
end function
Line 1,784 ⟶ 1,830:
end sub
' tokenize the input string
sub getsym()
do
if
line input usr_input
usr_input += chr(10)
endif
dim as string ch = mid(usr_input, 1, 1) ' get the next char
usr_input = mid(usr_input, 2) ' remove it from input
select case ch
case " ": continue do
case chr(10), "": sym =
case "+": sym =
case "-": sym =
case "*": sym =
case "/": sym =
case "(": sym =
case ")": sym =
case else
if isdigit(ch) then
Line 1,809 ⟶ 1,857:
s += ch
if ch = "." then dot += 1
ch = mid(usr_input, 1, 1) ' get the next char
usr_input = mid(usr_input, 2) ' remove it from input
loop
if ch = "." or dot > 1 then error_msg("bogus number")
usr_input = ch + usr_input ' prepend the char to input
tokenval = val(s)
sym =
end if
▲ sym = "*unknown*"
return
end select
Line 1,824 ⟶ 1,870:
end sub
function make_node(byval op as
dim t as Tree ptr
Line 1,834 ⟶ 1,880:
end function
function is_binary(byval op as
select case op
case mul_sym, div_sym, plus_sym, minus_sym: return true
case else: return false
end select
end function
function prec(byval op as
select case op
case
case
case
case else: return 0
end select
end function
Line 1,851 ⟶ 1,900:
select case sym
case
dim op as
getsym()
t = expr(prec(
if op =
if op =
case
getsym()
t = expr(0)
if sym <>
getsym()
return t
case
t = make_node(sym, 0, 0)
t->value = tokenval
Line 1,877 ⟶ 1,926:
while is_binary(sym) andalso prec(sym) >= p
dim t1 as Tree ptr
dim op as
getsym()
t1 = expr(prec(op) + 1)
Line 1,888 ⟶ 1,937:
if t <> 0 then
select case t->op
case
case
case
case
case
case
case
case else: error_msg("unexpected tree node")
end select
Line 1,903 ⟶ 1,952:
do
getsym()
if sym =
if sym = done_sym then continue do
dim t as Tree ptr = expr(0)
print"> "; eval(t)
if sym
if sym <> done_sym then error_msg("unexpected input")
loop
</lang>
| |||