我会回顾了自己之前写的这篇文章，后面的代码部分if else 实在是太多了，不够简洁。有时间改一下
什么叫做中缀表达式
中缀表达式是人们常用的算术表示方法。
例如:1 + 2 * 3 - 4
什么叫做后缀表达式
后缀表达式（将运算符写在操作数之后），也可称逆波兰式（Reverse Polish notation，RPN，或逆波兰记法）。
例如:1 2 3 * + 4 - （就是上面的中缀转换过来的)
为什么要使用后缀表达式
1 + 2 * 3 - 4这种格式，大家看一下就知道如何计算，数字小的情况下甚至能很快算出结果。既然如此我们为什么要把中缀表达式转换成后缀表达式呢？
这是因为中缀表达式虽然简单，但是那是对于人类的思维方式来说，中缀表示非常易于理解。可是你的计算机可不是这么想的，中缀表达式对于他来说非常复杂，无异于看天书。相反，后缀表达式在计算机中就像人类看中缀表达式一样。简单易懂。原因是计算机采用的内存结构普遍是栈式结构，先进后出。
中缀表达式如何转换为后缀表达式
说了这么多的理论知识，大家一定很想知道这么易于机器阅读的算数表达公式我该如何拥有呢？下面我们就一步步的了解，转换过程。
1.首先我们创建一个符号栈存放符号
2.拿到中缀表达式 我们分割操作数和符号 从左至右进行操作
3.判断如果是操作数则直接输出
4.如果是符号则出现两三种情况
1.如果符号栈为空则将其入栈
2.如果符号栈不为空则于栈顶的符号进行优先级比较，如果符号优先级大于栈顶符号则直接入栈；如果符号优先级小于等于栈顶符号则将栈顶符号输出，然后将符号与新的栈顶符号继续比较，直到符号优先级大于栈顶符号或者栈空之后入栈。
5.如果遇到左括号则入栈
6.如果遇到右括号则将距离栈顶最近的右括号之间的所有符号依次出栈，然后丢弃左括号
7.循环3~6的操作直到结束
8.这时候我们就得到了后缀表达式
举栗说明
说了那么多我想还是有的小伙伴比较懵，所以我们举个例子好了
随便来一个公式: 1*2+16/4-6*2
我们将他从字符串拆分: 1 * 2 + 16 / 4 - 6 * 2
接着按照上面的步骤依次操作
1.
1直接输出| 输出: "1 " | 符号栈: [] |2.
*因为符号栈空所以入栈| 输出: "1 " | 符号栈:['*'] |3.
2直接输出| 输出: "1 2 " | 符号栈:['*'] |4.
+与符号栈顶进行比较:+优先级小于*所以输出*;因为符号栈空所以+入栈| 输出: "1 2 * " | 符号栈:['+'] |5.
16直接输出| 输出: "1 2 * 16 " | 符号栈:['+'] |6.
/与符号栈顶进行比较:/优先级大于+所以/入栈| 输出: "1 2 * 16 " | 符号栈:['+','/'] |7.
4直接输出| 输出: "1 2 * 16 4 " | 符号栈:['+','/'] |8.
-与符号栈顶进行比较:-优先级小于/所以输出/;-优先级等于+所以输出+;因为符号栈空所以-入栈| 输出: "1 2 * 16 4 / + " | 符号栈:['-'] |9.
6直接输出| 输出: "1 2 * 16 4 / + 6 " | 符号栈:['-'] |10.
*与符号栈顶进行比较:*优先级大于-所以*入栈| 输出: "1 2 * 16 4 / + 6 " | 符号栈:['-','*'] |11.
2直接输出| 输出: "1 2 * 16 4 / + 6 2 " | 符号栈:['-','*'] |12.表达式结束依次输出符号栈中符号
| 输出: "1 2 * 16 4 / + 6 2 * - " | 符号栈: [] |
结束了，我们现在已经得到后缀表达式了，整个过程其实并不是很复杂，第一接触可能会觉得有些绕，自己多转换几次，很快就可以掌握了。
计算后缀表达式
上一步我们通过转换得到了后缀表达式：1 2 * 16 4 / + 6 2 * -
也就是说我们得到了，易于计算机理解的数学公式，那么我们这时候就应该关心，计算机是如何处理这个公式的。其实很简单。
我们将上面的后缀表达式按照空格分割成为数组，循环依然是从左到右的顺序。如果当前为操作数，则压栈；如果是符号，则将两个栈顶的两个元素弹出做响应的运算，然后入栈；最后当表达式循环结束，栈中剩下的就是运算结果。这里要注意如果是除法和减法后弹出的操作数作为被减数与被除数
依然举栗说明
后缀表达式：1 2 * 16 4 / + 6 2 * -
1.
12直接入栈| 栈 : [ 1, 2 ] | 后缀表达式 : [ '*', 16, 4, '/', '+', 6, 2, '*', '-', ]2.遇到符号
*计算 ：1 * 2 = 3结果入栈| 栈 : [ 2 ] | 后缀表达式 : [ 16, 4, '/', '+', 6, 2, '*', '-', ]3.
164直接入栈| 栈 : [ 2, 16, 4 ] | 后缀表达式 : [ '/', '+', 6, 2, '*', '-', ]4.遇到符号
/计算 ：16 / 4 = 4结果入栈| 栈 : [ 2, 4 ] | 后缀表达式 : [ '+', 6, 2, '*', '-', ]5.遇到符号
+计算 ：3 + 4 = 7结果入栈| 栈 : [ 6 ] | 后缀表达式 : [ 6, 2, '*', '-', ]6.
62直接入栈| 栈 : [ 6, 6, 2 ] | 后缀表达式 : [ '*', '-', ]7.遇到符号
*计算 ：6 * 2 = 12结果入栈| 栈 : [ 6, 12 ] | 后缀表达式 : [ '-', ]8.遇到符号
-计算 ：6 - 12 = -6结果入栈| 栈 : [ -6 ] | 后缀表达式 : []
计算结束，结果为 -6 怎么样，是不是没有想象中的那么难。
代码部分
使用js实现我们的逻辑
我这边将从头到尾的步骤，拆分为4个函数
- stringToArray ： 字符串转换中缀表达式
- infixToSuffix ： 中缀表达式转换后缀表达式
- suffixResult ： 根据后缀表达式计算结果
- operatorCompare ： 运算符号优先级比较
具体实现我就不一步一步讲解了，思路就是根据，我上面讲到的转换方法。
/**
* 将公式字符串转换为数组 将公式中的数组转换为Number
*
* @param {string} str - 公式字符串
* @returns {Array} - 中缀表达式数组
*/
var start = null;//起始时间
var end = null; //结束时间
function stringToArray(str) {
//console.log("|",str,"| sÎtringToArray");
start = new Date().getTime();
if (str !== "" && str !== undefined) {
let data = str.split('');
var flag = "";
let arr = [];
data.forEach((tmp, index) => {
if (isNaN(tmp) && tmp !== '.') {
//如果是符号
if (flag !== "") {
arr.push(parseFloat(flag));
arr.push(tmp);
flag = "";
} else {
arr.push(tmp);
}
} else {
//如果是数字
flag = flag + tmp;
if (index >= data.length - 1) {
arr.push(parseFloat(flag));
}
}
})
console.log("中缀表达式字符串:", arr.join(" "));
return arr;
} else {
return [];
}
}
/**
* 将stringToArray方法中生成的数组 转换为后缀表达式
*
* @param {Array} arr - 中缀表达式数组
* @returns {String} - 后缀表达式字符串
*/
function infixToSuffix(arr) {
//console.log("|",arr,"| infixToSuffix");
if (arr.length > 0) {
let str = ""
let operator = []
arr.forEach((val) => {
if (isNaN(val)) {
//如果是符号
if (operator.length === 0 || val === "(") {
operator.push(val)
} else {
if (val === ")") {
let operatorLength = operator.length;
for (let index = 0; index < operatorLength; index++) {
let flag = operator.pop();
if (flag === "(") {
break;
} else {
str = str + flag + " ";
}
}
} else {
let operatorLength = operator.length;
for (let index = 0; index <= operatorLength + 1; index++) {
let tmp = operator.pop()
if (tmp === undefined) {
operator.push(val)
break;
} else if (tmp === "(") {
operator.push(tmp)
operator.push(val)
break;
} else {
let flag = operatorCompare(val, tmp)
if (flag) {
str = str + tmp + " ";
} else {
operator.push(tmp)
operator.push(val)
break;
}
}
}
}
}
} else {
//如果是数字
str = str + val + " ";
}
})
while (operator.length !== 0) {
str = str + operator.pop() + " ";
}
console.log("后缀表达式字符串:", str);
return str;
} else {
return ""
}
}
/**
* 计算后缀表达式
*
* @param {String} str - 后缀表达式字符串
* @returns {Float} - 结果数据
*/
function suffixResult(str) {
//console.log("|",str,"| suffixResult");
if (str !== "") {
let data = str.split(' ');
let stack = []
data.forEach((data) => {
if (!isNaN(parseFloat(data))) {
stack.push(parseFloat(data))
} else {
switch (data) {
case "+":
stack.push(parseFloat(stack.pop()) + parseFloat(stack.pop()))
break;
case "-":
let a = parseFloat(stack.pop()); let b = parseFloat(stack.pop())
stack.push(b - a);
break;
case "*":
stack.push(parseFloat(stack.pop()) * parseFloat(stack.pop()))
break;
case "/":
let aa = parseFloat(stack.pop()); let bb = parseFloat(stack.pop())
stack.push(bb / aa);
break;
default:
break;
}
}
})
let result = parseFloat(stack.pop())
end = new Date().getTime();
console.log("运算时间: " + (end - start) + "ms");
console.log("运算结果:", result);
return result.toString()
} else {
return ""
}
}
/**
* 比较传入的两个符号的优先级
*
* @param {String} a
* @param {String} b
* @returns {Boolean} - 返回true a<=b 返回false a>b
*/
function operatorCompare(a, b) {
let test1 = (a === "+" || a === "-") ? 1 : 2
let test2 = (b === "+" || b === "-") ? 1 : 2
return test1 <= test2
}
我想说的话
本人接触计算机行业也就2年的时间，能力有限，有一些更加优雅，更加简洁的写法我还需要慢慢学习，慢慢探索。如果有大佬看到这篇文章，发现内容上有错误，或者觉得我的代码有什么不足之处可以改进。希望您能留言，不胜感激。
注:本文部分术语资料查询自「百度百科」
❥O
By 苗洪波 at February 15th, 2020 at 08:59 pm.