You are here

Arithmetic & Logic Gate Algorithm Evaluator (ALGEA)

published by Diego F. Roldán on Wed, 01/22/2020 - 15:14

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:

tags: