《数据结构与算法JavaScript描述》- 第四章 栈练习

1. 栈可以用来判断一个算术表达式中的括号是否匹配。编写一个函数，该函数接受一个算术表达式为参数，返回括号缺失的位置。下面是一个括号不匹配的算术表达式的例子：2.3+ 23 / 12 + （3.14159*0.24

2. 一个算术表达式的后缀表达式形式如下：op1 op2 operator 使用两个栈，一个用来存储操作数，另外一个用来存储操作符，设计并实现一个Javascript函数，该函数可以将中缀表达式转换为后缀表达式，然后利用栈对该表达式求值。

3. 现实生活中栈的一个例子是佩斯糖果盒。想象一下你有一盒佩斯糖果，里面塞满了红色、黄色和白色的糖果，但是你不喜欢黄色的糖果。使用栈（有可能用到多个栈）写一段程序，在不改变盒内其他糖果叠放顺序的基础上，将黄色糖果移除。

{
     // 首先实现一个栈
    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))
}

中缀表达式转换后缀表达式的实现，不理解，后面还需要思考