LC 225 & LC 20 & LC 1047 & LC 150

Solution to LeetCode 225 Implement Stack using Queues & LC 20 Valid Parentheses & LC 1047 Remove All Adjacent Duplicates in String & LC 150 Evaluate Reverse Polish notation.

LeetCode 225

Implement Stack using Queues (Easy) [link]

Using two queues:

class MyStack:

    def __init__(self):
        self.queue_in = deque()
        self.queue_out = deque()

    def push(self, x: int) -> None:
        self.queue_in.append(x)

    def pop(self) -> int:
        if self.empty():
            return None
        for i in range(len(self.queue_in)-1):
            self.queue_out.append(self.queue_in.popleft())
        self.queue_out, self.queue_in = self.queue_in, self.queue_out
        return self.queue_out.popleft()

    def top(self) -> int:
        if self.empty():
            return None
        return self.queue_in[-1]

    def empty(self) -> bool:
        return len(self.queue_in) == 0

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

Using one queue:

class MyStack:

    def __init__(self):
        self.que = deque()

    def push(self, x: int) -> None:
        self.que.append(x)

    def pop(self) -> int:
        if self.empty():
            return None
        for i in range(len(self.que)-1):
            self.que.append(self.que.popleft())
        return self.que.popleft()

    def top(self) -> int:
        if self.empty():
            return None
        return self.que[-1]

    def empty(self) -> bool:
        return len(self.que) == 0

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

LeetCode 20

Valid Parentheses (Easy) [link]

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

LeetCode 1047

Remove All Adjacent Duplicates in String. (Easy) [link]

class Solution:
    def removeDuplicates(self, s: str) -> str:
        stack = []
        for it in s:
            if stack and it == stack[-1]:
                stack.pop()
            else:
                stack.append(it)
        return ''.join(stack)

LeetCode 150

Evaluate Reverse Polish notation (Medium) [link]

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        stack = []
        for tok in tokens:
            if tok not in ['+','-','*','/']:
                stack.append(tok)
            else:
                first, second = stack.pop(), stack.pop()
                stack.append(int(eval(f'{second} {tok} {first}')))
        return int(stack.pop())