第一、意义
给你一个字符串,比如(9+(3-1))(3+(210/2))，如何计算他的值，必须是一般化的实现，不能说直接识别数字，然后怎样怎样。这里需要用到栈结构，就是中缀表达式转后缀，然后计算。
后缀表达式的计算规则，遇到数字就入栈，遇到操作符，就取出倒数第二个，作为第一个参数，倒数第一个，作为第二个参数，然后第一个操作第二个参数，这样来执行。
关键就是如何来计算出后缀表达式。
第二、实现中缀转后缀
规则：遇到数字，直接加入结果，遇到操作符，入栈，遇到优先级低于栈顶，或者右括号的情况，出栈，这部分书上讲得也有点不够细，网上很多人也基本瞎扯淡，我说一下。
stack是栈，final是最后的要输出的后缀表达式数组。
逻辑是这样的：
1、如果遇到( * /也就是左括号，乘除，直接入栈。
2、遇到），比如stack此时是( * ，这个时候）来了，就要把中间的所有操作符全部依次出栈加入final，()会抵消，也就是说，stack结束后变成了空
3、遇到 +或者-，就要比较栈顶操作符和他的优先级，比如此时栈顶是 * ，而此时是+操作符，那么这个时候，栈内东西依次全部出栈，除了（！注意，除了左括号！！左括号此时还是要留在里头的，遇到左括号就必须停下来。操作完了之后，这个+操作符会进入栈。
第三、代码实现
1、网上很多代码比较粗糙，没有考虑到直接split数组，把数字本身也拆开了的情况，比如''3+(2*10/2)"，就这个，你一split，把10都拆成0和1了，所以我重写了一下字符串的split，弄成了strongSplit方法。
2、还有的，瞎扯淡，乱写逻辑，乱push值都不对。
//这个suffix方法就是转后缀表达式数组
function suffix(str) {
let stack = [],
final = [],
strArr = strongSplit(str);
for(let i = 0;i < strArr.length;i++) {
if (')' === strArr[i]) {
while(true) {
var top = stack.pop();
if ('(' !== top) {
final.push(top);
}else {
break;
}
}
}else if (['-','+'].indexOf(strArr[i]) > -1) {
//如果新来的是这两个中的一个
if (['*','/'].indexOf(stack[stack.length - 1]) > -1) {
//优先级比不过栈顶
while(stack.length > 0 && stack[stack.length - 1] !== '(') {
final.push(stack.pop());
}
}
stack.push(strArr[i]);
}else if (['(','*','/'].indexOf(strArr[i]) > -1) {
//如果是这几个，没有比他们大的，不需要向前看，直接加入栈
stack.push(strArr[i]);
}else {
//就是数字
final.push(strArr[i]);
}
}
while(stack.length > 0) {
final.push(stack.pop());
}
return final;
}
//拆解字符串的方法，防止数字本身也split，当然其他方法也可以，只要你够普通
function strongSplit(str) {
var reg = /[\d]+/;
var reg1 = /[+|\-|*|/|(|)]/;
var arr = [];
var tempStr = '';
var s;
for(let i = 0;i < str.length;i++) {
if (s = reg1.exec(str[i])) {
//说明就是个符号
arr.push(s[0])
}else if (reg.test(str[i]) && reg.test(str[i + 1])) {
//说明后头一个还是数字
tempStr += str[i];
}else if (reg.test(str[i]) && !reg.test(str[i + 1])) {
//说明下一个已经不是了
tempStr += str[i];
arr.push(tempStr);
tempStr = '';
}
}
return arr;
}
//计算后缀表达式最终值的算法
function computeSuffix(arr) {
let reg = /[\d]+/,
stack = [];
for(let char of arr) {
if (reg.test(char)) {
//数字
stack.push(char);
}else {
//符号
var res,
num1 = parseInt(stack.pop()),
num2 = parseInt(stack.pop());
if (char === '*') {
res = num2 * num1;
}else if (char === '/') {
res = num2 / num1;
}else if (char === '+') {
res = num2 + num1;
}else if (char === '-') {
res = num2 - num1;
}
stack.push(res);
}
}
return stack[0];
}
var s = '(9+(3-1))*(3+(2*10/2))'
console.log(computeSuffix(suffix(s)))
网友评论