0.前言
之前用js实现的一个简易计算器有许多处理得不好的地方，抛开样式的问题，计算器最核心的计算部分直接使用了eval()函数，今天自己来实现计算部分，目标是获取一个算式字符串，并让计算机得出结果。
在这之前，什么是中缀表达式，什么是后缀表达式？？
今天特地查阅了一下《数据结构教程》：
......在算术表达式中，运算符位于两个操作数中间的表达式称为中缀表达式（infix expression）...... 后缀表达式（postfix expression）或逆波兰表达式，就是在算术表达式中运算符在操作数的后面......
我们在日常生活中所使用的几乎都是中缀表达式。因为我们知道运算法则：括号内优先计算，先乘除后加减......计算机并不懂得我们的计算法则，后缀表达式才对它的胃口，转化好的后缀表达式已经事先考虑了优先级，不仅没有括号，而且位置越靠前的运算符越优先执行。
在达到我们的目标前，我们事先准备三个“容器”：
var infixExp[]; //存放中缀表达式字符
var postfixExp[]; //存放后缀表达式字符
var tempExp[]; //存放临时字符
备注：上面的数组应该理解成栈，js中数组的pop()和push()方法，下文会以出栈，入栈来称呼。
1.从一个算式说起
4.25*（3+1）
看到这个算式，我们的第一个问题来了，如何将其正确地存入到infixExp里？
也就是说我们需要的是['4.25','*','(','3','+','1',')']而不是['4','.','2','5','*','(','3','+','1',')']。
这里提供一种思路:
strTemp = "获取到的中缀表达式字符串";
function expSolve() {
var i=0;
var j=0;
if(strTemp[0] == '-'){
i = 1;
}//对负数的处理
for(; i<strTemp.length; i++){
if(strTemp[i]=='('&&strTemp[i+1]=='-'){
infixExp.push('(');
j = i+1;
i++;
continue;
}//对负数的处理
if(strTemp[i]=='+'||strTemp[i]=='-'||strTemp[i]=='*'||strTemp[i]=='/'||strTemp[i]=='('||strTemp[i]==')'){
if(strTemp.slice(j, i)!='')
infixExp.push(strTemp.slice(j, i));
infixExp.push(strTemp[i]);
j=i+1;
}
}
if(strTemp.slice(j)!='')
infixExp.push(strTemp.slice(j));
}
扫描字符串的每个字符，当遇到运算符和括号时+，-，*，/，（，）时，将该符号前部分和该符号依次插入到infixExp里，要做是否为空的判断(例如括号前可能会出现运算符)。最后剩下部分可能为运算符右侧的数也要插入数组。
可能还存在bug，慎用！一定有更好的方法
2.中缀表达式转换为后缀表达式
扫描infixExp中的每个元素：
- 遇到数，直接入栈
postfixExp。 - 遇到符号
+,-,*,/时：- 如果此时临时栈
tempExp为空，该符号直接入栈tempExp。 - 如果此时临时栈
tempExp不为空，该符号优先级高于tempExp中的栈顶元素或栈顶元素为(时，入栈tempExp。 - 如果此时临时栈
tempExp不为空，该符号优先级低于tempExp中的栈顶元素，将tempExp中的栈顶元素出栈，并入栈postfixExp，直到该符号优先级高于tempExp的栈顶元素或栈顶元素为(，才将该符号入栈。
- 如果此时临时栈
- 遇到括号
(或)时：
- 遇到左括号
(，直接入栈tempExp。 - 遇到右括号
)，右括号两个栈均不入，将tempExp中的栈顶元素出栈，并入栈postExp，直到遇到(。左括号只出栈但不进入postfixExp。
左括号只有当遇到右括号时才出栈。
扫描完infixExp中的所有元素后，将tempExp中的元素依次弹出入栈postfixExp
中缀转后缀的实现（js）
function infixTopostfix() {
var item;
for (var i = 0; i < infixExp.length; i++) {
if (!isNaN(infixExp[i])) {
postfixExp.push(infixExp[i]);
}
else if (infixExp[i] == '+' || infixExp[i] == '-' || infixExp[i] == '*' || infixExp[i] == '/'||infixExp[i]=='('||infixExp[i]==')'){
if (tempExp.length == 0) {
tempExp.push(infixExp[i]);
}
else if (infixExp[i] == '*' || infixExp[i] == '/') {
item = tempExp.pop();
if (item == '*' || item == '/') {
postfixExp.push(item);
}
else {
tempExp.push(item);
}
tempExp.push(infixExp[i]);
}
else if (infixExp[i] == '+' || infixExp[i] == '-') {
while (tempExp.length != 0) {
item = tempExp.pop();
if(item == '('){
tempExp.push(item);
break;
}
postfixExp.push(item);
}
tempExp.push(infixExp[i]);
}
else if(infixExp[i] == '('){
tempExp.push(infixExp[i]);
}
else if(infixExp[i] == ')'){
while (1) {
item = tempExp.pop();
if(item == '('){
break;
}
postfixExp.push(item);
}
}
}
}
while (tempExp.length != 0) {
postfixExp.push(tempExp.pop());
}
}
3.后缀表达式的计算
扫描postfixExp中的每个元素：
- 遇到数，入栈
tempExp。 - 遇到符号
+,-,*,/（后缀表达式一定不会含左右括号），从tempExp中依次取出两个数，并根据符号计算（后取出的数在符号左侧）。最后将该次结果入栈tempExp。
扫描结束，tempExp中只剩一个元素， 即为最终结果！
后缀表达式的计算（js）
function postfixCalc() {
for (var i = 0; i < postfixExp.length; i++) {
if (!isNaN(postfixExp[i])) {
tempExp.push(postfixExp[i]);
}
else {
var strRight = opeStack.pop();
var strLeft = opeStack.pop();
switch (postfixExp[i]) {
case '+':
opeStack.push(Number(strLeft) + Number(strRight));
break;
case '-':
opeStack.push(Number(strLeft) - Number(strRight));
break;
case '*':
opeStack.push(Number(strLeft) * Number(strRight));
break;
case '/':
opeStack.push(Number(strLeft) / Number(strRight));
break;
default:
alert("运算符号出错！");
}
}
}
var out = tempExp.pop(); //out即为最终结果
}
