This is the seventh day of my participation in the August More text Challenge. For details, see: August More Text Challenge
The stack
The stack is a special linear table, can only be operated at the top of the stack, has the first in first out, last in first out characteristics
implementation
class Stack {
#stackArr = [] // Private property
constructor() {
// It is not recommended to define stackArr directly here, because stackArr can only be operated by exposed methods, not by instances that can directly operate stackArr
// this.stackArr = []
}
// Push adds an element to the top of the stack
push(item) {
this.stackArr.push(item)
}
// pop pops the top element of the stack
pop() {
return this.stackArr.pop()
}
// top returns the top element on the stack
top() {
return this.stackArr[this.stackArr.length - 1]}// isEmpty determines whether the stack isEmpty
isEmpty() {
return this.stackArr.length === 0
}
// size returns the number of elements in the stack
size() {
return this.stackArr.length
}
// clear Clear stack reset
clear() {
this.stackArr = []
}
}
Copy the codeThe stack implementation is actually an array based wrapper. Why encapsulate another layer of stack implementation when you already have arrays?
- Array provides a lot of operation mode, can be very convenient for data for any operation, it is not controllable, based on a layer of stack data encapsulation structure, can very good limit for any operation of the data, can only follow the stack handling characteristics (advanced after out, last in, first out), for the actual business development provides a way of thinking
- Wrapping stacks based on arrays is to hide implementation details, and when we encounter business and development problems, it is much easier to think on the shoulders of the stack, rather than using arrays as a plug
application
Judge parenthesis
let str1 = 'a(daj(fl(ks)aj)fl)kas' / / legal
let str2 = 'as(dj(flkajs)d(fsaj)fs)' / / legal
let str3 = 'as(dfl)ka(sf)j(skd)f)' // Illegal, lack of
let str4 = 'asd(kl)alk)s(df' // Not in the right order
Copy the codeTrain of thought
Loop strings, doing different operations for different types of strings
Open parenthesis – push
Close parenthesis encountered – determine whether the stack is empty, if it is empty, there is no corresponding open parenthesis, illegal, the stack is not empty, cancel a pair of parentheses
Other types – Skip
When the traversal is complete, it is legal if the stack is empty, otherwise it is illegal
const STR1 = 'a(daj(fl(ks)aj)fl)kas' / / legal
const STR2 = 'as(dj(flkajs)d(fsaj)fs)' / / legal
const STR3 = 'as(dfl)ka(sf)j(skd)f)' // Illegal, lack of
const STR4 = 'asd(kl)alk)s(df' // Not in the right order
/** * Check whether the parentheses in the string are valid */
const isLegalBracket = str= > {
if (Object.prototype.toString.call(str) ! = ="[object String]") {
// throw new Error('str is must string');
return false;
}
const STACK = new Stack()
for (let i = 0; i < str.length; i++) {
const ELE = str[i]
if (ELE === '(') { / / pressure stack
STACK.push(ELE)
}else if(ELE === ') ') {
if (STACK.isEmpty()) { // If the stack is empty, there is no corresponding open parenthesis
return false
} else { / / flare stack
STACK.pop()
}
}
}
return STACK.isEmpty()
}
console.log(isLegalBracket(STR1)) // true
console.log(isLegalBracket(STR2)) // true
console.log(isLegalBracket(STR3)) // false
console.log(isLegalBracket(STR4)) // false
Copy the codeCalculate the inverse Polish expression
use
The inverse Polish expression is a very useful expression that converts complex expressions into expressions that can be computed by simple operations. For example, (A +b)(C +d) converts to AB + CD +
advantage
The advantage is that you can perform any normal expression in just two simple operations, push and pull. Its operation mode is as follows:
If the current character is a variable or a number, the stack is pressed. If it is an operator, the top two elements are popped for the corresponding operation, and the result is pushed back into the stack. Finally, when the expression is scanned, the result is on the stack.
Reference table
| Normal expressions (infix expressions) | Inverse Polish expression (postfix expression) |
|---|---|
| a + b | [a, b, +] |
| a + (b – c) | [a, b, c, -, +] |
| a + (b – c) * d | [a, b, c, -, *, +] |
| a * (b + c) + d | [a, b, c, +, *, d, +] |
Computing [‘ 1 ‘, ‘2’, ‘3’, ‘+’, ‘*’, ‘4’, ‘+’] is equivalent to computing 1 * 2 + 3 + 4
答 案 :
I’m going to go through the array, and when I encounter a non-operator, I’m going to push the data, and when I encounter a budget, I’m going to bounce it from the stack twice in a row and then combine it with the operator, and I’m going to push the result, and when I’m done, there’s only one data left in the stack, and that’s the result
const ARR = ['1'.'2'.'3'.'+'.The '*'.'4'.'+']
const reversePolishNotation = arr= > {
// Error tolerant processing
if(!Array.isArray(arr)) {
throw new Error('arguments is must array');
}
const STACK = new Stack()
const OPERATORS = ['+'.The '-'.The '*'.'/'.' ']
for (let i = 0; i < arr.length; i++) {
const ELE = arr[i]
if(OPERATORS.includes(ELE)){ / / operators
// 1. Flick the stack twice in a row
const A = STACK.pop()
const B = STACK.pop()
// 2. Concatenate the data with the operator
const STR = B + ELE + A
// 3. Perform the operation and press the result
const RES = parseInt(eval(STR)).toString()
STACK.push(RES)
}else { // The non-operator pushes the stack directly
STACK.push(ELE)
}
}
return STACK.top()
}
console.log(reversePolishNotation(ARR)); / / 9
Copy the codeThe queue
A queue is a special type of linear table, which allows deleting elements from the head of the queue and adding new elements to the end of the queue. It is first-in, first-out and last-in, last-out
implementation
class Queue {
constructor() {
this.queue = []
}
// Add elements to the end of the queue
enqueue(queue) {
this.queue.push(queue)
}
// The queue header removes the element
dequeue() {
return this.queue.shift()
}
// View the queue header element without operating the queue
header() {
return this.queue[0]}// View the elements at the end of the queue
tail() {
return this.queue[this.queue.length - 1]}// Return the queue size
size() {
return this.queue.length
}
// Clear the queue
clear() {
this.queue.length = []
}
// Whether the queue is empty
isEmpty() {
return this.queue.length === 0}}Copy the codeapplication
Joseph ring
There is an array containing numbers from 0 to 99. Delete a number every two numbers. At the end of the loop, continue to the beginning of the loop to find the last number to delete
If 0 to 4
[0,1,3,4] is left after the deletion of the first round, and the round ends. At this point, the number of hours to the end is 2, and the start of the next round is 3
After the deletion of the second round, [1,3] is left, and the round ends. At this point, the number of hours to the end is 3, and the last digit 4 is deleted, and the beginning of the next round is 0
In the third round, the number of hours to the end of the round is 2. In the next round, the number of hours is 3, but the data itself remains the same
After the fourth round of deletion [3], only the last digit is left, which is the last digit to be deleted
Recursive thought:
/** * [Joseph ring problem] *@param {Number} Count [accumulator] *@param {[type]} Arr [array] *@return {[type]} [Returns the last deleted value] */
const josephus2 = (count = 0, arr) = > {
if(arr.length === 1) { // The end condition of recursion, when only 1 is left, it is the last number to delete
return arr[0]}// Use recursion
for (var i = 0; i < arr.length; i++) {
count += 1
if(count % 3= = =0) {
arr.splice(i, 1)
i -= 1 // After each delete, you must reset the value of I, otherwise arr itself is modified, resulting in a change in arr.length}}return josephus2(count, arr)
}
console.log(josephus2(0, ARR))
Copy the codeQueue idea:
/** * generate a sequence array *@param {[type]} Start [start, including start] *@param {[type]} End [End, not included] *@return {[type]} [Generated ascending array] */
const GENERATOR_NUMS = (start, end) = > {
let RES = []
for (let i = start; i < end; i++) {
RES.push(i)
}
return RES
}
const ARR = GENERATOR_NUMS(0.100)
/** * Joseph ring problem *@param {[type]} Array arr *@return {[type]} Returns the last deleted value */
const josephus = arr= > {
const QUEUE = new Queue()
// 1. Add the data of array arr to the queue
arr.forEach(num= > QUEUE.enqueue(num))
// 2. Define a variable to control the deletion of data
let index = 0
I % 3 === 0; I % 3 === 0
while(QUEUE.size() ! = =1) {
const ITEM = QUEUE.dequeue()
index += 1
if(index % 3! =0) {// Not satisfied to add to the end of the queue
QUEUE.enqueue(ITEM)
}
}
return QUEUE.header()
}
console.log(josephus(ARR))
Copy the code