中缀表达式转换为后缀表达式并求值

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中的每个元素：

1. 遇到数，直接入栈postfixExp。
2. 遇到符号+,-,*,/时：
   • 如果此时临时栈tempExp为空，该符号直接入栈tempExp。
   • 如果此时临时栈tempExp不为空，该符号优先级高于tempExp中的栈顶元素或栈顶元素为(时，入栈tempExp。
   • 如果此时临时栈tempExp不为空，该符号优先级低于tempExp中的栈顶元素，将tempExp中的栈顶元素出栈，并入栈postfixExp，直到该符号优先级高于tempExp的栈顶元素或栈顶元素为(，才将该符号入栈。
3. 遇到括号(或)时：

• 遇到左括号(，直接入栈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中的每个元素：

1. 遇到数，入栈tempExp。
2. 遇到符号+, -, *, /（后缀表达式一定不会含左右括号），从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即为最终结果
}