简单算法问题

数据结构

栈

栈的实现

描述：请你实现一个栈。

push x : 将 x 入栈，保证 x 为 int 整数。
pop ：输出栈顶，并让栈顶出栈。
top ：输出栈顶，栈顶不出栈。

输入描述：第一行为一个正整数 n 代表操作次数。（1 <= n <= 100000），接下来的 n，每行为一个字符串，代表一个操作。

输出描述：如果操作为 push，则不输出任何东西。如果为另外两种，若栈为空，则输出 “error”。否则按对应操作输出。

示例：

输入：
	6
    push 1
    pop
    top
    push 2
    push 3
    pop
输出：
    1
    error
    3

class Stack:
    def __init__(self, size=100000) -> None:
        self.stack = []
        self.size = size
        self.index = -1

    def is_empty(self):
        if self.index == -1:
            print("error")
            return True
        else:
            return False

    def push(self, num):
        self.stack.append(num)
        self.index += 1
    
    def pop(self):
        if self.is_empty():
            return
        else:
            res = self.stack.pop()
            self.index -= 1
            print(res)

    def top(self):
        if self.is_empty():
            return
        else:
            res = self.stack[self.index]
            print(res)


n = int(input())
s = Stack()
for line in range(n):
    str = input()
    if str == 'pop':
        s.pop()
    elif str == 'top':
        s.top()
    else:
        s1 = str.split(' ')
        s.push(int(s1[1]))

栈的压入、弹出序列

描述：输入练个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈道所有数字均不相等。例如序列 1，2，3，4，5 是某栈道压入顺序，序列 4，5，3，2，1 是该压栈序列对应的一个弹出序列，但 4，3，5，1，2 就不可能是该压栈序列的弹出序列。

1、0 <= pushV.length == popV.length <= 1000。
2、-1000 <= pushV[i] <= 1000。
3、pushV 的所有数字均不同。

示例1：

输入：
    [1,2,3,4,5],[4,5,3,2,1]
返回值：
	true
说明：
    可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()
    这样的顺序得到[4,5,3,2,1]这个序列，返回true。

示例2：

输入：
    [1,2,3,4,5],[4,3,5,1,2]
返回值：
    false
说明：
    由于是[1,2,3,4,5]的压入顺序，[4,3,5,1,2]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false。

方法一：我们通过一个辅助栈来判断是否能够实现这样的压栈顺序。思路并不困难，首先我们有 pushV 和 popV 两个数组，那么我们需要做的是遍历出栈数组，然后判断入栈数组中的数是否要入栈，接着再看栈的栈顶是不是等于出栈数组的数，如果是的话就出栈，否则就是这个出栈方案不满足条件。

def IsPopOrder(self , pushV: List[int], popV: List[int]) -> bool:
    n = len(pushV)		# 获取栈长度
    stack = []		# 用列表作为栈
    j = 0		# 用于输入栈的遍历
    for i in range(n):		# 遍历输出
        while j < n and (len(stack) == 0 or stack[-1] != popV[i]):
            # 当栈为空或者栈首位与输出栈不同的时候才入栈
            stack.append(pushV[j])
            j += 1
        if stack[-1] == popV[i]:
            # 判断栈顶是否与出栈一致，是就是出栈
            stack.pop()
        else:
            return False
    return True

方法二：实际上，我们可以用 pushV 作为栈进行判断，做法就是用一个变量 n 同时作为栈顶和索引，我们遍历数组 pushV 的每个元素，将它赋值给 pushV[n]，然后判断数组是否不为空且栈顶的第一个元素是否与 popV 数组的元素相同，如果是就出栈，最后判断栈是否为空，作为能否成功出栈的依据。

def IsPopOrder(self , pushV: List[int], popV: List[int]) -> bool:
    n = 0		# 栈顶 和 数组索引
    j = 0 		# popV的索引
    for num in range(pushV):
        pushV[n] = num
        while n >= 0 and pushV[n] == pop[j]:
            # 满足条件 栈不空 且与 出栈顺序相等
            j += 1
            n -= 1
        n += 1
    return True if n == 0 else False

有效括号序列

描述：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s。

要求：判断字符串 s 是否有效（即括号是否匹配）。

说明：

有效字符串需满足：
1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。

示例：

输入：s = "()"
输出：True


输入：s = "()[]{}"
输出：True

def isValid(self , s: str) -> bool:
    # write code here
    stack = []
    n = -1
    for s_ in s:
        if n > -1 and stack[n] == '(' and s_ == ')':
            stack.pop()
            n -= 1
        elif n > -1 and stack[n] == '{' and s_ == '}':
            stack.pop()
            n -= 1
        elif n > -1 and stack[n] == '[' and s_ == ']':
            stack.pop()
            n -= 1
        else:
            stack.append(s_)
            n += 1
    
    return True if n == -1 else False

逆波兰表达式

描述：给定一个逆波兰表达式，求表达式的值。

数据范围：1 <= n <= 100000，表达式中仅包含数字和 +，-，*，/，其中数字的大小满足 $|val| \leq 200$。

示例：

输入：["2","1","+","4","*"]
返回值：12

输入：["2","0","+"]
返回值：2

def evalRPN(self , tokens: List[str]) -> int:
    # write code here
    stack = []
    for t in tokens:
        if t == '+':
            n1 = int(stack.pop())
            n2 = int(stack.pop())
            stack.append(n1+n2)
        elif t == '-':
            n1 = int(stack.pop())
            n2 = int(stack.pop())
            stack.append(n2-n1)
        elif t == '*':
            n1 = int(stack.pop())
            n2 = int(stack.pop())
            stack.append(n1*n2)
        elif t == '/':
            n1 = int(stack.pop())
            n2 = int(stack.pop())
            stack.append(n2/n1)
        else:
            stack.append(t)
    return int(stack[-1])

中缀表达式转逆波兰表达式(后缀表达式)

中缀表达式就是我们所熟悉的表达式，需要关注运算符的优先级，比如 3 + 4 * 2，就要先算 4 * 2。

后缀表达式，也称为逆波兰表达式，运算符写在操作数后面，比如 (3 + 4) * 5 - 6，为 3 4 + 5 * - 6。

将中缀表达式变成后缀表达式的规则就是把每个运算符都移到它的两个操作数的后面，然后删除括号。

我们需要两个栈 a 和 b，a 用来存储转换过程，b 用于临时存储操作符与小括号。

主要注意的是 b 栈的进出规则，如果扫描到当前符号比栈中的符号优先级要低，则先出栈再将该符号入栈。
def frontToBack(tokens):
    a = []
    b = []
    for t in tokens:
        if t.isnumeric():
            a.append(t)
        else:
            if t == '*' or t == '/' or t == '(':
                b.append(t)
            elif t == '+' or t == '-':
                if b[-1] and b[-1] == '*' or b[-1] == '/':
                    a.append(b.pop())
                b.append(t)
            elif t == ')':
                o = b.pop()
                while o != '(':
                    a.append(o)
                    o = b.pop()
    while b:
        a.append(b.pop())
    return a