You are here
Arithmetic & Logic Gate Algorithm Evaluator (ALGEA)
Algorithm
The algorithm uses the Shunting-Yard algorithm and applies the Reverse Polish Notation to traverse through an array of tokens, essentially a parsed mathematical expression (string).
Queue holds operands, evaluation of expression results, and operators including logical operators.
Stack holds the logical operators.
The implementation uses the Shunting-Yard algorithm and applies the Reverse Polish Notation (RPN) to traverse through an array of tokens, essentially to parsed mathematical expressions (string). The evaluation of these expressions return a boolean value of true or false.
e.g. mathematical expression to determine if it evaluates to true or false.
(9 = 3 OR 1 = 4) OR (1 = 2)
evaluates to false
((1 + 2) = ( 2 + 1))
evaluates to true
<ALGORITHM>
WHILE TOKENS
IF OPERATOR
WHILE OPERATOR WITH GREATER PRECEDENCE
POP OPERATOR FROM STACK
EVALUATE EXPRESSION
PUSH EXPRESSION RESULT TO QUEUE
PUSH CURRENT OPERATOR TO STACK
ELSE IF LEFT BRACKET
PUSH TO STACK
ELSE IF RIGHT BRACKET
WHILE NOT LEFT BRACKET AT TOP OF STACK
POP OPERATOR FROM STACK
EVALUATE EXPRESSION
PUSH EXPRESSION RESULT TO QUEUE
POP LEFT BRACKET FROM STACK
ELSE IF OPERAND
PUSH TO QUEUE
WHILE OPERATORS IN STACK
EVALUATE EXPRESSION
PUSH RESULT TO QUEUE
</ALGORITHM>
References
- Reverse Polish Notation (RPN) The reverse Polish scheme was proposed in 1954 by Arthur Burks, Don Warren, and Jesse Wright[4] and was independently reinvented by Friedrich L. Bauer and Edsger W. Dijkstra
Examples
In this example the $result variable will have an array with the mathematical expression submitted for evaluation and the result of the mathematical expression.
require_once('algae/src/MathExpression.inc');
$args = new stdClass();
$args->debug = true;
$args->math_expression = '((1 + 2) = ( 2 + 1))';
$math_exp = new \PARCE\ALGAE\MathExpression($args);
$result = $math_exp->evaluate();
Upcoming features
Less strict syntax for arithmetic operands.
Github: https://github.com/diegoroldan/phpsandbox/tree/master/algae
lifestyle:
medium:
- Diego F. Roldán's blog
- Log in to post comments
- 17847 reads