天天看点

javascrip学习栈:中序表达式转换为逆波兰表达式(后缀表达式)

在学习栈中,中序表达式转后缀表达式应该是一个经典例子,我把我自己的思路整理了一个,用switch进行分而治之方式进行处理,所有的思路都在程序注释中解释了,自认为这样更容易理解,但应该还有更好的方式,肯请大家指点,谢谢。

function My_stack() {
    let items = [];  // 使用数组存储数据

    // push方法向栈里压入一个元素
    this.push = function (item) {
        items.push(item);
    };

    // pop方法把栈顶的元素弹出
    this.pop = function () {
        return items.pop();
    };

    // top 方法返回栈顶元素
    this.top = function () {
        return items[items.length - 1];
    };

    // isEmpty返回栈是否为空,空为true,不空为false
    this.isEmpty = function () {
        return items.length == 0;
    };

    // size方法返回栈的大小
    this.size = function () {
        return items.length;
    };

    // clear 清空栈
    this.clear = function () {
        items = []
    };
    this.print = function () {//打印栈的内容
        console.log('栈', items.toString());
    }
}

function RPN(exp) {
    let stack = new My_stack;
    let str = [];
    let item = '';
    for (let i = 0; i < exp.length; i++) {
        item = exp[i];
        //判断是否是数字,数字直接入栈,否则就对运算符操作,这里用了分而治之的思想
        if (!isNaN(item)) {
            str.push(item);
            // console.log('数组->', str);

        } else {
            //三别处理三种情况
            //1、+-级别最低,弹出除(外的所有+-*/入数组,自身入栈。
            //2、*/级别最高,弹出所有*/入数组,自身入栈。
            //3、遇到()是这样处理,(直接入栈,)弹出所有+-*/,直到栈顶元素是(并弹出
            switch (item) {
                case '+':
                case '-':
                    while (!stack.isEmpty() && stack.top() != '(') {//栈不空并且不等于(,弹出入数组
                        str.push(stack.pop());
                    }
                    stack.push(item);//自身入栈
                    break;
                case '*':
                case '/':
                    if (!stack.isEmpty() && ['*','/'].indexOf(stack.top()) >= 0) {//栈不空并且栈顶是*/,弹出入数组
                        str.push(stack.pop());
                    }
                    stack.push(item);//自身入栈
                    break;
                case '(':
                    stack.push(item);//直接入栈
                    break;
                case ')':
                    let a = stack.pop();
                    while (a != '(') {//弹出所有+-*/,直到遇到(,并且弹出(不入栈
                        str.push(a);
                        a = stack.pop();
                    }
            }
            // stack.print();
        }
    }

    while (!stack.isEmpty()) {
        str.push(stack.pop())
    }
    return str.toString();
}
console.log(RPN('(1+(4*5*3+2)/4-3)+(6+8)*3'));      

继续阅读