6 posts tagged with "Stack"

from typing import Callable


class Solution:
    def evalRPN(self, tokens: list[str]) -> int:
        stack: list[int] = []
        operators: dict[str, Callable[[int, int], int]] = {
            '+': lambda a, b: a + b,
            '-': lambda a, b: a - b,
            '*': lambda a, b: a * b,
            '/': lambda a, b: int(a / b),
        }
        for token in tokens:
            if token in operators:
                b, a = stack.pop(), stack.pop()
                stack.append(operators[token](a, b))
            else:
                stack.append(int(token))
        return stack[0]

class Solution:
    def dailyTemperatures(self, temperatures: list[int]) -> list[int]:
        result = [0] * len(temperatures)
        stack = []
        for r in range(len(temperatures)):
            while stack and temperatures[stack[-1]] < temperatures[r]:  # l < r
                l = stack.pop()
                result[l] = r - l
            stack.append(r)
        return result

class Solution:
    def asteroidCollision(self, asteroids: list[int]) -> list[int]:
        s: list[int] = []
        for a in asteroids:
            s.append(a)
            while len(s) > 1 and s[-2] > 0 > s[-1]:
                if s[-2] == -s[-1]:
                    s.pop()
                elif s[-2] < -s[-1]:
                    s[-2] = s[-1]
                s.pop()
        return s

class Solution1:
    def simplifyPath(self, path: str) -> str:
        stack = []
        for p in path.split('/'):
            if p == '..':
                stack.pop() if stack else None
            elif p and p != '.':
                stack.append(p)
        return '/' + '/'.join(stack)


class Solution:
    def simplifyPath(self, path: str) -> str:
        stack = []
        for p in path.split('/'):
            d = {'': stack, '.': stack, '..': stack[:-1]}
            stack = d.get(p, stack + [p])
        return '/' + '/'.join(stack)

class Solution:
    def isValid(self, s: str) -> bool:
        P = {
            '(': ')',
            '{': '}',
            '[': ']',
        }
        stack = []
        for c in s:
            if stack and P.get(stack[-1]) == c:
                stack.pop()
            else:
                stack.append(c)
        return not stack

class Solution1:
    def backspaceCompare(self, s: str, t: str) -> bool:
        S = '#'
        ss, st = [], []
        for c in s:
            if c != S:
                ss.append(c)
            elif ss:
                ss.pop()
        for c in t:
            if c != S:
                st.append(c)
            elif st:
                st.pop()
        return ss == st


class Solution:
    def backspaceCompare(self, s: str, t: str) -> bool:
        def go_left(string, pointer, backspace):
            S = '#'
            while pointer >= 0 and (backspace or string[pointer] == S):
                backspace += (-1) ** (string[pointer] != S)
                pointer -= 1
            return pointer, backspace

        ps, pt = len(s) - 1, len(t) - 1  # pointer
        bs, bt = 0, 0  # backspace
        while True:
            (ps, bs), (pt, bt) = go_left(s, ps, bs), go_left(t, pt, bt)
            if not (ps >= 0 and pt >= 0 and s[ps] == t[pt]):
                return ps == pt == -1
            ps -= 1
            pt -= 1