这篇文章次要讲一下如何用 JS 实现一个算数表达式的求值形式，例如输出一个算数表达式字符串 ‘ 23 + 4 * 5 ‘，如何返回这个表达式的最终后果呢？可能大家会感觉这个很简略，间接用 Function 或 eval 将表达式作为代码执行不就能够了吗？可能的实现如下：
function evalExpr(expr) {let func = new Function(`return ${expr}`);
return func();}
这篇文章次要是从算法层面上剖析一个表达式的求值过程。
一、如何将一个算数表达式转化成一棵二叉树：
对于什么是二叉树，不相熟的同学能够看一下相干的材料或数据；还是以表达式 23 + 4 * 5 为例，转换成二叉树的构造如下：
从图中能够看出，每一个叶子节点（没有子节点）对应一个操作数，操作符对应的节点都不是叶子节点。
接下来通过代码看一下转换过程：
1、首先定义节点的类型，这个例子中节点可能有两种类型，操作数节点或者操作符节点
// 节点类型，操作符或操作数
const nodeType = {
operator: 0,
operand: 1
};
2、为二叉树中的单个节点建设数据模型，节点蕴含四个字段：值、类型、左子节点、有子节点；
// 二叉树的节点
function BTNode(value, type, left = null, right = null) {
this.value = value; // 节点的值，例如对于操作符节点，可能的取值为：+、-、*、/
this.type = type; // 节点类型，取值为 nodeType.operator or nodeType.operand
this.left = left; // 左子节点
this.right = right; // 右子节点
}
3、接下来就是如何将一个表达式转换成二叉树了，简略起见，先不思考表达式中有括号的状况：
首先讲一下具体的转换原理，还是以 23 + 4 * 5 为例，转化过程如下：
（1）将表达式转换成一个数组，[23, +, 4, * 5]，创立一个空的栈（即一个空的数组）: const stack = [];
(2) 从左到右顺次遍历每一个元素：
a、如果是一个操作数，创立一个新的操作数节点，接下来查看栈顶的元素是否是值为 * 或 / 的操作符节点，如果 是，则将新的操作树节点作为栈顶元素的右子节点，否则间接将新的节点压入栈中；
b、如果是一个操作符，则创立一个新的操作符节点，接下来将栈顶的元素取出，并作为新节点的左子节点，而后 将新的节点压入栈中；
（3）从左向右遍历栈中的节点，将栈中的每一个节点作为他前一个节点的右子节点；并返回第一个节点。
依照上述的过程，在转化 23 + 4 * 5 的过程中，stack 的构造变动一次如下：
const operReg = /[+-*/]/;
const isOper = t => operReg.test(t);
// 将字符串表达式转换成二叉树
function toBT(expr) {const tokens = expr.replace( /[+-*/]/g, _ => `${_}`).trim()
.split(/s+/)
.map(t => t.trim());
const nodes = [];
for (let token of tokens) {if (isOper(token)) {const node = new BTNode(token, nodeType.operator, nodes.pop());
nodes.push(node);
} else {const value = parseFloat(token);
if (Number.isNaN(value)) {throw `Invalid express for '${token}'`;
}
const node = new BTNode(value, nodeType.operand);
const top = nodes[nodes.length - 1];
if (top && top.type === nodeType.operator && (top.value === '*' || top.value === '/')) {top.right = node;} else {nodes.push(node);
}
}
}
for (let i = 0; i < nodes.length - 1; i++) {const node = nodes[i];
node.right = nodes[i + 1];
}
return nodes[0];
}
4、接下来实现一下二叉树的遍历性能
遍历包含前序遍历、中序遍历、后序遍历；前序遍历就是先遍历父节点，再遍历左子节点，再遍历右子节点；中序遍历的程序是：左子节点、父节点、右子节点；后序遍历的程序为：左子节点、右子节点以及父节点。中序遍历的后果就是咱们通常看到的表达式；前面的求值会用到后序遍历的后果。后序表达式就是先书写操作数再书写操作符，例如 23 + 4 5 对应的后序表达式为：23 4 5 +。
后序表达式尽管不利于浏览，然而用于计算表达式的值时十分的不便，且不须要借助于括号就可是调整运算的优先级。
遍历性能的实现如下：
const proto = BTNode.prototype;
proto.nodeType = nodeType;
// 中序遍历
proto.middleTraverse = function () {return traverse(this, 'middle');
}
// 前序遍历
proto.forwardTraverse = function () {return traverse(this, 'forward');
}
// 前序遍历
proto.backwardTraverse = function () {return traverse(this, 'backward');
}
function traverse(node, type = 'mid') {if (!node instanceof BTNode) {throw `The param 'node' must be type of BTNode`;}
if (node.type === nodeType.operand) {return [node.value];
}
switch(type) {
case 'forward':
return [node.value, ...traverse(node.left, type), ...traverse(node.right, type)];
case 'middle':
return [...traverse(node.left, type), node.value, ...traverse(node.right, type)];
case 'backward':
return [...traverse(node.left, type), ...traverse(node.right, type), node.value];
}
}
5、后序表达式的求值
后序表达式的求值过程很简略：
遍历后序表达式中的每一个元素：
（1）如果是操作数则间接压入栈中，
（2）如果时操作符，从栈顶中取出两个元素，并进行操作符对应的运算，并将运算后果从新压入栈中；
具体的实现如下：
function evalBackwardExpression(exprs) {const exprsStack = [];
for (let token of exprs) {if (isOper(token)) {const rNum = exprsStack.pop();
const lNum = exprsStack.pop();
let result;
switch(token) {
case '+':
result = lNum + rNum;
break;
case '-':
result = lNum - rNum;
break;
case '*':
result = lNum * rNum;
break;
case '/':
result = lNum / rNum;
break;
}
exprsStack.push(result);
} else {exprsStack.push(token);
}
}
return exprsStack[0];
}
综上所述，整个求值过程包含以下几个步骤：
（1）生成二叉树；
（2）遍历二叉树获取后序表达式；
（3）对后序表达式求值。
下面的代码中在将表达式转换为二叉树的过程中没有思考表达式中有括号的状况，接下来对 toBT 办法进行扩大以反对有括号的表达式。对于有括号的表达式，如果将括号中的整体看成是一个操作数，则整个解析过程和之前是统一的。
括号的处理过程大抵如下：
如果是“（”, 间接入栈；
如果是右小括号，则一次取出第一个左括号之后的所有节点，依照 3.（3）中的步骤组装成单个节点压入栈中；
扩大后的实现如下：
// 将字符串表达式转换成二叉树
const shouldMerge = node => node &&
node.type === nodeType.operator &&
(node.value === '*' || node.value === '/');
function toBT(expr) {const tokens = expr.replace(/[+-*/()]/g, _ => ` ${_} `)
.trim()
.split(/s+/)
.map(t => t.trim());
console.log(tokens);
const nodes = [];
for (let token of tokens) {if (isOper(token)) {const node = new BTNode(token, nodeType.operator, nodes.pop());
nodes.push(node);
} else if(token === '(') {nodes.push('(');
} else if(token === ')') {let node = nodes.pop();
let preNode;
try {while ((preNode = nodes.pop()) !== '(') {
preNode.right = node;
node = preNode;
}
} catch(err) {throw 'bracket count not match';}
const top = nodes[nodes.length - 1];
if (shouldMerge(top)) {top.right = node;} else {nodes.push(node);
}
} else {const value = parseFloat(token);
if (Number.isNaN(value)) {throw `Invalid express for '${token}'`;
}
const node = new BTNode(value, nodeType.operand);
const top = nodes[nodes.length - 1];
if (shouldMerge(top)) {top.right = node;} else {nodes.push(node);
}
}
}
for (let i = 0; i < nodes.length - 1; i++) {const node = nodes[i];
node.right = nodes[i + 1];
}
return nodes[0];
}
文章到这里就完结了，心愿对大家有所帮忙~~~