中缀表达式转前缀表达式

计算机算法实现步骤

1. 构造两个栈，s1,s2分别存储运算符与操作数
2. 从右至左扫描中缀表达式
   2.1 如果当前值为数值，读取，直到遇到运算符，将其转为一个数值并存入s2
   2.2 如果是运算符，则比较优先级
   2.2.1 如果当前运算符的优先级大于等于s1栈顶运算符的优先级，则将运算符直接入栈；
   2.2.2 否则将栈顶运算符出栈并输出，直到当前运算符的优先级大于等于栈顶运算符的优先级（如果栈顶是括号直接入栈），再将当前运算符入栈。
   2.3 如果是括号，则根据括号的方向进行处理。如果是右括号，则直接入栈；否则，遇左括号前将所有的运算符全部出栈并输出，遇右括号后将左右的两括号一起删除。
3. 重复上述操作2直至扫描结束，将栈内剩余运算符全部出栈并输出，再逆缀输出字符串。中缀表达式也就转换为前缀表达式了。

代码实现：

function toPloishNotation(input){
    var len = input.length;
    var c, tmpChar;
    var s1 = new Array(); //存放运算符
    var s2 = new Array(); //存放操作数
    var expression = new Array();
    var number;
    var lastIndex = -1;
    for(var i=len-1; i>=0; --i){
        c = input.charAt(i);
        if(!isNaN(c)) {
            lastIndex = readDoubleReverse(input, i);
            number = parseFloat(input.substring(lastIndex,i+1));
            s2.push(number);
            i = lastIndex;
            expression.push(number);
        }else if (isOperator(c)) {
            while(s1.length!=0 && s1[s1.length-1] != ')' && priorityCompare(c, s1[s1.length-1])<0){
                expression.push(s1[s1.length-1]);
                s2.push(calc(s2.pop(),s2.pop(),s1.pop()));
            }
            s1.push(c);
        } else if(c == ')'){
            s1.push(c);
        } else if (c == '('){
            while((tmpChar=s1.pop())!=')'){
                expression.push(tempChar);
                s2.push(calc(s2.pop(),s2.pop(),tempChar));
            }
        } else if (c == ' ') {
            //ignore
        } else {
            alert("error char");
        }
    }
    while(s1.length!=0){
        tempChar = s1.pop();
        expression.push(tempChar);
        s2.push(calc(s2.pop(),s2.pop(),tempChar));
    }
    // while(!expression.isEmpty()){
    //     //输出前缀表达式
    // }
    var result = s2.pop();
    var display = document.getElementById("display");
    display.innerHTML = result;
}

//处理小数,遇到操作符返回
function readDoubleReverse(input, start){
    var dotIndex = -1;  //避免多个小数点
    var c;
    for(var i=start; i>=0; --i){
        c = input.charAt(i);
        if(c == '.') {
            if (dotIndex != -1) 
                alert("more than 1 dots);")
            else
                dotIndex = i;
        } else if(isNaN(c)) {
            return i+1; 
        } else if(i == 0){
            return 0;
        }
    }
    alert("not a number");
}

//检测是否是操作符
function isOperator(c){
    return (c=='+' || c=='-' || c=='*' || c=='/');
}

//优先级比较
function priorityCompare(op1,op2){
    switch(op1){
        case '+': case '-':
            return (op2 == "*" || op2 == '/' ? -1:0);
        case '*': case '/':
            return (op2 == "+" || op2 == '-' ? 1:0);
    }
    return 1;
}

//数值计算
function calc(num1, num2, op){
    switch(op) {
        case '+':
            return num1 + num2;
        case '-':
            return num1 - num2;
        case '*':
            return num1 * num2;
        case '/':
            if(num2 == 0) alert("division is zero");
            else
                return num1/num2;
        default:
            return 0;
    }
}