genetic-programming.txt

## genetic-programming.txt
y = f(x)
input: (x, y)
GA should generate program (tree) that calculates f(x) most correct for any value of x.
During fitness run, replace x with input value. Checkout output against correct value for y.

T: 1 2 3 4 5 x
F: + - * /

Example tree: y = 3 + 5 - x

   +
 3    -
    5  x

Representation:

infix: [3+5-x]
prefix: [+3-5x]

Example tree 2: y = (x + 2) / 5 - (3 * x)

     /
  +     -
 x 2   5  *
         3  x

Representation:

postfix: [/+x2-5*3x]

Example tree 3: y = (a * b) + (c / d)
y = (6 * 2) + (9 / 3)
12 + 3
15

infix: [a*b+c/d]
postfix: [ab*cd/+]
prefix: [+*ab/cd]

      +
  *      /
 a  b  c   d


x = 1
y = 3 + (5 - x) = 7

x = 2
y = 3 + (5 - 2) = 6

x = 3
y = 3 + (5 - 3) = 5

x = 4
y = 3 + (5 - 4) = 4

x = 5
y = 3 + (5 - 5) = 3

## prefix.js
const functions = '+-*/'.split('');
const plus = (a, b) => { return a + b; }
const minus = (a, b) => { return a - b; }
const multiply = (a, b) => { return a * b; }
const divide = (a, b) => { return a / b; }

const isOperator = val => {
  return functions.includes(val);
};

const compute = (a, op, b) => {
  return op(a, b);
};

const symbolToOperator = symbol => {
  switch (symbol) {
    case '+': return plus;
    case '-': return minus;
    case '*': return multiply;
    case '/': return divide;
  }
}

const evaluatePostfix = expr => {
  const parts = expr.split('');
  const stack = [];

  parts.forEach(val => {
    if (isOperator(val)) {
      const b = stack.pop();
      const a = stack.pop();
      stack.push(compute(a, symbolToOperator(val), b));
    }
    else {
      stack.push(parseInt(val));
    }
  });

  return stack[0];
};

const evaluatePrefix = expr => {
  const parts = expr.split('');
  const stack = [];

  for (let j=expr.length - 1; j >= 0; j--) {
    const val = expr[j];

    // Push operated to stack.
    if (!isOperator(val)) {
      stack.push(parseInt(val));
    }
    else {
      // Operator found. Pop two elements from the stack.
      const a = stack.pop();
      const b = stack.pop();
      stack.push(compute(a, symbolToOperator(val), b));
    }
  }

  return stack[0];
};

const subtreePrefix = (expr, index) => {
  const parts = expr.split('');
  let val = parts[index];
  const opStack = []; // Start with the node at the index.
  const valStack = [];
  let valCount = 0;
  let i = index + 1;

  if (isOperator(val)) {
    opStack.push(val);
  }
  else {
    valStack.push(val);
  }

  while (opStack.length && i < parts.length) {
    val = parts[i];

    if (!isOperator(val) && valCount) {
        valStack.push(compute(valStack.pop(), symbolToOperator(opStack.pop()), parseInt(val)));
    }
    else if (isOperator(val)) {
      opStack.push(val);
      valCount = 0;
    }
    else {
      valStack.push(parseInt(val));
      valCount++;
    }

    i++;
  }

  // Correct for extraneous value at end of subtree.
  if (Math.abs(index - i) % 2 === 0) {
    i--;
  }

  return { expression: expr.substring(index, i), start: index, end: i - 1 };
};

$(function() {
  $('#btnPrefix').click(() => {
 $('#output').html(evaluatePrefix($('#expression').val()));
  });

  $('#btnPostfix').click(() => {
 $('#output').html(evaluatePostfix($('#expression').val()));
  });
});

console.log(subtreePrefix('+7+-*01-0*692', 7));

## zclient.css
.container {
  margin-top: 10px;
}

.btn {
  margin-top: 10px;
}

#output {
  width: 100%;
  min-height:100px;
}

## zclient.html
<div class="container">
  <div class='form-group'>
    <label for='expression' className='form-control'>Expression</label>
    <input type='text' id='expression' class='form-control' />
    <button type='button' id='btnPrefix' class='btn btn-primary'>Evaluate Prefix</button>
    <button type='button' id='btnPostfix' class='btn btn-primary'>Evaluate Postfix</button>
  </div>
  <small>Output</small>
  <div id="output" class='pl-1'></div>
</div>