概念

栈是一个线性结构，在计算机中是一个相当常见的数据结构。

栈的特点是只能在某一端添加或删除数据，遵循先进后出的原则

实现

class Stack {
  constructor() {
    this.stack = []
  }
  push(item) {
    this.stack.push(item)
  }
  pop() {
    this.stack.pop()
  }
  peek() {
    return this.stack[this.getCount() - 1]
  }
  getCount() {
    return this.stack.length
  }
  isEmpty() {
    return this.getCount() === 0
  }
}

应用

1. 通中缀计算器

class Stack {
  constructor() {
    this.stack = []
  }
  push(item) {
    this.stack.push(item)
  }
  pop() {
    return this.stack.pop()
  }
  peek() {
    return this.stack[this.getCount() - 1]
  }
  getCount() {
    return this.stack.length
  }
  isEmpty() {
    return this.getCount() === 0
  }
}
function priority(oper) {
  if (oper == '*' || oper == '/') {
    return 1
  } else if (oper == '+' || oper == '-') {
    return 0
  } else {
    return -1
  }
}
function isOper(val) {
  let oper = ['+', '-', '*', '/']
  return oper.includes(val)
}
function cal(num1, num2, oper) {
  let result = 0
  switch (oper) {
    case '+':
      result = num1 + num2
      break;
    case '-':
      result = num1 - num2
      break;
    case '*':
      result = num1 * num2
      break;
    case '/':
      result = num1 / num2
      break;
    default:
      throw new Error('出错')
  }
  return result
}
let expression = '7*2'
let numStack = new Stack()
let operStack = new Stack()
let index = 0
let num1 = 0;
let num2 = 0;
let result = 0
let oper = ''
let ch = '';
while (true) {
  ch = expression[index]
  if (isOper(ch)) {
    if (!operStack.isEmpty()) {
      let pre = operStack.peek()
      if (priority(pre) >= priority(ch)) {
        num1 = numStack.pop()
        num2 = numStack.pop()
        oper = operStack.pop()
        result = cal(num2, num1, oper)
        numStack.push(result)
        operStack.push(ch)
      }
      else {
        operStack.push(ch)
      }
    } else {
      operStack.push(ch)
    }
  } else {
    let num = ch
    let temIndex = index + 1
    while (!isOper(expression[temIndex])) {
      if (temIndex >= expression.length) {
        break
      }
      num = num + expression[temIndex]
      temIndex++
    }
    index = temIndex - 1
    numStack.push(+num)
  }
  index++
  if (index >= expression.length) {
    break
  }
}
while (true) {
  if (operStack.isEmpty()) {
    break
  }
  num1 = numStack.pop()
  num2 = numStack.pop()
  oper = operStack.pop()
  result = cal(num2, num1, oper)
  numStack.push(result)
}
console.log(numStack.pop());

2. 中缀转后缀计算器(逆波兰计算器)

class Stack {
  constructor() {
    this.stack = []
  }
  push(item) {
    this.stack.push(item)
  }
  pop() {
    return this.stack.pop()
  }
  peek() {
    return this.stack[this.getCount() - 1]
  }
  getCount() {
    return this.stack.length
  }
  isEmpty() {
    return this.getCount() === 0
  }
}
function cal(num1, num2, oper) {
  let result = 0
  switch (oper) {
    case '+':
      result = num1 + num2
      break;
    case '-':
      result = num1 - num2
      break;
    case '*':
      result = num1 * num2
      break;
    case '/':
      result = num1 / num2
      break;
    default:
      // console.log(oper);
      //break
      throw new Error('出错')
  }
  return result
}
function priority(oper) {
  if (oper == '*' || oper == '/') {
    return 1
  } else if (oper == '+' || oper == '-') {
    return 0
  } else {
    return -1
  }
}
function isOper(val) {
  let oper = ['+', '-', '*', '/', '(', ')']
  return oper.includes(val)
}
function toArr(str) {
  let index = 0
  let newArr = []
  while (index < str.length) {
    let c = str[index]
    if (isOper(c)) {
      newArr.push(c)
    } else {
      while (true) {
        if ((!isOper(str[index + 1])) && index + 1 < str.length) {
          if (str[index + 1] !== ' ') {
            c = c + str[index + 1]
            index++
          } else {
            index++
          }
        } else {
          break
        }
      }
      newArr.push(+c)
    }
    index++
  }
  return newArr
}
function change(str) {
  let newArr = toArr(str)
  console.log(newArr);
  //初始化两个栈：运算符栈s1和储存中间结果的栈s2(s2只进栈,最后还要逆序, 可用数组代替)；
  let s1 = new Stack()
  let s2 = []
  //从左至右扫描中缀表达式；
  newArr.forEach(item => {
    if (typeof item === 'number') {
      // 遇到操作数时，将其压s2；
      s2.push(item)
    } else if (item === '(') {
      //遇到括号时：如果是左括号“(”，则直接压入s1
      s1.push(item)
    } else if (item === ')') {
      //如果是右括号“)”，则依次弹出s1栈顶的运算符，并压入s2，直到遇到左括号为止，此时将这一对括号丢弃
      while (!(s1.peek() === '(')) {
        s2.push(s1.pop())
      }
      s1.pop()    //将“(”弹出s1栈,消除小括号
    } else {
      //遇到运算符时
      //当item的优先级<=s1栈顶运算符, 将s1栈顶的运算符弹出并压入到s2中，再次转到(4-1)与s1中新的栈顶运算符相比较；
      while (!s1.isEmpty() && priority(s1.peek()) >= priority(item)) {
        s2.push(s1.pop())
      }
      s1.push(item)
    }
  });
  while (!s1.isEmpty()) {
    s2.push(s1.pop())
  }
  return s2
}

let oldStr = '1 0. 1+((2+ 3 )*4)-5'
let newStr = change(oldStr)
console.log(newStr);

let stack = new Stack()
newStr.forEach(element => {
  if (!isOper(element)) {
    stack.push(element)
    console.log('push', element);
  } else {
    let num1 = stack.pop()
    console.log('pop', num1);
    let num2 = stack.pop()
    console.log('pop', num2);
    let result = cal(num2, num1, element)
    stack.push(result)
    console.log('push', result);
  }
});
console.log(stack.pop());