在学习栈中,中序表达式转后缀表达式应该是一个经典例子,我把我自己的思路整理了一个,用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'));