直接上代码。
/*
* 数组实现的栈: 顺序栈
* 链表实现的栈: 链式栈
* 栈: 当某个数据集只涉及在一端插入和删除数据, 并且满足后进先出, 就该使用栈这种数据结构
* 时间复杂度 O(1)
*/
class ArrayStack {
constructor () {
// 数组
this.items = []
// 栈顶位置
this.top = 0
// 栈内元素个数
this.count = 0
}
// 入栈: 栈顶位置更新
push (item) {
this.items[this.top++] = item
this.count++
}
// 出栈: 返回出栈元素, 同时刷新栈顶位置
pop () {
if (this.count <= 0) { return false }
this.count--
return this.items[--this.top]
}
// 获取栈顶元素
peek () {
return this.items[this.top - 1]
}
}
// 案例1: 进制转换 如32 => 2进制, 100000, 125 => 8 进制, 175
function mulBase (source, base) {
const s = new ArrayStack()
let res = ''
while (source > 0) {
s.push(source % base)
source = Math.floor(source /= base)
}
while (s.count) {
res += s.pop()
}
return res
}
console.log(mulBase(32, 2), mulBase(125, 8))
// 案例2: 回文字符串, 如'dad' ‘1001’, 从前写=从后写
function isPalindrome(word) {
const s = new ArrayStack()
let reverseWord = ''
for (let i = 0; i < word.length; i++) {
s.push(word[i])
}
while (s.count) {
reverseWord += s.pop()
}
return Object.is(reverseWord, word)
}
console.log(isPalindrome('dad'), isPalindrome('racecar'))
// 案例3: 栈模拟阶乘 如factorial(5)=120
function factorial (n) {
if (n <= 0) { return }
const s = new ArrayStack()
let res = 1
while (n) {
s.push(n--)
}
while (s.count) {
res *= s.pop()
}
return res
}
console.log(factorial(5), factorial(2)) // 120 2
// 案例4: 使用栈判断一个算术表达式的括号是否匹配, 并且返回括号丢失的位置 如2.3+(23/12+(3.14159×0.24)
function matchBracket (str) {
const index = new ArrayStack()
const s = new ArrayStack()
let res = []
for (let i = 0; i < str.length; i++) {
if (str[i] === '(') {
s.push(str[i])
index.push(i)
} else if (str[i] === ')') {
if (s.count <= 0) {
index.push(i)
} else {
s.pop()
index.pop()
}
}
}
if (index.count) {
while (index.count) {
res.push(index.pop())
}
return res.reverse().join(',')
}
return true
}
console.log(matchBracket('1 + (31.1415926 * 0.24))',), matchBracket('1 + (31.1415926 * 0.24'), matchBracket('1 + (31.1415926 * 0.24)'))
// 案例5: 把中缀表达式转后缀表达式, 并计算结果
// 中缀表达式(Infix Notation)就是我们数学课上学到的最常见的将操作符放在操作数中间的算术表达式。
// 后缀表达式(Postfix Notation)与之相反，是指运算符写在操作数后面的不含括号的算术表达式，也叫做逆波兰表达式。比如1 2 3 + -
/*
* 假设有一个中缀表达式a+b*c-(d+e)：
*
* 1. 首先将这个中缀表达式的所有运算加括号((a+(b*c))-(d+e))
* 2. 然后将所有运算符放到括号后面，这样就变成了((a(bc)* )+ (de)+ )-
* 3. 把所有括号去掉abc*+de+-，最后得出的结果就是后缀表达式。
*/
// 中缀表达式转换成后缀表达式，这里假设数字都只有1位且没有空格，例如：'1+2*3-(4+5)'
// 中缀表达式转换成后缀表达式，这里假设数字都只有1位且没有空格，例如：'1+2*3-(4+5)'
function transferHouzhuiExp(str) {
let input = str.split(''),
output = new ArrayStack(),
temp = new ArrayStack(); // output表示输出，temp表示临时存放操作符的堆栈
let yxj = {'+': 1, '-': 1, '*': 2, '/': 2}; // 优先级
input.forEach(current => {
if(/\d/g.test(current)) output.push(current); // 如果是数字，直接输出
else if(current == '(') temp.push(current); // 如果左括号，放入堆栈
else if(current == ')') { // 如果是右括号，循环输出，直至匹配到左括号才停止
while(temp.count > 0) {
let op = temp.pop();
if(op == '(') break;
output.push(op);
}
} else { // 否则，如果是加减乘除，需要针对优先级做不同处理
while(temp.count >= 0) {
let op = temp.peek();
// 如果堆栈为空，或者上一个操作符是(，或者当前操作符优先级比栈顶操作符优先级要高
if(!temp.count || op == '(' || yxj[current] > yxj[op]) {
temp.push(current);
break;
} else output.push(temp.pop());
}
}
});
// 输入循环结束后，如果操作符堆栈不为空，还要循环输出
while(temp.count > 0) output.push(temp.pop());
// console.log(output) // [ '1', '2', '3', '*', '+', '4', '5', '+', '-' ]
return output;
}
function parseExpress(input) {
let reverseInput = new ArrayStack();
let output = new ArrayStack();
while (input.count) {
reverseInput.push(input.pop())
}
while (reverseInput.count) {
let item = reverseInput.pop()
if(/\d/g.test(item)) output.push(item);
else {
let n2 = output.pop();
let n1 = output.pop();
output.push(count(n1, n2, item));
}
}
// 这里偷懒，直接使用eval
function count(n1, n2, op) {return eval(n1+op+n2);}
return output.peek();
}
console.log(parseExpress(transferHouzhuiExp('1+2*3-(4+5)'))); // -2
