-
栈可以用来判断一个算术表达式中的括号是否匹配。编写一个函数，该函数接受一个算术表达式为参数，返回括号缺失的位置。下面是一个括号不匹配的算术表达式的例子：2.3+ 23 / 12 + （3.14159*0.24
-
一个算术表达式的后缀表达式形式如下：op1 op2 operator 使用两个栈，一个用来存储操作数，另外一个用来存储操作符，设计并实现一个Javascript函数，该函数可以将中缀表达式转换为后缀表达式，然后利用栈对该表达式求值。
-
现实生活中栈的一个例子是佩斯糖果盒。想象一下你有一盒佩斯糖果，里面塞满了红色、黄色和白色的糖果，但是你不喜欢黄色的糖果。使用栈（有可能用到多个栈）写一段程序，在不改变盒内其他糖果叠放顺序的基础上，将黄色糖果移除。
{
// 首先实现一个栈
function Stack() {
this.dataStore = []
this.top = 0
this.push = push
this.pop = pop
this.peek = peek
this.length = length
this.clear = clear
}
function push(element) {
this.dataStore[this.top++] = element
}
function pop(params) {
return this.dataStore[--this.top]
}
function peek() {
return this.dataStore[this.top - 1]
}
function length() {
return this.top
}
function clear() {
this.top = 0
}
// 数值间的相互转换
// 利用栈将一个数字从一种数值转换成另一种数值。假设想将数组n转换为以b为基数的数字，实现的转换算法如下：
// 1. 最高位为n%b,将此位压入栈
// 2. 使用n/b代替n
// 3. 重复步骤1和1，直到n等于0，且没有余数
// 4. 持续将栈内元素弹出，直到栈为空，依次将这些元素排列，就得到转换后数字的字符串形式
// 此算法只针对基数为2～9的情况
function mulBase(num, base) {
var s = new Stack();
do {
s.push(num % base)
num = Math.floor( num/ base)
} while (num > 0)
var converted = ''
while (s.length() > 0) {
converted += s.pop()
}
return converted
}
// 测试用例
// var num = 32;
// var base = 2
// var newNum = mulBase(num, base)
// console.log(newNum)
// 利用stack类，判断给定字符串是否是回文的程序
function isPalindrome(word) {
var s = new Stack()
for(var i = word.length - 1; i >= 0; i--) {
s.push(word[i])
}
var rword = ''
while (s.length() > 0) {
rword += s.pop()
}
console.log(word)
console.log(rword)
}
// 测试用例
// isPalindrome('hello')
// 普通递归
function factorial(n) {
if (n === 0) {
return 1
} else {
return n * factorial(n - 1)
}
}
// 测试用例
// console.log(factorial(5))
// 用栈来模拟递归
function fact(n) {
var s = new Stack()
while(n > 1) {
s.push(n--)
}
var product = 1
while (s.length() > 0) {
product *= s.pop()
}
return product
}
// 思考：用栈来模拟递归，将需要递归的数据存储在栈里，再将栈中的元素弹出去做递归计算。
// 测试用例
// console.log(fact(5))
// 1. 栈可以用来判断一个算术表达式中的括号是否匹配。编写一个函数，该函数接受一个算术表达式为参数，返回括号缺失的位置。下面是一个括号不匹配的算术表达式的例子：2.3+23/12+(3.14159*0.24
function isMatch(express) {
var str = String(express)
var s = new Stack()
for(var i = 0; i < str.length; i++) {
if(str[i] === '(') {
s.push(i) // 注意 这里存储的是扩号的位置
} else if (str[i] === ')') {
s.pop()
}
}
console.log(`在第${s.peek()}个字符是不匹配的括号`)
}
// isMatch('2.3+23/12+(3.14159*0.24')
// 2. 一个算术表达式的后缀表达式形式如下：op1 op2 operator
// 使用两个栈，一个用来存储操作数，另外一个用来存储操作符，设计并实现一个Javascript函数，该函数可以将中缀表达式转换为后缀表达式，然后利用栈对该表达式求值。
// 3.现实生活中栈的一个例子是佩斯糖果盒。想象一下你有一盒佩斯糖果，里面塞满了红色、黄色和白色的糖果，但是你不喜欢黄色的糖果。使用栈（有可能用到多个栈）写一段程序，在不改变盒内其他糖果叠放顺序的基础上，将黄色糖果移除。
// 先取糖果 如果不是黄色就将糖果放到A栈，如果是黄色糖果就将糖果放到B栈，直到将原栈的长度为0
// 再将A栈的糖果依次放入到oirgin原栈
const boxS = new Stack();
boxS.push('red');
boxS.push('yellow');
boxS.push('white');
boxS.push('white');
boxS.push('yellow');
boxS.push('yellow');
boxS.push('red');
boxS.push('red');
boxS.push('white');
boxS.push('yellow');
boxS.push('red');
function Tangguo(sourceStack) {
var tempStack = new Stack()
var yellowStack = new Stack()
while (sourceStack.length() > 0) {
if(sourceStack.peek() === 'yellow') {
yellowStack.push(sourceStack.pop()) // 移除黄色糖果
} else {
tempStack.push(sourceStack.pop()) // 暂时保留其它颜色糖果
}
}
var newStack = new Stack()
while (tempStack.length() > 0) {
newStack.push(tempStack.pop())
}
return newStack
}
console.log(Tangguo(boxS))
}
中缀表达式转换后缀表达式的实现，不理解，后面还需要思考
网友评论