Arithmetic evaluation: Difference between revisions
Content added Content deleted
(→{{header|ooRexx}}: Add example for ooRexx) |
|||
Line 2,236: | Line 2,236: | ||
ocamlopt -pp camlp4o arith_eval.ml -o arith_eval.opt |
ocamlopt -pp camlp4o arith_eval.ml -o arith_eval.opt |
||
=={{header|ooRexx}}== |
|||
<lang ooRexx> |
|||
expressions = .array~of("2+3", "2+3/4", "2*3-4", "2*(3+4)+5/6", "2 * (3 + (4 * 5 + (6 * 7) * 8) - 9) * 10", "2*-3--4+-.25") |
|||
loop input over expressions |
|||
expression = createExpression(input) |
|||
if expression \= .nil then |
|||
say 'Expression "'input'" parses to "'expression~string'" and evaluates to "'expression~evaluate'"' |
|||
end |
|||
-- create an executable expression from the input, printing out any |
|||
-- errors if they are raised. |
|||
::routine createExpression |
|||
use arg inputString |
|||
-- signal on syntax |
|||
return .ExpressionParser~parseExpression(inputString) |
|||
syntax: |
|||
condition = condition('o') |
|||
say condition~errorText |
|||
say condition~message |
|||
return .nil |
|||
-- a base class for tree nodes in the tree |
|||
-- all nodes return some sort of value. This can be constant, |
|||
-- or the result of additional evaluations |
|||
::class evaluatornode |
|||
-- all evaluation is done here |
|||
::method evaluate abstract |
|||
-- node for numeric values in the tree |
|||
::class constant |
|||
::method init |
|||
expose value |
|||
use arg value |
|||
::method evaluate |
|||
expose value |
|||
return value |
|||
::method string |
|||
expose value |
|||
return value |
|||
-- node for a parenthetical group on the tree |
|||
::class parens |
|||
::method init |
|||
expose subexpression |
|||
use arg subexpression |
|||
::method evaluate |
|||
expose subexpression |
|||
return subexpression~evaluate |
|||
::method string |
|||
expose subexpression |
|||
return "("subexpression~string")" |
|||
-- base class for binary operators |
|||
::class binaryoperator |
|||
::method init |
|||
expose left right |
|||
-- the left and right sides are set after the left and right sides have |
|||
-- been resolved. |
|||
left = .nil |
|||
right = .nil |
|||
-- base operation |
|||
::method evaluate |
|||
expose left right |
|||
return self~operation(left~evaluate, right~evaluate) |
|||
-- the actual operation of the node |
|||
::method operation abstract |
|||
::method symbol abstract |
|||
::method precedence abstract |
|||
-- display an operator as a string value |
|||
::method string |
|||
expose left right |
|||
return '('left~string self~symbol right~string')' |
|||
::attribute left |
|||
::attribute right |
|||
::class addoperator subclass binaryoperator |
|||
::method operation |
|||
use arg left, right |
|||
return left + right |
|||
::method symbol |
|||
return "+" |
|||
::method precedence |
|||
return 1 |
|||
::class subtractoperator subclass binaryoperator |
|||
::method operation |
|||
use arg left, right |
|||
return left - right |
|||
::method symbol |
|||
return "-" |
|||
::method precedence |
|||
return 1 |
|||
::class multiplyoperator subclass binaryoperator |
|||
::method operation |
|||
use arg left, right |
|||
return left * right |
|||
::method symbol |
|||
return "*" |
|||
::method precedence |
|||
return 2 |
|||
::class divideoperator subclass binaryoperator |
|||
::method operation |
|||
use arg left, right |
|||
return left / right |
|||
::method symbol |
|||
return "/" |
|||
::method precedence |
|||
return 2 |
|||
-- a class to parse the expression and build an evaluation tree |
|||
::class expressionParser |
|||
-- create a resolved operand from an operator instance and the top |
|||
-- two entries on the operand stack. |
|||
::method createNewOperand class |
|||
use strict arg operator, operands |
|||
-- the operands are a stack, so they are in inverse order current |
|||
operator~right = operands~pull |
|||
operator~left = operands~pull |
|||
-- this goes on the top of the stack now |
|||
operands~push(operator) |
|||
::method parseExpression class |
|||
use strict arg inputString |
|||
-- stacks for managing the operands and pending operators |
|||
operands = .queue~new |
|||
operators = .queue~new |
|||
-- this flags what sort of item we expect to find at the current |
|||
-- location |
|||
afterOperand = .false |
|||
loop currentIndex = 1 to inputString~length |
|||
char = inputString~subChar(currentIndex) |
|||
-- skip over whitespace |
|||
if char == ' ' then iterate currentIndex |
|||
-- If the last thing we parsed was an operand, then |
|||
-- we expect to see either a closing paren or an |
|||
-- operator to appear here |
|||
if afterOperand then do |
|||
if char == ')' then do |
|||
loop while \operators~isempty |
|||
operator = operators~pull |
|||
-- if we find the opening paren, replace the |
|||
-- top operand with a paren group wrapper |
|||
-- and stop popping items |
|||
if operator == '(' then do |
|||
operands~push(.parens~new(operands~pull)) |
|||
leave |
|||
end |
|||
-- collapse the operator stack a bit |
|||
self~createNewOperand(operator, operands) |
|||
end |
|||
-- done with this character |
|||
iterate currentIndex |
|||
end |
|||
afterOperand = .false |
|||
operator = .nil |
|||
if char == "+" then operator = .addoperator~new |
|||
else if char == "-" then operator = .subtractoperator~new |
|||
else if char == "*" then operator = .multiplyoperator~new |
|||
else if char == "/" then operator = .divideoperator~new |
|||
if operator \= .nil then do |
|||
loop while \operators~isEmpty |
|||
top = operators~peek |
|||
-- start of a paren group stops the popping |
|||
if top == '(' then leave |
|||
-- or the top operator has a lower precedence |
|||
if top~precedence < operator~precedence then leave |
|||
-- process this pending one |
|||
self~createNewOperand(operators~pull, operands) |
|||
end |
|||
-- this new operator is now top of the stack |
|||
operators~push(operator) |
|||
-- and back to the top |
|||
iterate currentIndex |
|||
end |
|||
raise syntax 98.900 array("Invalid expression character" char) |
|||
end |
|||
-- if we've hit an open paren, add this to the operator stack |
|||
-- as a phony operator |
|||
if char == '(' then do |
|||
operators~push('(') |
|||
iterate currentIndex |
|||
end |
|||
-- not an operator, so we have an operand of some type |
|||
afterOperand = .true |
|||
startindex = currentIndex |
|||
-- allow a leading minus sign on this |
|||
if inputString~subchar(currentIndex) == '-' then |
|||
currentIndex += 1 |
|||
-- now scan for the end of numbers |
|||
loop while currentIndex <= inputString~length |
|||
-- exit for any non-numeric value |
|||
if \inputString~matchChar(currentIndex, "0123456789.") then leave |
|||
currentIndex += 1 |
|||
end |
|||
-- extract the string value |
|||
operand = inputString~substr(startIndex, currentIndex - startIndex) |
|||
if \operand~datatype('Number') then |
|||
raise syntax 98.900 array("Invalid numeric operand '"operand"'") |
|||
-- back this up to the last valid character |
|||
currentIndex -= 1 |
|||
-- add this to the operand stack as a tree element that returns a constant |
|||
operands~push(.constant~new(operand)) |
|||
end |
|||
loop while \operators~isEmpty |
|||
operator = operators~pull |
|||
if operator == '(' then |
|||
raise syntax 98.900 array("Missing closing ')' in expression") |
|||
self~createNewOperand(operator, operands) |
|||
end |
|||
-- our entire expression should be the top of the expression tree |
|||
expression = operands~pull |
|||
if \operands~isEmpty then |
|||
raise syntax 98.900 array("Invalid expression") |
|||
return expression |
|||
</lang> |
|||
Output: |
|||
<pre> |
|||
Expression "2+3" parses to "(2 + 3)" and evaluates to "5" |
|||
Expression "2+3/4" parses to "(2 + (3 / 4))" and evaluates to "2.75" |
|||
Expression "2*3-4" parses to "((2 * 3) - 4)" and evaluates to "2" |
|||
Expression "2*(3+4)+5/6" parses to "((2 * ((3 + 4))) + (5 / 6))" and evaluates to "14.8333333" |
|||
Expression "2 * (3 + (4 * 5 + (6 * 7) * 8) - 9) * 10" parses to "((2 * (((3 + (((4 * 5) + (((6 * 7)) * 8)))) - 9))) * 10)" and evaluates to 7000" |
|||
Expression "2*-3--4+-.25" parses to "(((2 * -3) - -4) + -.25)" and evaluates to "-2.25" |
|||
</pre> |
|||
=={{header|Oz}}== |
=={{header|Oz}}== |
||
We can create a simple, but slow parser using logic programming. |
We can create a simple, but slow parser using logic programming. |