|
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)); |