逆波兰式

逆波兰式，是计算机计算四则混合运算（括号优先，乘除优先加减）时，对我们常规表达式（符号在中间）的一种转换方式。主要用到栈这种数据结构。
除了这种方式，网上讲用二叉树也可以实现计算机的四则混合运算，后续研究。链接博客

生成逆波兰式

1. 一个栈存储符号，一个数组存储结果
2. 对常规表达式（中缀表达式）数组，从左往右遍历
3. 若是数字，直接放入结果数组
4. 若是符号，对符号进行操作如下。
5. 左括号，’(‘，直接压入操作符号栈
6. 右括号，’）’，则将距离栈顶的最近的’(‘之间的运算符，逐个出栈，依次放入结果数组，此时抛弃’(‘’)’；
7. 加减乘除，若栈为空，或者栈顶是左括号’(‘，直接入栈。否则与栈顶元素比较优先级，当前优先级大，则直接入栈。当前优先级小于或者等于，则将栈中元素依次弹出，存入结果数组，直至栈空，或者遇到栈顶为左括号’(‘，或者栈顶优先级小于（不包含等于）当前元素。此后再将当前运算符放入符号栈中（注意：不是结果数组）
8. 遍历完成后，判断符号存储栈中是否有元素，若有，依次弹出，并放入结果数组

//逆波兰式生成
//仅仅考虑+-*/()

function create(arr){
    var result = [];//结果数组
    var stack = [];//操作符号栈

    for(var i = 0 ; i < arr.length;i++){
        var now = arr[i];
        if(isnum(now)){
            result.push(now);//1.数字，直接放入结果数组
        }else{

            //2.符号相关处理
            //2.1.左括号直接压入操作符号栈
            if(now == '('){
                stack.push(now);
            }

            //2.2.右括号，将操作符号栈左括号‘(’之间操作符放入结果数组，并抛弃左右括号'('')'
            if(now == ')'){
                var temp = stack.pop();
                while(temp != '('){
                    result.push(temp);//把操作栈中左括号中间的符号输出
                    temp = stack.pop();
                }

            }
            //2.3.加号，减号,乘号，除号
            //2.3.1.栈为空,或者栈顶为左括号‘(’,直接压入
            //2.3.2.比较now和栈顶,当now优先级高于（不包括等于）栈顶，直接压入
            //2.3.3.优先级小于等于栈顶，弹出栈顶压入结果数组，直至栈顶优先级低于（不包括等于）now,或者遇到左括号‘(’,或者操作栈空。此后，将now压入操作符号栈（不是结果数组）
            //此处只考虑，加减乘除。
            if(now == '-' || now == '+' || now == '*' || now == '/'){
                if(stack.length == 0 || stack[stack.length-1] == '('){
                    stack.push(now);
                }else{
                    var temp2 = stack[stack.length-1];

                    if(now == '*' || now == '/'){
                        if(temp2 == '*' || temp2 == '/'){

                        result.push(stack.pop());

                        while(true){
                            if(stack.length == 0){
                                break;
                            }
                            temp2 = stack[stack.length-1];

                            if(temp2 == '(' || temp2 == '+' || temp2 == '-'){
                                break;
                            }
                            result.push(stack.pop());
                        }
                        //压入
                        stack.push(now);

                        }else{//加减，优先级低
                            stack.push(now);
                        }

                    }

                    if(now == '+' || now == '-'){
                        result.push(stack.pop());
                        while(true){
                            if(stack.length == 0){
                                break;
                            }
                            temp2 = stack[stack.length-1];

                            if(temp2 == '('){
                                break;
                            }
                            result.push(stack.pop());
                        }
                        //压入
                        stack.push(now);
                    }
                }
            }
        }
    }
    //stack中全部输出
    while(stack.length>0){
        result.push(stack.pop());
    }
    return result;
}

//是不是数字
function isnum(a){
    if(a == '(' || a == ')' || a == '+' || a == '-' || a == '*' || a == '/'){
        return false;
    }
    return true;
}
//测试
//var h = create('9+(3-1)*3+10/2'.split(''));//数字10被分为1,0
var h = create(['9','+','(','3','-','1',')','*','3','+','10','/','2']);
//h:9 3 1 - 3 * + 10 2 / +
//["9", "3", "1", "-", "3", "*", "+", "10", "2", "/", "+"]

//var h = create('1+2-5*(5-4)*6-(6-1)'.split(''));
//h:1 2 + 5 5 4 - * 6 * - 6 1 - -
//["1", "2", "+", "5", "5", "4", "-", "*", "6", "*", "-", "6", "1", "-", "-"]

逆波兰式计算

//逆波兰式运算
//str 是右序表达式的数组
function result(str){
var len = str.length;

var stack = [];//数值放入栈，遇到符号，出栈两个数字，计算
    for(var i = 0;i<len;i++){
        if(str[i] != '+' && str[i] != '-' && str[i] != '*' && str[i] != '/'){
            stack.push(str[i]);
        }else{
            //字符转数字
            var p2 = Number(stack.pop());//注意此处顺序，先pop是被操作数（被加减乘除）
            var p1 = Number(stack.pop());

            switch(str[i]){
                case '+':
                    p1 +=p2;
                    break;
                case '-':
                    p1 -=p2;
                    break;
                case '*':
                    p1 *=p2;
                    break;
                case '/':
                    p1 /=p2;
                    break;

            }
            stack.push(p1);
        }

    }
    return stack.pop();


}
var s = result(["9", "3", "1", "-", "3", "*", "+", "10", "2", "/", "+"]);//20
var s1 = result(["1", "2", "+", "5", "5", "4", "-", "*", "6", "*", "-", "6", "1", "-",   "-"]);//-32
console.log(s+"::::"+s1);