xlearns / algoristic

算法learn

Orientation 🎯

Analysis 👇

algoristic's Issues

双栈算术表达式求值

function calc(input) {
if(typeof input!='string') console.warn('请输入字符串')
input = input.split(' ').reverse();
var len = input.length;
var optStack = [];
var valStack = [];
while(len--) {
var item = input[len];
switch(item) {
case "+":
case "-":
case "*":
case "/":
optStack.push(item);
break;
case "(":
break;
case ")":
var a = valStack.pop();
var b = valStack.pop();
var opt = optStack.pop();
valStack.push(eval(a + opt + b));
break;
default:
valStack.push(item);
}
}
return valStack.pop();
}

console.log(calc('( 1 + ( 5 * 2 ) )' ))

stack实现

//object版本
function Stack(){
  //stark
  this.arr = {}
  //指针
  this.pointer = 0
}
Stack.prototype = {
  push:function(item){
    return this.arr[++this.pointer] = item
  },
  pop:function(){
      let res = this.arr[this.pointer]
      delete this.arr[this.pointer]
      --this.pointer
      return res
  },
  peek:function(){
    return this.arr[this.pointer]
  },
  size:function(){
    return Object.keys(this.arr).length
  },
  clear:function(){
    this.pointer = 0
    this.arr = {}
    return this.arr
  }
}

//测试
// var stack = new Stack()
// stack.push(1)
// console.log(stack.push(1))
// stack.push(1)
// stack.push(2)
// stack.push(3)
// console.log(stack.peek(),stack.size())
// console.log(stack.pop())
// console.log(stack.peek(),stack.size())

//Array版本
function Stack_arr(){
  //stark
  this.arr = []
}
Stack_arr.prototype = {
  push:function(item){
    return this.arr.push(item)
  },
  pop:function(){
      return this.arr.pop()
  },
  peek:function(){
    return this.arr[this.arr.length-1]
  },
  size:function(){
    return this.arr.length
  },
  clear:function(){
    this.arr = []
    return this.arr
  }
}
//测试
// var stack = new Stack_arr()
// stack.push(1)
// console.log(stack.push(1))
// stack.push(1)
// stack.push(2)
// stack.push(3)
// console.log(stack.peek(),stack.size())
// console.log(stack.pop())
// console.log(stack.peek(),stack.size())

链表

//singlelink 单链表
class Node{
  constructor(ele){
    this.element = ele
    this.next = null
    this.pre = null
  }
}
class Link {
  constructor(){
    this.head =  new Node('head')
    this.cur = this.head
    this.pointer = 1
  }

  find(ele){
    let cur = this.head;
    while(cur.element !==ele){
      cur = cur.next
    }
    return cur
  }

  findPre(ele){
    let cur = this.head;
    while(cur.element !== null && cur.next.element !==ele){
      cur = cur.next
    }
    return cur
  }
  
  insert(ele,item){
    const newNode = new Node(ele)
    let cur = this.find(item)
    newNode.next = cur.next
    cur.next = newNode
    this.pointer++;
  }
  advance(n){
    if (n <= 0||n>=this.size()) {
      console.warn('n值范围不对')
      return
    }
    let index = 0;
    while (index < n && this.cur.next != null) {
      this.cur = this.cur.next;
      index++;
    }
  }

  remove(ele){
    let pre = this.findPre(ele)
    while (pre.next != null) {
      pre.next = pre.next.next;
      this.pointer--;
    }
  }
  isEmpty(){
    return this.pointer ==0
  }
  size(){
    return this.pointer
  }
  show(){
    return this.cur.element
  }
}
const link = new Link();
link.insert('aaa', 'head');
link.insert('bbb', 'aaa');
link.advance(2);
console.log(link.show());
console.log(link.size())

//doublelink 双向链表