前端学数据结构与算法（二）：数组的操作特性与栈的应用

function test(arr) {
	let len = arr.length
    for (let i = 0; i < len; i++) {
    	arr.shift()
    }
}

const arr = ['a', 'b']

arr[10000000000] = 'c'

const arr = [1, 2, 3, 4];

arr.unshift(0)

function test(arr) {
	let len = arr.length
    for (let i = 0; i < len; i++) {
    	arr.shift() // 每一次操作都需要整体搬家
    }
}

class Stack {
  constructor() {
    this._data = []
  }
  push(e) {
    this._data.push(e)
  }
  pop() {
    return this._data.pop()
  }
  size() {
  	return this._data.length
  }
}

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
示例：
  "()[]{}"  // true
  "([)]"    // false
  "{[]}"  // true

var isValid = function (s) {
    const leftBrackets = '([{'
    const brackets = {
        ')': '(',
        ']': '[',
        '}': '{'
    }
    const stack = new Stack()
    for (const c of s) {
        if (leftBrackets.indexOf(c) > -1) {
            stack.push(c) // 左括号就入栈
        } else {
            const d = stack.pop() // 弹出栈顶元素
            if (d !== brackets[c]) { // 是否匹配
                return false
            }
        }
    }
    return stack.size() === 0 // 是否为空
};

以Unix风格给出一个文件的绝对路径，将其转换为规范路径。
一个点(.)表示当前目录本身；
此外，两个点(..)表示将目录切换到上一级(指向父目录)；
两者都可以是复杂相对路径的组成部分。
请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。
最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
示例：
  输入："/a/./b/../../c/"
  输出："/c"
  
  输入："/a/../../b/../c//.//"
  输出："/c"
  
  输入："/a//b////c/d//././/.."
  输出："/a/b/c"

var simplifyPath = function (path) {
    const stack = new Stack() // 添加join方法
    const pathArr = path.split('/')
    for (const s of pathArr) {
        if (s === '' || s === '.') {
            continue;
        } else if (s === '..') {
            stack.pop()
        } else {
            stack.push(s)
        }
    }
    return '/' + stack.join('/')
};

有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式，求表达式的值。
示例：
  输入: ["4", "13", "5", "/", "+"]
  输出: 6
  解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
  
  输入: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
  输出: 22
  解释: 
  该算式转化为常见的中缀算术表达式为：
    ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
  = ((10 * (6 / (12 * -11))) + 17) + 5
  = ((10 * (6 / -132)) + 17) + 5
  = ((10 * 0) + 17) + 5
  = (0 + 17) + 5
  = 17 + 5
  = 22

const SIGN = {
  '*': (a, b) => a * b,
  '/': (a, b) => a / b | 0, // 向下取整
  '+': (a, b) => a + b,
  '-': (a, b) => a - b
}

var evalRPN = function(tokens) {
  const stack = new Stack()
  tokens.forEach(item => {
    if (item in SIGN) { // 是运算符
      const b = stack.pop()
      const a = stack.pop() // 弹出两个
      const res = SIGN[item](a, b)
      stack.push(res) // 结果再压入栈
    } else {
      stack.push(+item) // 是数字直接压入栈
    }
  })
  return stack.pop()
};

计算字符串表达式的值：
"3+8*5-6/3"           // 41
"1+2*2-6+8/2*3-4"     // 7

提示：
  使用两个栈