LeetCode 20 - Valid Parentheses

topic:
Given a string consisting only of '(', ')', '{', '}', '[', ']', determine whether the string is valid.

A valid string must satisfy:

An opening parenthesis must be closed with a closing parenthesis of the same type.
Opening parentheses must be closed in the correct order.
Note that an empty string is considered a valid string.

Example 1:
Input: "()"
output: true

Topic link: 20 - valid parentheses

Ideas:
There are three situations where stack matching fails: 1. Excessive left parentheses 2. Excessive closing parentheses 3. The number of parentheses is fine, but the types do not match. Check whether parentheses are redundant by comparing the number of closing parentheses.
Traverse the string, put the corresponding right bracket into the stack every time "(" "[" "{" is encountered, pop the top element of the stack when the right bracket is encountered, and return False if the top element of the stack is different from the current right bracket symbol ; Or if the stack is found to be empty during the traversal process, False will be returned if there is no matching character; if the string is traversed and the stack is not empty, False will also be returned.

class Solution:
    def isValid(self, s: str) -> bool:
        stack = []
        
        for item in s:
            if item == '(':
                stack.append(')')
            elif item == '[':
                stack.append(']')
            elif item == '{':
                stack.append('}')
            elif not stack or stack[-1] != item:
                return False
            else:
                stack.pop()
        
        return True if not stack else False   #Return True if the stack is empty

LeetCode 1047 - Remove all adjacent duplicates in a string

topic:
Given a string S consisting of lowercase letters, the duplicate removal operation selects two adjacent identical letters and removes them.
Repeat the deduplication operation on S until no further deduplication is possible.
Returns the final string after all deduplication operations have completed. The answer is guaranteed to be unique.

Example:
Enter: "abbaca"
Output: "ca"
Explanation: For example, in "abbaca", we can delete "bb" Since the two letters are adjacent and identical, this is the only duplicate that can be deleted at this time. Then we get the string "aaca", where again only "aa" can be deduplicated, so the final string is "ca".

Topic link: 1047 - Remove all adjacent duplicates in a string

Ideas:
Use the stack to store letters, traverse the string, if the current character is the same as the top character on the stack, pop the top element out of the stack, otherwise store the character in the stack.

class Solution:
    def removeDuplicates(self, s: str) -> str:
        res = list()
        for item in s:
            if res and res[-1] == item:
                res.pop()
            else:
                res.append(item)
        return "".join(res)

LeetCode 150-Reverse Polish Expression Evaluation

topic:
Evaluates the expression according to Reverse Polish Notation.
Valid operators include + , - , * , / . Each operand can be an integer or another reverse Polish expression.

illustrate:
Integer division keeps only the integer part. The given reverse Polish expression is always valid. In other words, the expression will always result in a valid value and no divisor by 0 will exist.

Example 1:
Input: ["2", "1", "+", "3", " * "]
Output: 9
Explanation: This formula is transformed into a common infix arithmetic expression: ((2 + 1) * 3) = 9

Topic link: 150 - Reverse Polish Expression Evaluation

Ideas:
Traverse the string, store non-arithmetic operators into the stack, and pop the first two characters on the top of the stack when encountering an arithmetic operator, the first popped number is on the right side of the operator, and the second popped number is operated on the left side of the string The result of the operation continues to be stored on the stack.
Note: python's division is rounded down. If you encounter a negative number, the division result will be far away from 0. (For example, -13//10=-2 is not the -1 required by this question). You cannot directly use integer division. You need to divide by first and then divide The result is cast to type int.

from operator import add, mul, sub # The operator function provides the corresponding function for the corresponding arithmetic operator

class Solution:
    op_map = {'+': add, '-': sub, '*': mul, '/': lambda x, y: int(x / y)} #Anonymous function set division
    #python's division is rounded down. If a negative number is encountered, the division result will be far away from 0. You cannot directly use integer division. You need to divide by first and then convert the result to an int type

    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for token in tokens:
            if token not in {'+', '-', '*', '/'}:
                stack.append(int(token))
            else:
                op2 = stack.pop()
                op1 = stack.pop()
                stack.append(self.op_map[token](op1,op2))
        return stack.pop()