Kiner algorithm: Recursion and stack (solve the expression evaluation problem)

Series article guide

Kiner algorithm brush topic (a) : linked list and linked list ideas
Kiner algorithm: Recursion and stack (solve the expression evaluation problem)
Kiner algorithm brush topic (3) : thread pool and task queue
Do you really know binary trees?
Do you really know binary trees?
Kiner algorithm: Heap and Priority queue
Kiner algorithm brush topic (five) : Heap (priority queue)

The open source project

All articles in this series will be collected and managed in GitHub. Welcome ISSUE and Star.

GitHub portal: Kiner algorithm

thinking

There’s one thing we can do+ 1, it can also beInto the stackIt’s just a matter of way of thinking. It’s essentially the same thing
Similarly, to accomplish something, we can- 1, it can also beOut of the stack
(() ())So we can actually think of the outer pair of parentheses as representing oneLarge taskBut there is a precondition for us to complete this big task, and that is to complete the two smaller tasks inside, the two pairs of brackets in the middle. Therefore, the thinking of parenthesis pairing is not only used for parsing strings or HTML code, but also can be generalized to the following scenarios:
- A pair of(a)You can view it as a whole event, and(() ())You can view it as havingCompletely containsRelationship of task execution details.
- Function execution, such as:(() ())We can think of the outermost parentheses as a big functionFn0And in this big functionFn0There is a call inFn1andFn2When MY two subfunctions are done, ourFn0It’s done.
- Binary treetheDepth-first traversalAs a result, namely,DFS.(() ())You can think of it as a root node with two children

From the above, we have come up with a data structure suitable for dealing with these full inclusion problems, which is our hero stack for today

Typical stack application scenarios

Operating system thread stack (thread space)
- When we apply for a new thread space, the default size of the thread stack on the Mac is 8192KB, or about 8M.
```
# MAC to check the default size of the thread stack
ulimit -a
Copy the code
```
- When our function calls are too deep and we push too many variables into the thread stack beyond 8192KB, a stack burst occurs
Evaluate the expression 3 + 5(e.g., evaluate the inverse Polish expression)
- Consider: Is there any difference between evaluating an expression recursively and evaluating an expression on a stack
  - Answer: No, recursion is essentially usedsystemGive us the stack of variables.
- Solution: 3 + 5 is regarded as a binary tree with + as the root node, 3 as the left subtree and 5 as the right subtree, namely, we often say: expression tree.
- The concept of an expression tree: Operators are usually used as root nodes and computed factors are used as attribute structures of the subtrees
- For example: 3 * (4 + 5), which is essentially a multiplication expression, the following addition is essentially a subproblem to be solved before we evaluate the multiplication expression, so we can logically convert the above formula into the following binary tree:
```
[*] [3] [+] [4] [5]Copy the code
```

Brush the topic

LeetCode 682: Baseball game

Their thinking

This problem is the stack comparison of the basic problem, the main use of the idea of divide and conquer and stack characteristics. The general idea is to loop over our list of points:

Push numbers onto the stack as they are encountered.
When the meet +, the need to put the two recent scores, then we can the next element in the stack stack elements out together (note that due to the nature of the stack, we can only get elements from the stack, so to get the top of the stack the next element, we need to pop up the stack, then, the last element in the stack to pressure into the stack, And press the sum of the two elements).
If we hit D, we need to multiply the most recent integral by 2, and then push the result onto the stack.
If C is encountered, indicating that the previous score is invalid, we need to pop the top element of the stack
When the loop ends, our stack stores our entire score, we just need to pop the stack elements one by one, and add up to get the answer we want.

Code demo

/* * @lc app=leetcode.cn id=682 lang=typescript * * [682] baseball game */

// @lc code=start
function calPoints(ops: string[]) :number {
    // Use an array stack to store score data
    const stack: number[] = [];
    // Use the idea of divide and conquer, treating different situations in different ways
    for(const op of ops) {
        switch(op) {
            case "+":
                // When a plus sign is encountered, the top two results are added and pushed onto the stack
                // Pop the top element first, otherwise you can't get the next element from the top element
                const a = stack.pop();
                // Get the current top element of the stack
                const b = stack[stack.length-1];
                // Push the top element back on the stack, and push the result of a+b back on the stack
                stack.push(a, a+b);
                break;
            case "D": 
                // When D is encountered, it is necessary to double the top element of the stack before pushing it onto the stack
                const top = stack[stack.length-1];
                stack.push(top*2);
                break;
            case "C": 
                // If C is encountered, the last score is invalid and the top element is popped
                stack.pop();
                break;
            default: 
                // If it is not one of the above, it is a score, and the score is pushed onto the stack
                stack.push(parseInt(op)); }}// At the end of the loop, all you need to do is pop up the stack and add up the total score
    let num = 0;
    while(stack.length! = =0) {
        num += stack.pop();
    }
    return num;
};
// @lc code=end


Copy the code

LeetCode 844: Compares strings containing backspace

Their thinking

This problem is a typical stack logic problem, we only need to be in addition to the empty string and # of other pressing string into the stack, meet with # #, we’ll elements pop up the stack, so you can get a final string, in the end, we only need to compare two original string through the final string is equal to that of can

Code demo

/* * @lc app=leetcode.cn id=844 lang=typescript * * [844] Compares backspace strings */

// @lc code=start
function toRealString(s: string) :string {
    // The stack used to store the result characters
    const stack = [];
    for(const char of s) {
        // Skip an empty string
        if(char === "") continue;
        // The top element of the stack is ejected when # is encountered
        else if(char === "#") stack.pop();
        // Otherwise it is our real character, which is pushed directly onto the stack
        else stack.push(char);
    }
    // Convert the stack directly to a string for subsequent comparison
    return stack.toString();
}

function backspaceCompare(S: string, T: string) :boolean {
    return toRealString(S) === toRealString(T);
};
// @lc code=end
Copy the code

LeetCode 1021: Remove the outermost parentheses

Their thinking

This is a pretty good stack thinking problem. Why stack thinking? Because when we actually implement, we don’t use the data structure of the stack, but we use the stack mentality, that is, advance after exit, last in, first out. If you go back to the beginning of this article and look at what we’re thinking, we can use +1 to represent the push, -1 to represent the push, and when our counter is 0, it means the stack is empty. So, with this idea as a base, let’s look at the detailed idea of how to solve the problem. This problem is written directly into the code comments, so that it is easier to understand.

Code demo

/* * @lc app=leetcode.cn id=1021 lang=typescript * * [1021] Remove the outermost parentheses */

// @lc code=start
function removeOuterParentheses(S: string) :string {
    // We don't use the stack data structure, but we use the stack header pointer idea
    
    let res = "";
    // where j represents the starting position of the first outermost parenthesis, count is the difference between the opening and closing parentheses
    // When count is 0, we have matched the opening and closing brackets
    for(let i=0,j=0,count=0; i<S.length; i++) {// When an open parenthesis is encountered, count is incremented by 1
        if(S[i] === '(') ++count;
        // The closing parentheses subtract count by one, and the parentheses cancel out
        else --count;
        // If the left and right parentheses do not cancel, the next loop continues
        if(count ! = =0) continue;
        // If the parentheses cancel out, we need to cancel the outermost parentheses of the currently found parentheses sequence
        / / such as: (1) () () () ()
        // We can split the above parenthesis sequence into two parts
        / / () () () and (())
        // When we first encounter left and right parenthesis cancellation, that is, when count is 0
        // We have already found a subsequence to be processed
        // We just need to remove the outermost parentheses of (()())
        // We know that the current I has reached the last position of the above subsequence, which is the position of the outermost close parenthesis
        // J is the outermost open parenthesis we record, so we want to intercept the start and end of the parenthesis:

        // Notice that the second argument to substr is the length of the string,
        // I -j+1 is the length of the original subsequence. Since I and j are both subscripts, to convert to length, you add 1),
        // Because we want to remove a pair of parentheses, we subtract 2
        // substr(j+1, i - j + 1 - 2)
        // substr(j+1, i - j -1)
        res += S.substr(j+1, i - j - 1);
        // After intercepting and splicing, move the starting position to the next bit of the last bit of the current subsequence to continue the next round of processing
        j = i + 1;
    }
    return res;
};
// @lc code=end


Copy the code

LeetCode 636: Exclusive time for a function

Their thinking

This problem actually has two main points, as long as these two points to solve, then this problem is easy.

How to effectively determine the start and end of a function edit

To define the start and end of a function, it is easy to simply slice the string to see if the current state is start or end. However, it is important to note that we need to maintain an array to simulate stack manipulation, and the index of the array is actually the id of the function
When the function starts, does the time from the last function to the current position go to the previous function or does it go to the current function, when the function ends?

We can draw a simple diagram to illustrate this:
```
# start0 and end0 represent the beginning and end of function 1, respectively. Start1 and end1 represent the beginning and end of function 2, respectively|___________________|___________________|___________________| start0 start1 end1 end0 | ___________________ | | -- -- -- -- -- -- -- -- -- | | -- -- -- -- -- -- -- -- -- | time1 time2 time3Copy the code
```
From the above figure, we can see that the distance from start0 to start1 should be the independent running time of function 1, so when we get to start1, we should calculate the time to function 1, i.e., we need to add time1 to fnTime1, i.e. FnTime1 += time1, when we get to end1, it is obvious that our time2 should be the execution time of function 2, namely fnTime2 += time2, and finally we reach end0, obviously the time from end1 to end0 is also the exclusive time of function 1. FnTime1 = time3.

Code demo

/* * @lc app=leetcode.cn id=636 lang=typescript * * [636] exclusive time for functions */

// @lc code=start
function exclusiveTime(n: number, logs: string[]) :number[] {
    // The stack is used to simulate the execution of the function.
    // The execution time of the last function should be added to the execution time of the last function.
    // Our time is the execution time added to the current function

    // Initializes a result array with the number of functions in length and initializes it with 0 as the initial value for each item
    const res: number[] = new Array<number>(n);
    res.fill(0);
    // Maintain a stack for storing the id of the function
    const stack: number[] = [];

    // Pre Records the time of the last operation
    for(let i=0,pre=0; i<logs.length; i++) {// Convert id, status, and time into integers
        const [sid, status, stime] = logs[i].split(':');
        const last = stack.length - 1;
        let id = parseInt(sid);
        let time = parseInt(stime);
        console.log(id, status, time);

        // Lines 28 to 33 are an optimization for lines 36 to 55, essentially the same, but the code is cleaner, though harder to understand
        let offset = (status === 'end'? 1 : 0);// When the end state is encountered, the calculation time needs to be added by 1
        if(stack.length! = =0) res[stack[last]] += time - pre + offset;
        pre = time + offset;

        (status === 'start')? stack.push(id) : stack.pop();// If it is in the start state
        // if(status === 'start') {
        // // When the stack is not empty, we need to add the current time to the top element of the stack to meet a time difference as soon as the task starts
        // // state, which indicates that the execution of the previous function is suspended and the time is suspended, so the current timestamp minus the previous time is
        // // A period of time when our last function was run independently
        // if(stack.length! = = 0) {
        // res[stack[last]] += time - pre;
        / /}
        // // Assigns the current time to the previous time for the next round
        // pre = time;
        // // whenever the start state is encountered, the id of the current function is pushed onto the stack
        // stack.push(id)
        // } else {
        // // When the end state is encountered, we need to calculate the execution time of the current function, just take the current time minus the start time of the function execution plus 1
        // res[id] += time - pre + 1;
        // // Previous time corrected to current time + 1
        // pre = time + 1;
        // // The top element is off the stack because it encountered an end state, and the current function has finished processing
        // stack.pop();
        // }
    }

    return res;
};
// @lc code=end


Copy the code

LeetCode 20: Valid parentheses

Their thinking

In this case, we also need to push our open parenthesis onto the stack. When we encounter the parenthesis, pop up the top element of the stack and compare whether the current close parenthesis matches the open parenthesis. If it matches, it is valid, otherwise it is invalid.

PS: The following two solutions are essentially the same, but the second general solution is to use the counter to achieve, the purpose is to let people not too limited to the stack of data structure, but to divergent thinking, learn the stack of thinking rather than the structure of the stack. This is the same kind of linked list thinking THAT I did in my previous series of articles on two lists, and you can take a look at it if you’re interested. Kiner algorithm brush topic (a) : linked list and linked list ideas

Code demo

Solution a:

/ * * *@param {string} s
 * @return {boolean}* /
var isValid = function(s) {

    if(s.length===0) {return true;
    }
    
    let left = "([{";
    let right = ")]}";

    let stack = new Stack();
    for(let i=0; i<s.length; i++){let char = s[i];
        if(left.indexOf(char)>=0){
            stack.push(char);
        }else if(right.indexOf(char)>=0&&left.indexOf(stack.head())===right.indexOf(char)){
            stack.pop();
        }else{
            return false; }}return stack.empty();
};
function Stack(){
    let arr = [];
    this.push = function(val){
        arr.push(val);
    }
    this.pop = function(){
        return arr.pop();
    }
    this.tail = function(){
        return arr[0];
    }
    this.head = function(){
        return arr[arr.length-1]}this.size = function(){
        return arr.length;
    }
    this.empty = function(){
        return this.size()===0; }}Copy the code

Scheme 2:

/* * @lc app=leetcode.cn id=20 lang=typescript * * [20] Valid parentheses */

// @lc code=start
function isValid(s: string) :boolean {
    // Define as many counters as there are parentheses
    let count1 = 0, count2 = 0, count3 = 0;
    // Open parenthesis set and close parenthesis set respectively, so that the number of parentheses is valid, but the nesting level of parentheses is illegal
    let subStrLeft = '({[';
    let subStrRight = ')}] ';
    // It is used to store the index corresponding to the parenthesis type. If it is {, then its index in the open parenthesis set should be 1. When we find the next close parenthesis,
    // See if the index of the next close parenthesis in the close parenthesis set is also 1
    let idxStack = [];
    for(let i=0; i<s.length; i++) {// Gets the index of the current character in the left parenthesis collection
        let lIdx = subStrLeft.indexOf(s[i]);
        // Gets the index of the current character in the close parenthesis collection
        let rIdx = subStrRight.indexOf(s[i]);
        // If the current character is found in the set of open parentheses, the current character is one of the left parentheses, and the index of the left parentheses is pushed onto the stack
        if(lIdx! = = -1) idxStack.push(lIdx);
        // If the current character is found in the set of close parentheses, it indicates that the current character is one of the close parentheses
        // The index of the left parenthesis is displayed, and the index of the right parenthesis is matched with the index of the current right parenthesis
        if(rIdx! = = -1&& rIdx! ==idxStack.pop())return false;
        // Open parentheses are also encountered, adding up the number of open parentheses of different types
        if(lIdx === 0) ++count1;
        else if (lIdx === 1) ++count2;
        else if (lIdx === 2) ++count3;
        // When close parentheses are encountered, the number of close parentheses is accumulated separately
        if(rIdx === 0) --count1;
        else if (rIdx === 1) --count2;
        else if(rIdx === 2) --count3;
        // Each turn of the loop should determine if there are more close parentheses than left parentheses, i.e., if the counter is less than 0,
        // Because of a legal parenthesis sequence, the number of left parentheses is always greater than or equal to the number of right parentheses during traversal
        if(count1<0 || count2<0 || count3<0) return false;
    }

    // At the end of the loop, it is valid as long as all counters are 0, that is, all the left and right parentheses are cancelled out, otherwise it is invalid
    return count1===0&&count2===0&&count3===0;
};
// @lc code=end


Copy the code

Kiner algorithm: Recursion and stack (solve the expression evaluation problem)

Series article guide

The open source project

thinking

Typical stack application scenarios

Brush the topic

LeetCode 682: Baseball game

Their thinking

Code demo

LeetCode 844: Compares strings containing backspace

Their thinking

Code demo

LeetCode 1021: Remove the outermost parentheses

Their thinking

Code demo

LeetCode 636: Exclusive time for a function

Their thinking

Code demo

LeetCode 20: Valid parentheses

Their thinking

Code demo

Related Posts

88. Merge two ordered arrays (easy)

Agora Silver: Machine learning-based speech codec sound net: Support for high tone quality speech interaction at ultra-low bit rates

Come, work with me to develop your own multiterminal error monitoring platform (full version)