栈

栈（Stack） 是一种经典的数据结构，它具有“后进先出”（Last-In-First-Out，LIFO）的特性。栈一般有两个根本操作：压栈（Push）和弹栈（Pop）。压栈操作将数据元素增加到栈顶，弹栈操作将栈顶的元素弹出。

除了根本操作，栈还有其他几个重要的概念：

  1. 栈顶（Top）：栈中终究一个压入的元素。

  2. 栈底（Bottom）：栈中最早被压入的元素。

  3. 栈空（Empty）：栈中没有任何元素。

  4. 栈满（Full）：栈中现已没有剩余的空间能够容纳新的元素。

栈的应用非常广泛，常见的应用场景包含：

  1. 程序的函数调用仓库：每个函数的参数和回来值都被存储在一个栈帧（Stack Frame）中，调用一个函数时就将其栈帧压入栈中，函数回来时再将其栈帧弹出。

  2. 表达式求值：将中缀表达式转换为后缀表达式，再运用栈来求解后缀表达式。

  3. 修改器的吊销和重做操作：运用两个栈，一个栈用于存储前史修改操作，另一个栈用于存储已吊销的操作。

  4. 浏览器的前进和撤退操作：运用两个栈，一个栈用于存储已拜访过的页面，另一个栈用于存储现已拜访过的页面的前一个页面。

栈的完结方式有多种，常见的完结方式包含数组完结和链表完结。数组完结的栈具有随机拜访的特性，但刺进和删去操作的时刻杂乱度较高；链表完结的栈具有刺进和删去操作的时刻杂乱度较低，但拜访元素的时刻杂乱度较高。

Python中能够运用列表（List）来完结栈的功用，由于列表能够在末尾增加和删去元素，能够很方便地完结栈的压入和弹出操作。

以下是运用列表完结栈的根本操作：

  1. 创建一个空的栈：
stack = []
  1. 将元素压入栈中：
stack.append(element)
  1. 从栈中弹出一个元素：
element = stack.pop()
  1. 获取栈顶元素：
element = stack[-1]
  1. 检查栈是否为空：
if not stack:
    print("stack is empty")

假如不嫌麻烦，能够把栈的完结能够封装成一个类，方便运用。以下是一个简略的栈类的完结：

class Stack:
    def __init__(self):
        self.stack = []
    def push(self, element):
        self.stack.append(element)
    def pop(self):
        if not self.stack:
            return None
        return self.stack.pop()
    def peek(self):
        if not self.stack:
            return None
        return self.stack[-1]
    def is_empty(self):
        return not self.stack

运用这个类，能够很方便地创建栈目标，并运用栈的各种方法：

stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.pop())  # 3
print(stack.peek())  # 2
print(stack.is_empty())  # False

155. 最小栈

规划一个支撑push，pop，top操作，并能在常数时刻内检索到最小元素的栈。

完结MinStack类:

  • MinStack()初始化仓库目标。
  • void push(int val)将元素val推入仓库。
  • void pop()删去仓库顶部的元素。
  • int top()获取仓库顶部的元素。
  • int getMin()获取仓库中的最小元素。

示例 1:

输入：
[“MinStack”,”push”,”push”,”push”,”getMin”,”pop”,”top”,”getMin”]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解说：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); –> 回来 -3.
minStack.pop();
minStack.top(); –> 回来 0.
minStack.getMin(); –> 回来 -2.

提示：

  • −231<=val<=231−1-2^{31}<= val <= 2^{31}- 1
  • pop、top和getMin操作总是在非空栈上调用
  • push,pop,top, andgetMin最多被调用3∗1043 * 10^4次

这个代码很简略，但是要留意标题的要求 “常数时刻取得最小值”。 所以用一个辅佐最小栈。

class MinStack:
    def __init__(self):
        self.vals = []
        self.minStack = [float('inf')]
    def push(self, val: int) -> None:
        self.vals.append(val)
        self.minStack.append(self.minStack[-1] if self.minStack[-1] < val else val)
    def pop(self) -> None:
        self.vals.pop()
        self.minStack.pop()
    def top(self) -> int:
        return self.vals[-1] 
    def getMin(self) -> int:
        return self.minStack[-1]
# 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()

20. 有用的括号

给定一个只包含'('，')'，'{'，'}'，'['，']'的字符串s，判别字符串是否有用。

有用字符串需满意：

  1. 左括号有必要用相同类型的右括号闭合。
  2. 左括号有必要以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

输入： s = “()”
输出： true

示例2：

输入： s = “()[]{}”
输出： true

示例3：

输入： s = “(]”
输出： false

提示：

  • 1 <= s.length <= 104
  • s仅由括号'()[]{}'组成
class Solution:
    def isValid(self, s: str) -> bool:
        brackets = {'(':')','[':']','{':'}'}
        stack = []
        for x in s:
            if stack and stack[-1] in brackets and brackets[stack[-1]] == x:
                stack.pop()
            else:
                stack.append(x)
        return not len(stack)

首先，界说了一个字典 brackets，用于存储括号的匹配关系。然后创建一个空栈 stack，遍历输入字符串 s 中的每一个字符：

  1. 假如栈不为空，而且栈顶的括号和当时字符能够匹配，则弹出栈顶的括号。

  2. 假如栈为空，或许栈顶的括号和当时字符不能匹配，则将当时字符压入栈中。

终究，假如栈为空，阐明一切的括号都匹配了，回来 True；不然回来 False。

150. 逆波兰表达式求值

给你一个字符串数组tokens，表明一个依据逆波兰表明法表明的算术表达式。

请你核算该表达式。回来一个表明表达式值的整数。

留意：

  • 有用的算符为'+'、'-'、'*'和'/'。
  • 每个操作数（运算目标）都能够是一个整数或许另一个表达式。
  • 两个整数之间的除法总是向零截断。
  • 表达式中不含除零运算。
  • 输入是一个依据逆波兰表明法表明的算术表达式。
  • 答案及一切中间核算成果能够用32 位整数表明。

示例1：

输入： tokens = [“2″,”1″,”+”,”3″,”*”]
输出： 9
解说： 该算式转化为常见的中缀算术表达式为：((2+1)∗3)=9((2 + 1) * 3) = 9

示例2：

输入： tokens = [“4″,”13″,”5″,”/”,”+”]
输出： 6
解说： 该算式转化为常见的中缀算术表达式为：(4+(13/5))=6(4 + (13 / 5)) = 6

示例3：

输入： tokens = [“10″,”6″,”9″,”3″,”+”,”-11″,”“,”/”,”“,”17″,”+”,”5″,”+”]
输出： 22
解说： 该算式转化为常见的中缀算术表达式为：

((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((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

提示：

  • 1<=tokens.length<=1041 <= tokens.length <= 10^4
  • tokens[i]是一个算符（"+"、"-"、"*"或"/"），或是在规模[-200, 200]内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后边。

  • 往常运用的算式则是一种中缀表达式，如( 1 + 2 ) * ( 3 + 4 )。
  • 该算式的逆波兰表达式写法为( ( 1 2 + ) ( 3 4 + ) * )。

逆波兰表达式主要有以下两个优点：

  • 去掉括号后表达式无歧义，上式即使写成1 2 + 3 4 + * 也能够依据次序核算出正确成果。
  • 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行核算，并将成果压入栈中
class Solution:
    def evalRPN(self, tokens: [str]) -> int:
        nums = []
        for i in tokens:
            if i.isdigit() or len(i)>1:   # 负数用isdigit()回来false
                nums.append(int(i))
            else:
                n1 = nums.pop()
                n2 = nums.pop()
                if i == '+':
                    nums.append(n2+n1)
                elif i == '-':
                    nums.append(n2-n1)
                elif i == '*':
                    nums.append(n2*n1)
                elif i == '/':
                    nums.append(int(n2/n1))
        return nums[-1]

该算法运用一个栈来盯梢表达式中的数字，在从左到右读取tokens时运用。当遇到一个数字时，它被推送到栈上。当遇到运算符时，栈上的前两个数字被弹出，运算符被应用于它们，然后将成果推回到栈上。

在循环结束时，栈上应该只剩下一个数字，这个数字是表达式的终究成果。这个数字作为函数的输出回来。

代码检查每个token以检查它是运算符还是数字。假如它是数字，则将其转换为整数并推送到栈上。假如它是运算符，则弹出栈上的前两个数字，并应用运算符。然后将成果推回到栈上。

代码处理四个运算符：+，-，*和/。假如运算符是+，则将弹出的两个数字相加，并将成果推回到栈上。假如运算符是-，则将第二个弹出的数字从第一个弹出的数字中减去，并将成果推回到栈上。假如运算符是*，则将弹出的两个数字相乘，并将成果推回到栈上。假如运算符是/，则将第二个弹出的数字除以第一个弹出的数字（运用整数除法），并将成果推回到栈上。

终究，函数回来栈中的终究一个元素，这应该是表达式的终究成果。

71. 简化途径

给你一个字符串path，表明指向某一文件或目录的Unix 风格绝对途径 （以'/'最初），请你将其转化为更加简练的标准途径。

在 Unix 风格的文件体系中，一个点（.）表明当时目录自身；此外，两个点 （..）表明将目录切换到上一级（指向父目录）；两者都能够是杂乱相对途径的组成部分。任意多个接连的斜杠（即，'//'）都被视为单个斜杠'/'。 对于此问题，任何其他格局的点（例如，'...'）均被视为文件/目录称号。

请留意，回来的标准途径有必要遵循下述格局：

  • 始终以斜杠'/'最初。
  • 两个目录名之间有必要只有一个斜杠'/'。
  • 终究一个目录名（假如存在）不能 以'/'结束。
  • 此外，途径仅包含从根目录到目标文件或目录的途径上的目录（即，不含'.'或'..'）。

回来简化后得到的标准途径。

示例 1：

输入： path = "/home/"
输出： "/home"
解说： 留意，终究一个目录名后边没有斜杠。

示例 2：

输入： path = “/../”
输出： “/”
解说： 从根目录向上一级是不可行的，由于根目录是你能够到达的最高级。

示例 3：

输入： path = “/home//foo/”
输出： “/home/foo”
解说： 在标准途径中，多个接连斜杠需求用一个斜杠替换。

示例 4：

输入： path = “/a/./b/../../c/”
输出： “/c”

提示：

  • 1 <= path.length <= 3000
  • path由英文字母，数字，'.'，'/'或'_'组成。
  • path是一个有用的 Unix 风格绝对途径。
class Solution:
    def simplifyPath(self, path: str) -> str:
        path = path.split('/')
        stack = []
        for i in path:
            if i == '' or i == '.':
                continue
            elif i == '..':
                if stack:
                    stack.pop()
            else:
                stack.append(i)
        return '/' + '/'.join(stack)

用于简化给定的 Unix 途径。它接受一个字符串参数 path，然后运用斜杠 / 分隔途径字符串，并将其存储在一个列表中。然后，代码遍历该列表，并依据以下规则对途径进行简化：

  • 假如当时途径是空字符串或许单点（.），则越过。
  • 假如当时途径是双点（..），则将栈中的终究一个途径弹出。
  • 假如当时途径不是单点或双点，则将其增加到栈中。

终究，代码运用 join 函数将栈中的途径组合成一个字符串，并在最初增加一个斜杠 /，然后将简化后的途径字符串作为成果回来。

394. 字符串解码

给定一个经过编码的字符串，回来它解码后的字符串。

编码规则为:k[encoded_string]，表明其中方括号内部的encoded_string正好重复k次。留意k确保为正整数。

你能够认为输入字符串总是有用的；输入字符串中没有额外的空格，且输入的方括号总是符合格局要求的。

此外，你能够认为原始数据不包含数字，一切的数字只表明重复的次数k，例如不会出现像3a或2[4]的输入。

示例 1：

输入： s = "3[a]2[bc]"
输出： "aaabcbc"

示例 2：

输入： s = "3[a2[c]]"
输出： "accaccacc"

示例 3：

输入： s = "2[abc]3[cd]ef"
输出： "abcabccdcdcdef"

示例 4：

输入： s = "abc3[cd]xyz"
输出： "abccdcdcdxyz"

提示：

  • 1 <= s.length <= 30

  • s由小写英文字母、数字和方括号'[]'组成

  • s确保是一个有用的输入。

  • s中一切整数的取值规模为[1, 300]

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        res = ''
        mul = 0
        for c in s:
            if c.isdigit():
                mul = mul*10 + int(c)
                # 留意mul的大小
            elif c == '[':
                stack.append([mul,res])
                res = ''
                mul = 0
            elif c == ']':
                m,s = stack.pop()
                res = s + m*res
            else:
                res += c
        return res

  1. 界说一个栈，一个字符串变量res用来保存当时解码的成果，一个整数变量mul用来保存当时数字字符所表明的倍数；

  2. 遍历字符串s中的每个字符c：

    a. 假如c是数字字符，将其参加mul变量的个位上；

    b. 假如c是左括号字符，将当时的mul和res入栈，并分别将mul和res初始化为0和空字符串；

    c. 假如c是右括号字符，弹出栈顶的mul和res，并将当时的res设置为栈顶的res加上mul个当时的res；

    d. 假如c是其他字符，直接将其参加res中；

  3. 终究回来res即为解码成果。

224. 根本核算器 – 力扣（Leetcode）

给你一个字符串表达式s，请你完结一个根本核算器来核算并回来它的值。

留意:不允许运用任何将字符串作为数学表达式核算的内置函数，比如eval()。

示例 1：

输入： s = "1 + 1"
输出： 2

示例 2：

输入： s = " 2-1 + 2 "
输出： 3

示例 3：

输入： s = "(1+(4+5+2)-3)+(6+8)"
输出： 23

提示：

  • 1<=s.length<=3∗1051 <= s.length <= 3* 10^5

  • s由数字、'+'、'-'、'('、')'、和' '组成

  • s表明一个有用的表达式

  • ‘+’不能用作一元运算(例如，”+1″和”+(2 + 3)”无效)

  • ‘-‘能够用作一元运算(即”-1″和”-(2 + 3)”是有用的)

  • 输入中不存在两个接连的操作符

  • 每个数字和运行的核算将适合于一个有符号的 32位 整数

class Solution:
    def calculate(self, s: str) -> int:
        ans = 0
        num = 0
        sign = 1
        stack = [sign]  # stack[-1]: current env's sign
        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c == '(':
                stack.append(sign)
            elif c == ')':
                stack.pop()
            elif c == '+' or c == '-':
                ans += sign * num
                sign = (1 if c == '+' else -1) * stack[-1]
                num = 0
        return ans + sign * num

  1. 初始化 ans 和 num 为 0，sign 为 1，stack 为 [sign]。

  2. 遍历字符串 s 中的每个字符 c：

    • 假如 c 是数字，则更新 num 为 num*10 + int(c)。

    • 假如 c 是左括号 (，则将当时的 sign 压入 stack 中，表明进入一个新的环境。

    • 假如 c 是右括号 )，则将 stack 的栈顶元素弹出，得到当时环境的符号 sign_env。将当时环境的成果 num 与当时环境的符号 sign_env 相乘，参加到 ans 中，表明当时环境的成果现已核算完结，能够退出当时环境了。

    • 假如 c 是加号 + 或减号 -，则将当时环境的成果 num 与当时环境的符号 sign_env 相乘，参加到 ans 中。更新当时环境的符号 sign 为 1 或 -1，具体依据 c 的值来判别。同时，将当时环境的符号 sign 与 stack 的栈顶元素相乘，得到当时环境下的符号，更新 stack 的栈顶元素。终究，将 num 重置为 0，开端下一个数字的解析。

  3. 终究，将 ans 与终究一个数字 num 乘以当时环境的符号 sign 相乘的成果相加，得到终究的核算成果。

需求留意的是，这个完结并没有考虑乘除法的优先级，只是依照从左到右的顺序进行核算。假如需求考虑优先级，能够在遍历时将乘除法的成果先核算出来，再核算加减法的成果。