第十天——栈和队列（有效的括号，删除字符串中的所有相邻重复项，逆波兰表达式求值）

20. 有效的括号

学习链接

https://programmercarl.com/0020.有效的括号.html

个人思路

维护一个栈，遇到括号左边就压一个右边进栈，遇到右边就pop一个值，如果值和右边不同或者最后栈非空则证明false

解题代码


/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
    const array = []
    const parenthesesinfo = {
        '(':')',
        '{':'}',
        '[':']',
    }
    const parenteses = Object.keys(parenthesesinfo)
    const sArray = s.split('')
    for(let i = 0;i<sArray.length;i++){
        if(parenteses.includes(sArray[i])){
            array.push(parenthesesinfo[sArray[i]])
        } else{
            if(sArray[i] !== array.pop()){
                return false
            }
        }
    }
    return array.length === 0
};

1047. 删除字符串中的所有相邻重复项

学习链接

https://programmercarl.com/1047.删除字符串中的所有相邻重复项.html

个人想法

用一个array 存储，判断 s[i] 和 array尾部元素，相同pop 不同 push，最后循环导出array里面的内容

解题代码


/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicates = function(s) {
    const array = []
    const sArray = s.split('')
    let res = ''
    for(let i = 0; i<sArray.length;i++){
        if(array[array.length - 1]!== sArray[i]){
            array.push(sArray[i])
        } else{
            array.pop()
        }
    }   
    while(array.length){
        res =  array.pop() + res
    }
    return res
};

150. 逆波兰表达式求值

学习链接

https://programmercarl.com/0150.逆波兰表达式求值.html#算法公开课

个人想法

遇到数字就压入栈，遇到运算字符就从栈弹出两个运算再把结果压入栈。

解题代码


/**
 * @param {string[]} tokens
 * @return {number}
 */
var evalRPN = function(tokens) {
    let array = []
    let add = (a,b) => Number(a) + Number(b)
    let minus = (a,b) => a - b
    let multi = (a,b) => a * b
    let divided = (a,b) => a / b >0 ? Math.floor(a/b) : Math.ceil(a/b)
    let arithmetic = {
        '+': add,
        '-': minus,
        '*': multi,
        '/': divided,
    }
    let arithmeticArray = Object.keys(arithmetic)
    for(let i = 0;i < tokens.length;i++){
        if(arithmeticArray.includes(tokens[i])){
            let b = array.pop()
            let a = array.pop()
            array.push(arithmetic[tokens[i]](a,b))
        } else{
            array.push(tokens[i])
        }
    }
    return array.pop()
};