The stack

In last Out (last in first out)

  • Push adds an element to the top of the stack
  • Pop Pops the element at the top of the stack
  • Top returns the top element on the stack
  • IsEmpty checks whether it isEmpty
  • Size returns the number of elements in the stack
  • The clear empty stack

Implement a stack using an array of JS

function Stack() {
  const items = []

  // Add elements from the top of the stack
  this.push = function (item) {
    items.push(item)
  }

  / / the pop-up
  this.pop = function () {
    return !this.isEmpty() && items.pop()
  }

  // Return the top element of the stack
  this.top = function () {
    return !this.isEmpty() && items[items.length - 1]}// Check whether it is null
  this.isEmpty = function () {
    return items.length === 0
  }

  // Return the stack size
  this.size = function () {
    return items.length
  }

  / / empty stack
  this.clear = function () {
    items.length = 0}}Copy the code

Check whether the parentheses are valid

Train of thought

Iterate over the string, and when (is encountered, add a token to the stack to indicate that this is the beginning of the first pair of parentheses. When), we pull a token from the stack to indicate that the bracket is a group. If you can’t pop it, you’re missing it. Return false. At the end of the walk, we determine the stack length. If the stack is empty, all parentheses cancel out and return true. If the length is not 0, it is missing). Returns false.

implementation

const str1 = '(12) (323) (123) (1))'
const str2 = '() (123123).

function isLegal(str) {
  const items = new Stack()
  for (let i = 0; i < str.length; i++) {
    if (str[i] === '(') {
      items.push(1)}else if (str[i] === ') ') {
      if (items.isEmpty()) return false
      else items.pop()
    }
  }
  return items.isEmpty()
}

console.log(isLegal(str1), isLegal(str2))
Copy the code

Computes inverse Polish expressions (postfix operation)

Train of thought

Iterate over the array expression, adding all the numbers to the stack. When an operator is encountered, two numbers are taken from the stack and concatenated, evaluated using eval, and the result is pushed back on the stack. So we keep going through the loop and at the end of the loop, if the expression is correct we’re left with the last value, and we just take it off the stack and return it

implementation

/ / 4 + 13/5
const exp1 = ['4'.'13'.'5'.'/'.'+']
const exp2 = ['10'.'6'.'9'.'3'.'+'.'11'.The '*'.'/'.The '*'.'17'.'+'.'5'.'+']

function calcExp(exp) {
  const stack = new Stack()
  for (let i = 0; i < exp.length; i++) {
    const item = exp[i]
    if (['+'.The '-'.The '*'.'/'].indexOf(item) >= 0) {
      const value1 = stack.pop()
      const value2 = stack.pop()
      const expStr = value2 + item + value1
      stack.push(parseInt(eval(expStr)).toString())
    } else {
      stack.push(item)
    }
  }
  return stack.pop()
}

console.log(calcExp(exp1))
console.log(calcExp(exp2))
Copy the code

Implement a stack with min methods

Implement a stack that, in addition to the usual push, pop methods, provides a min method that returns the minimum value in the stack. The required time is O(1)

Train of thought

Define two stacks, one for normal storage of data and operations, hereinafter referred to as stacks. The other stores the minimum value of each stack, hereinafter referred to as min stack. Values are added to the stack as normal each time a push is made. If the min stack is empty or the value at the top of the min stack is larger than the value added, then we push it. The top of the min stack is the minimum value for this operation. Each pop, the stack and min stack normal operation. Min stack pops an element after the top of the stack. Because every time we push, we’re pushing the minimum value of that state into the min stack. The value at the top of the stack is still the smallest value in the stack.

implementation

function MinStack() {
  const stack = new Stack()
  const minStack = new Stack()

  this.push = function (item) {
    stack.push(item)
    if (minStack.isEmpty() || minStack.top() > item) {
      minStack.push(item)
    } else {
      minStack.push(minStack.top())
    }
  }
  this.pop = function () {
    if (stack.isEmpty()) return false
    stack.pop()
    minStack.pop()
  }
  this.min = function () {
    return minStack.top()
  }
}

const minStack = new MinStack()

minStack.push(3) / / [3]
console.log(minStack.min()) / / 3
minStack.push(2) / / (3, 2]
console.log(minStack.min()) / / 2
minStack.push(5) / /,2,5 [3]
console.log(minStack.min()) / / 2
minStack.push(-1) / / [3,2,5, 1]
console.log(minStack.min()) // -1
minStack.pop() / /,2,5 [3]
minStack.pop() / / (3, 2]
minStack.pop() / / [3]
console.log(minStack.min()) / / 3

/ / 3
/ / 2
/ / 2
// -1
/ / 3
Copy the code

Midorder expression goes to postfix expression

thought

Define a stack and a list array. Loop expression elements. If it is a number, add it directly to the list. If the parenthesis is left, the stack is pressed. If it is a close parenthesis, it loops through the stack element and pops the top of the stack into the list until an open parenthesis is encountered to end the loop. And pop open parenthesis. If it is the operator, it determines whether the stack is empty at that time. If the stack is empty, the operator is added directly to the empty stack. If it is not empty, loop through the stack, add the top operator to the list with a pop-up whose priority is greater than or equal to that of the current operator. Until a priority less than the current operator is found. Pushes the current operator onto the stack. At the end of the loop, the remaining elements in the stack, in turn, pop off the top of the stack and add to the list. And returns the list result.

implementation

const priorityMap = {
  '+': 1.The '-': 1.The '*': 2.'/': 2
}

function infixExpToPostfixExp(exp) {
  const stack = new Stack()
  
  const list = []
  for (let i = 0; i < exp.length; i++) {
    const item = exp[i]
    if (!isNaN(item)) {
      list.push(item)
    } else if (item === '(') {
      stack.push(item)
    } else if (item === ') ') {
      while(stack.top() ! = ='(') {
        list.push(stack.pop())
      }
      stack.pop()
    } else {
      while(! stack.isEmpty() && ['+'.The '-'.The '*'.'/'].indexOf(stack.top()) ! = = -1 && priorityMap[stack.top()] >= priorityMap[item]) {
        list.push(stack.pop())
      }
      stack.push(item)
    }
  }
  
  while(! stack.isEmpty()) { list.push(stack.pop()) }return list
}

const test1 = ['12'.'+'.'3'] / / 12 + 3
const test2 = ['2'.The '-'.'3'.'+'.'2'] / / 2-3 + 2
const test3 = ['('.'1'.'+'.'('.'4'.'+'.'5'.'+'.'3'.') '.The '-'.'3'.') '.'+'.'('.'9'.'+'.'8'.') '] / / (1 + 4 + 5 + 3) - 3) + (9 + 8)

console.log(infixExpToPostfixExp(test1))
console.log(infixExpToPostfixExp(test2))
console.log(infixExpToPostfixExp(test3))
Copy the code