栈

1、有效的括号
题目内容：
给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

输入格式:
一行字符串

输出格式：
True或False，表示该输入是否为合法括号串
输入样例：([])
输出样例：True
解题思路：遇到左括号存储到栈，右括号与栈最上部元素匹配

代码

def matches(open, close):
    opens = '({['
    closers = ')}]'
    return opens.index(open) == closers.index(close)

def isValid(s):
    stack = []
    balanced = True
    index = 0
    while index < len(s) and balanced:
        st = s[index]
        if st in "({[":
            stack.append(st)
        else:
            if not stack:
                balanced = False
            else:
                top = stack.pop()
                if not matches(top, st):
                    balanced = False
        index += 1
    if not stack and balanced:
        return True
    else:
        return False

print(isValid('([{})])'))

2、每日温度
题目内容：
根据每日气温列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替
输入格式:
一行以Python表达式格式给出的列表，包含数个整数
输出格式：
整数组成的列表，直接使用print输出

输入样例：[73, 74, 75, 71, 69, 72, 76, 73]
输出样例：[1, 1, 4, 2, 1, 1, 0, 0]

Python代码

def dailyTemp(T):
    stack = []
    res = [0] * len(T)
    for index, value in enumerate(T):
        while stack and T[stack[-1]] < value:
            cur = stack.pop()
            res[cur] = index - cur
        stack.append(index)
    return res

print(dailyTemp([73, 74, 75, 71, 69, 72, 76, 73]))

3、后缀表达式求值
题目内容：
根据后缀表达式表示法，求表达式的值。
有效的运算符包括 +, -, *, / ；其中除法仅保留整数结果。
若出现除数为0或表达式非法的情况，输出"NaN"
注：
每个数字token可包含多位，也可为负数
除法统一使用 int(a / b) 而非 a // b 进行计算
输入格式:
一行字符串，每个token间以空格分隔
输出格式：
一行，包含一个整数或"NaN"
输入样例：“4 13 5 / +”
输出样例：6

代码

def calc(tokens):
    operandStack = []
    tokenList = tokens.split()
    for token in tokenList:
        if token not in "+-*/":
            operandStack.append(int(token))
        else:
            operand2 = operandStack.pop()
            operand1 = operandStack.pop()
            result = doMath(token, operand1, operand2)
            operandStack.append(result)
    return operandStack.pop()

def doMath(op, op1, op2):
    if op == "*":
        return op1 * op2
    elif op == "/":
        return int(op1 / op2)
    elif op == "+":
        return op1 + op2
    else:
        return op1 - op2

print(calc("4 13 5 / +"))

1有效的括号（10分）
题目内容：
给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
输入格式:
一行字符串
输出格式：
True或False，表示该输入是否为合法括号串
输入样例1：
([])
输出样例1：
True
输入样例2：
{{)]}
输出样例2：
False

class Stack:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        # 检查栈是否为空，布尔型
        return self.items == []

    def push(self, item):
        # 将一个元素添加到栈的顶端
        self.items.append(item)

    def pop(self):
        # 将栈顶端的元素移除，且返回该元素
        return self.items.pop()

    def peek(self):
        # 返回栈顶端的元素，但不移除
        return self.items[len(self.items) - 1]

    def size(self):
        # 返回栈中元素数量
        return len(self.items)


def parChecker(symbolString):
    s = Stack()
    index = 0
    balanced = True
    while index < len(symbolString) and balanced:
        symbol = symbolString[index]
        if symbol in '([{':
            s.push(symbol)
        else:
            if s.isEmpty():
                balanced = False
            else:
                top = s.pop()
                if not matches(top, symbol):
                    balanced = False
        index += 1
    if balanced and s.isEmpty():
        return True
    else:
        return False

def matches(open, close):
    opens = '([{'
    closes = ')]}'
    return opens.index(open) == closes.index(close)

print(parChecker(input()))

2、一维开心消消乐（10分）
题目内容：
开心消消乐我们都熟悉，我们可以用刚学过的栈来做一个“一维”的开心消消乐游戏，这个游戏输入一串字符，逐个消去相邻的相同字符对。
如果字符全部被消完，则输出不带引号的“None”
输入格式:
一个字符串，可能带有相邻的相同字符，如“aabbbc”
输出格式：
一个字符串，消去了相邻的成对字符，如“bc”
输入样例1：
beepooxxxyz
输出样例1：
bpxyz
输入样例2：
kxkx
输出样例2：
kxkx
输入样例3：（这里bb被消了以后，第二个a挨上来了，所以两个a也相邻，同样消去）
abbacddccc00
输出样例3：
None

def happyGames():
    playStrings = input()
    s = Stack()
    for play in playStrings:
        if s.isEmpty():
            s.push(play)
            continue
        if s.peek() == play:
            s.pop()
        else:
            s.push(play)
    if s.isEmpty():
        print(None)
    else:
        print(''.join(s.items))
happyGames()

3、强迫症老板和他的洗碗工（10分）
题目内容：
洗碗工小明碰上了一位强迫症老板老王，餐厅一共就10只盘子，老板给仔细编上了0～9等10个号码，并要求小明按照从0到9的编号来洗盘子，当然，每洗好一只盘子，就必须得整齐叠放起来。
小明洗盘子期间，经常就有顾客来取盘子，当然每位顾客只能从盘子堆最上面取1只盘子离开。
老王在收银台仔细地记录了顾客依次取到盘子的编号，比如“1043257689”，这样他就能判断小明是不是遵照命令按照0123456789的次序来洗盘子了。
你也能像老王一样作出准确的判断吗？
输入格式:
长度为10的字符串，其中只包含0～9的数字，且不重复，代表顾客依次取到的盘子编号
输出格式：
字符串：Yes或者No，表示遵照次序洗盘子，或者没有遵照次序洗盘子
输入样例1：
1043257689
输出样例1：
Yes
输入样例2：
4230178956
输出样例2：
No

def washDish():
    """
    1043257689 Yes
    4321078965 Yes
    4230178956 No
    思路：
    #若栈为空，推入栈，并将存储的编号设为None
    若栈不为空，则比较栈顶部数字与该数字大小：
    若小于栈顶部peak，num应为比peak小且离peak最近的没拿走过的盘子号。如序列4321078965中的96
    若大于栈顶部数字，直接入栈
    :return:
    """
    numInput = input()
    sequence = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]  # 存储现有盘子
    found = True  # 是否按顺序
    s = Stack()
    index = 0
    while index < len(numInput) and found:
        num = int(numInput[index])
        if s.isEmpty():
            s.push(num)
            sequence[num] = None
        else:
            peak = int(s.peek())
            if num < peak:
                while num != peak - 1 and found:
                    if sequence[peak-1] == None:
                        peak = peak-1
                    else:
                        found = False
                else:
                    s.push(num)
                    sequence[int(num)] = None
            else:
                s.push(num)
                sequence[int(num)] = None
        index += 1
    if found == True:
        print('Yes')
    else:
        print('No')
washDish()