对于一个算术表达式，人是可以很容易进行计算的，但是对于电脑来说，却不是直接可以理解的。
比如1+2*3，人可以直接进行1+(2*3)的计算，但是电脑根本不知道该如何进行计算。
有的童鞋会说JavaScript中可以用eval函数直接执行字符串啊，但是，如果是1+2x3这种写法呢？
思路分析
我们平时写的表达式也叫中缀表达式，它是一个通用的算术或逻辑公式的表示方法，操作符是以中缀的形式处在操作数中间。其中需要注意的是，中缀表达式中括号在表示优先顺序时是必须的。
除了中缀表达式，还有前缀表达式，前缀表达式中的操作符是处在操作数前面，而前缀表达式中，不需要用括号来规定优先级。
对于前缀表达式，这里需要引入一个名词：“波兰表达式”。以下摘自维基百科：
波兰表示法（Polish notation，或波兰记法），是一种逻辑、算术和代数表示方法，其特点是操作符置于操作数的前面，因此也称做前缀表示法。
如果操作符的元数（arity）是固定的，则语法上不需要括号仍然能被无歧义地解析。
其实对于一颗二叉树表示的算术表达式，其波兰式就是这颗二叉树的前序遍历结果。在运算波兰表达式时，无需记住运算的层次，只需要直接寻找第一个运算的操作符。
比如算术表达式1+2*3-4/5，它所对应的一种波兰式为-+1*23/45，那么它的计算方式如下：
前缀表达式的计算就是从左往右顺序查找第一个后面紧跟着两个操作数的操作符，并做计算，将计算结果替换这个操作符和两个操作数。
同时，在正确的前缀表达式中，操作数必然比操作符多一个，所以必然能找到一个操作符符合运算条件；而替换时，两个操作数和一个操作符替换为一个操作数，所以减少了各一个操作符和操作数，仍然可以迭代运算直至计算整个式子。
不过，前缀表达式基本没有在商业计算器中使用过，商业计算器中用到的是我们即将了解的另一种表示方法：“逆波兰式”。
逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式。
在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。
逆波兰表达式的解释器一般是基于堆栈的。解释过程一般是：操作数入栈；遇到操作符时，操作数出栈，求值，将结果入栈；当一遍后，栈顶就是表达式的值。因此逆波兰表达式的求值使用堆栈结构很容易实现，并且能很快求值。
而中缀表达式可以通过调度厂算法转换成后缀表达式。如下：
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>中缀表达式转逆波兰式</title>
</head>
<body>
<p>中缀表达式：<span>1*2+(3*4-6/5)</span></p>
<p>逆波兰式结果:<span id="result"></span></p>
<script>
const opMap = new Map([
['+', 4],
['-', 4],
['*', 3],
['/', 3],
['(', 1],
[')', 1]
])
// 中缀表达式转后缀表达式(逆波兰式)
function LDR2RPN(ldr = '') {
const result = []
const stack = []
ldr = '(' + ldr + ')'
for (let i of ldr) {
// 如果为操作符
if (opMap.has(i)) {
// 如果栈为空或者操作符是(
// 则将操作符压入栈中
if (!stack.length || i === '(') {
stack.push(i)
}
// 如果操作符是)
// 则需要将栈中操作符依次弹出压入输出结果
// 直到匹配第一个(
// 如果没有则说明中缀表达式有错误
else if (i === ')') {
let op
while (true) {
op = stack.pop()
if (op === undefined) {
throw new Error('expression is error')
return;
} else if (op !== '(') {
result.push(op)
} else {
break
}
}
}
// 如果是其它操作符
// 则需要与栈顶操作符比较优先级
// 如果优先级比栈顶高，则压入栈
// 如果优先级比栈顶低，则依次弹出栈中操作符并推入输出结果
// 并重新比较优先级，直到栈为空
else {
while (true) {
const topOp = stack.slice(-1)[0]
const topPriority = opMap.get(topOp)
const curPriority = opMap.get(i)
// 此处因为我们在中缀表达式外包裹了一层()
// 所以不用判断栈为空，直接匹配(即可
if (topOp === '(' || topPriority > curPriority) {
stack.push(i)
break
} else {
result.push(stack.pop())
}
}
}
} else {
result.push(i)
}
}
return result
}
document.querySelector('#result').innerText = LDR2RPN('1*2+(3*4-6/5)')
</script>
</body>
</html>
现在我们已经可以将一个算术表达式转换成逆波兰式了，下面就是介绍对逆波兰式的求值，求值原理在上面已经提到过了，这里再详细讲解一次：
从左往右遍历逆波兰式每一项，
如果是操作数，则压入栈；
如果是操作符，从栈中取出两个操作数，求值，并将结果重新入栈；
当逆波兰式遍历结束时，栈顶就是逆波兰式的结果。
代码实现如下：
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>算术计算与二叉树</title>
</head>
<body>
<p>中缀表达式：<span>1*2+(3*4-6/5)</span></p>
<p>逆波兰式：<span>[1,2,*,3,4,*,6,5,/,-,+]</span></p>
<p>运算结果：<span id="result"></span></p>
<script>
const opMap = new Map([
['+', 4],
['-', 4],
['*', 3],
['/', 3],
['(', 1],
[')', 1]
])
// 计算逆波兰式结果
function computeRPN(rpn = []) {
const stack = []
for (let i of rpn) {
// 如果是操作符
// 则取出栈中两个操作数做计算
// 将结果重新入栈
if (opMap.has(i)) {
const num1 = stack.pop()
const num2 = stack.pop()
// 此处注意顺序，对于不满足交换律的操作符，顺序很重要！！！
stack.push(eval(`${num2}${i}${num1}`))
} else {
stack.push(i)
}
}
return stack.pop()
}
document.querySelector('#result').innerText = computeRPN([1, 2, '*', 3, 4, '*', 6, 5, '/', '-', '+'])
</script>
</body>
</html>
总结
现在我们已经实现了中缀表达式转后缀表达式并对后缀表达式求值的全部过程，下面就是对这部分的总结，代码很简单，就不写了。
这篇博文最主要的不是实现对算术表达式的求值，而是对计算器计算原理的探究。
因为上面提到的操作符，我们完全可以自己重新定义，也就是我们可以自己定义一套运算法则。
至于实际中如何运用，大家自己去探究了。