Instantly share code, notes, and snippets.

Embed
What would you like to do?
Evaluate a Prefix and Postfix expression. Extract a prefix subtree at a starting index. https://codepen.io/anon/pen/KBmpzr
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
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));
.container {
margin-top: 10px;
}
.btn {
margin-top: 10px;
}
#output {
width: 100%;
min-height:100px;
}
<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>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment