Task03: stack

1. Video title

1.1 Valid parenthesis

1.1.1 describe

Given one only includes ‘(’,’)’,’{’,’}’,’[’,’]’ String s , Determines whether the string is valid .

Valid string needs to meet ：

Opening parentheses must be closed with closing parentheses of the same type .
The left parenthesis must be closed in the correct order .

Example 1：

Input ：s = “()”
Output ：true

Example 2：

Input ：s = “()[]{}”
Output ：true

Example 3：

Input ：s = “(]”
Output ：false

Example 4：

Input ：s = “([)]”
Output ：false

Example 5：

Input ：s = “{[]}”
Output ：true

Tips ：

1 <= s.length <= 104
s Brackets only ‘()[]{}’ form

1.1.2 Code

Sequential scanning , For the left bracket, press it directly onto the stack , For the right parenthesis, the stack top match is taken

Can stack if To determine whether it matches , You can also use a dictionary

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        pairs = {
    
                    ')':'(', 
                    '}':'{',
                    ']':'['
                }
        for i in s :
            if i=='(' or i =='[' or i =='{' :
                stack.append(i)
            else :
                if len(stack) != 0 and stack[-1] == pairs[i] :
                    stack.pop()
                else :
                    return False
        if len(stack) == 0:
            return True
        else :
            return False

1.1.3 summary

Dictionaries are easy to match , It also simplifies the code

1.2 Evaluate the inverse Polish expression

1.2.1 describe

according to Reverse Polish notation , Find the value of the expression .

Valid operators include +、-、*、/ . Each operand can be an integer , It can also be another inverse Polish expression .

Be careful The division between two integers retains only the integer part .

It can be guaranteed that the given inverse Polish expression is always valid . let me put it another way , The expression always yields a valid number and does not have a divisor of 0 The situation of .

Example 1：

Input ：tokens = [“2”,“1”,"+",“3”,"*"]
Output ：9
explain ： This formula is transformed into a common infix arithmetic expression as ：((2 + 1) * 3) = 9

Example 2：

Input ：tokens = [“4”,“13”,“5”,"/","+"]
Output ：6
explain ： This formula is transformed into a common infix arithmetic expression as ：(4 + (13 / 5)) = 6

Example 3：

Input ：tokens = [“10”,“6”,“9”,“3”,"+","-11","","/","",“17”,"+",“5”,"+"]
Output ：22
explain ： This formula is transformed into a common infix arithmetic expression as ：
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

Tips ：

1 <= tokens.length <= 104
tokens[i] It's an operator （"+"、"-"、"*" or “/”）, Or in the range [-200, 200] An integer in

Reverse Polish notation ：

The inverse Polish expression is a suffix expression , The so-called suffix means that the operator is written after .

The usual formula is a infix expression , Such as ( 1 + 2 ) * ( 3 + 4 ) .
The inverse Polish expression of the formula is written as ( ( 1 2 + ) ( 3 4 + ) * ) .
The inverse Polish expression has two main advantages ：

There is no ambiguity in the expression after removing the brackets , Even if the above formula is written as 1 2 + 3 4 + * You can also calculate the correct result according to the order .
It is suitable for stack operation ： When it comes to numbers, it's on the stack ; When you encounter an operator, you take out two numbers at the top of the stack to calculate , And push the results into the stack

1.2.2 Code

The better thing is that expressions can be evaluated directly in order , Without considering the priority of operators

So it means pushing numbers onto the stack , Then, two numeric operations pop up when an operator is encountered , The result is pushed onto the stack

Pay attention to the position of numbers on both sides of the operator , The first pop-up element is on the right side of the operator

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for i in tokens :
            if i == '+':
                stack.append( stack.pop() + stack.pop() )
            elif i == '-':
                stack.append( -stack.pop() + stack.pop() )
            elif i == '*':
                stack.append( stack.pop() * stack.pop() )
            elif i == '/':
                stack.append( int(1/stack.pop() * stack.pop()) )
            else :
                stack.append(int(i))
        return stack.pop()

1.2.3 summary

For subtraction , The first thing that pops up is subtraction , The symbol is required

Empathy , For division , The first thing that pops up is the divisor , You need to count down

2. Assignment topic

2.1 Smallest stack

2.1.1 describe

Design a support push ,pop ,top operation , And can retrieve the stack of the smallest elements in a constant time .

push(x) —— Put the element x Push into the stack .
pop() —— Delete the element at the top of the stack .
top() —— Get stack top element .
getMin() —— Retrieve the minimum elements in the stack .

Example :

Input ：
[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”]
[[],[-2],[0],[-3],[],[],[],[]]
 
Output ：
[null,null,null,null,-3,null,0,-2]
 
explain ：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> return -3.
minStack.pop();
minStack.top(); --> return 0.
minStack.getMin(); --> return -2.

Tips ：

pop、top and getMin The operation is always in Non empty stack On the call .

2.1.2 Code

There's nothing to say , Just intuitively realize

class MinStack:

    def __init__(self):
        self.stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)

    def pop(self) -> None:
        if self.stack :
            self.stack.pop()

    def top(self) -> int:
        if self.stack :
            return self.stack[-1]

    def getMin(self) -> int:
        if self.stack :
            return min(self.stack)

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

2.1.3 summary

Instances of the entire class maintain a list , So you need to use... When initializing self Set a variable

top Is to access the top element of the stack , No stack changes ;pop Is the pop-up stack top element , Changed stack

2.2 Compare strings with backspace

2.2.1 describe

Given s and t Two strings , When they are entered into a blank text editor , Please judge whether the two are equal .# For backspace characters .

If equal , return true ; otherwise , return false .

Be careful ： If you enter backspace characters for empty text , Text continues to be empty .

Example 1：

Input ：s = “ab#c”, t = “ad#c”
Output ：true
explain ：S and T Will become “ac”.

Example 2：

Input ：s = “ab##”, t = “c#d#”
Output ：true
explain ：s and t Will become “”.

Example 3：

Input ：s = “a##c”, t = “#a#c”
Output ：true
explain ：s and t Will become “c”.

Example 4：

Input ：s = “a#c”, t = “b”
Output ：false
explain ：s Will become “c”, but t Still “b”.

Tips ：

1 <= s.length, t.length <= 200
s and t It contains only lowercase letters and characters ‘#’

Advanced ：

You can use it. O(N) Time complexity and O(1) Does spatial complexity solve the problem ？

2.2.2 Code

The intuitive way is to create two stacks , Encounter non # It into the stack , encounter # Just pop up at the top of the stack , Then compare

class Solution:
    def delBlank(self, s:str) -> str :
        stack = []
        for i in s:
            if i != '#' :
                stack.append(i)
            elif stack :
                stack.pop()
                
        return "".join(stack)
    
    def backspaceCompare(self, s: str, t: str) -> bool:
    
        return self.delBlank(s) == self.delBlank(t)

The advanced method is to compare the original array , And it's in reverse order

Because the backspace # Is entered after the character , Reverse order is better

If it's sequential , Once you encounter a backspace symbol , We have to go back and deal with it

So it's reverse scanning , Compare the corresponding elements of two arrays one by one

If you encounter # Sequence , Delete elements by shifting the corresponding length to the left

Once you encounter a mismatched element, you jump out , The two strings must be different

Or just a walk away , One is not over yet , The length is not the same

class Solution:
    def backspaceCompare(self, S: str, T: str) -> bool:
        i, j = len(S) - 1, len(T) - 1
        skipS = skipT = 0

        while i >= 0 or j >= 0:
            while i >= 0:
            #  Handle S Which is continuous # Sequence 
                if S[i] == "#":
                    skipS += 1
                    i -= 1
                #  If it is # Then write down the step size and move it to the left 
                elif skipS > 0:
                    skipS -= 1
                    i -= 1
                #  Until the character is not # until 
                #  The subscript moves left to mark the step size 
                #  That is, delete the corresponding characters 
                else:
                    break
                #  Left shift completed , Finish processing the # Sequence 
            while j >= 0:
            #  Handle T Which is continuous # Sequence 
                if T[j] == "#":
                    skipT += 1
                    j -= 1
                #  If it is # Then write down the step size and move it to the left 
                elif skipT > 0:
                    skipT -= 1
                    j -= 1
                #  Until the character is not # until 
                #  The subscript moves left to mark the step size 
                #  That is, delete the corresponding characters 
                else:
                    break
                #  Left shift completed , Finish processing the # Sequence 
            if i >= 0 and j >= 0:
            #  If this position is not the end 
                if S[i] != T[j]:
                    return False
                #  Determine whether the current characters are consistent 
            elif i >= 0 or j >= 0:
            #  Otherwise, if one of them is over 
            #  And this is another unfinished business 
                return False
                
            i -= 1
            j -= 1
            #  The current characters are consistent 
            #  Move left to judge the next 
        
        return True

2.2.3 summary

Intuitive approach , Generally, it is similar to the operation of printing tables , Need something to help

Advanced approach , That is to operate directly on the original array , Using pointers, etc

There are one or more of these situations , It's usually a sequence , Use while Cycle through processing

2.3 Basic calculator II

2.3.1 describe

Here's a string expression for you s , Please implement a basic calculator to calculate and return its value .

Division of integers preserves only the integral part .

Example 1：

Input ：s = “3+2*2”
Output ：7

Example 2：

Input ：s = " 3/2 "
Output ：1

Example 3：

Input ：s = " 3+5 / 2 "
Output ：5

Tips ：

1 <= s.length <= 3 * 105
s By integers and operators (’+’, ‘-’, ‘*’, ‘/’) form , The middle is separated by some spaces
s It means a Valid expressions
All integers in an expression are nonnegative integers , And in scope [0, 231 - 1] Inside
The question data guarantees that the answer is 32-bit Integers

2.3.2 Code

This is a bit like the previous inverse Polish expression , But this is about the order of operations

If you consider order, multiply and divide first , Add and subtract only after multiplication and division

Let's calculate multiplication and division directly off the stack , For addition and subtraction, assign symbols to numbers

Put it at the end and calculate it together , This makes multiplication and division prior to addition and subtraction

Next we have to consider the details of the operation , Because the input is a string

So for the quotation marks of the string , We can just ignore , Never mind

If you want to calculate , That should be to ensure that there are numbers in the stack , Then read the operation symbol

Then read another number completely , Operate on this expression

So the trigger condition for the operation should be , After the second number is read

So how to judge ？ Look at the current bit of the string , Whether it is an operation symbol or a number

If the current digit is still a number , This indicates that the value is more than one digit , Not finished reading

If the current bit is an operation symbol , Then it is proved that the value reading is complete , It's ready to operate

in other words , We need to read the second operator , Calculate with the previous operator

So we need a variable to store the first operator , And update to the second operator at the end of the operation

At the same time, the read value also needs a variable storage , It is also easy to read the next value after operation

Get the value at the top of the stack , The first operation symbol presign, And the number just read num Just do the calculation

Update after operation presign Is the operator of the current bit , Reset at the same time num To read the next value

class Solution:
    def calculate(self, s: str) -> int:
        n = len(s)
        stack = []
        preSign = '+'
        #  Set the leading symbol to +, No effect 
        num = 0
        for i in range(n):
            if s[i] != ' ' and s[i].isdigit():
                num = num * 10 + ord(s[i]) - ord('0')
                #  There may be more than one number , Full read 
            if i == n - 1 or s[i] in '+-*/':
            #  After encountering symbols , Expression before starting evaluation 
                if preSign == '+':
                    stack.append(num)
                #  The plus sign is pressed directly into the original number 
                elif preSign == '-':
                    stack.append(-num)
                #  The minus sign pushes in the opposite number 
                elif preSign == '*':
                    stack.append(stack.pop() * num)
                #  Multiply to get the top of the stack and then press 
                else:
                    stack.append(int(stack.pop() / num))
                #  Divide and take the reciprocal of the top of the stack before pressing 
                preSign = s[i]
                #  Record this operation symbol , So that the next operation 
                num = 0
                #  Reset number , To read the next number 
        return sum(stack)
        #  Finally, sum all elements in the station , That is, calculate the addition and subtraction 

2.3.3 summary

ord() Function is to find the corresponding character parameter of the passed in character ASCII character string

The basic construction of an operable expression is generally Numbers + Operator + Numbers The format of

So the trigger condition for the operation should be , After the second number is read

Also note that this is a string , The value may be more than one digit

And there is no operation symbol after the last operable expression

So the trigger condition of the last operation needs to be specified