Stacks & Queues

# Each closing bracket and the opener it must match.
PAIRS = {")": "(", "]": "[", "}": "{"}


def is_valid(s: str) -> bool:
    """Whether every bracket in `s` is closed by the same type, in the right order."""
    stack: list[str] = []
    for ch in s:
        opener = PAIRS.get(ch)
        if opener is None:
            stack.append(ch)  # An opener waits on the stack for its closer.
        elif not stack or stack.pop() != opener:
            return False  # A closer must match the most recent unclosed opener.
    return not stack  # Anything left was never closed.


if __name__ == "__main__":
    print(is_valid("([]){}"))  # True
    print(is_valid("([)]"))  # False
    print(is_valid("(("))  # False
    print(is_valid("]"))  # False

// Each closing bracket and the opener it must match.
const PAIRS = new Map([
  [")", "("],
  ["]", "["],
  ["}", "{"],
]);

// Whether every bracket in s is closed by the same type, in the right order.
export function isValid(s: string): boolean {
  const stack: string[] = [];
  for (const ch of s) {
    const opener = PAIRS.get(ch);
    if (opener === undefined) {
      stack.push(ch); // An opener waits on the stack for its closer.
    } else if (stack.length === 0 || stack.pop() !== opener) {
      return false; // A closer must match the most recent unclosed opener.
    }
  }
  return stack.length === 0; // Anything left was never closed.
}

console.log(isValid("([]){}")); // true
console.log(isValid("([)]")); // false
console.log(isValid("((")); // false
console.log(isValid("]")); // false

package main

import "fmt"

// pairs maps each closing bracket to the opener it must match.
var pairs = map[rune]rune{')': '(', ']': '[', '}': '{'}

// isValid reports whether every bracket in s is closed by the same type, in
// the right order.
func isValid(s string) bool {
	stack := []rune{}
	for _, ch := range s {
		opener, isCloser := pairs[ch]
		if !isCloser {
			stack = append(stack, ch) // An opener waits on the stack for its closer.
		} else if len(stack) == 0 || stack[len(stack)-1] != opener {
			return false // A closer must match the most recent unclosed opener.
		} else {
			stack = stack[:len(stack)-1]
		}
	}
	return len(stack) == 0 // Anything left was never closed.
}

func main() {
	fmt.Println(isValid("([]){}")) // true
	fmt.Println(isValid("([)]"))   // false
	fmt.Println(isValid("(("))     // false
	fmt.Println(isValid("]"))      // false
}

using System;
using System.Collections.Generic;

public class Solution
{
    // Each closing bracket and the opener it must match.
    static readonly Dictionary<char, char> Pairs = new() { [')'] = '(', [']'] = '[', ['}'] = '{' };

    // Whether every bracket in s is closed by the same type, in the right order.
    public static bool IsValid(string s)
    {
        var stack = new Stack<char>();
        foreach (char ch in s)
        {
            if (!Pairs.TryGetValue(ch, out char opener))
            {
                stack.Push(ch); // An opener waits on the stack for its closer.
            }
            else if (stack.Count == 0 || stack.Pop() != opener)
            {
                return false; // A closer must match the most recent unclosed opener.
            }
        }
        return stack.Count == 0; // Anything left was never closed.
    }

    public static void Main()
    {
        Console.WriteLine(IsValid("([]){}")); // True
        Console.WriteLine(IsValid("([)]")); // False
        Console.WriteLine(IsValid("((")); // False
        Console.WriteLine(IsValid("]")); // False
    }
}

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

public class Solution {
    // Each closing bracket and the opener it must match.
    static final Map<Character, Character> PAIRS = Map.of(')', '(', ']', '[', '}', '{');

    // Whether every bracket in s is closed by the same type, in the right order.
    static boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char ch : s.toCharArray()) {
            Character opener = PAIRS.get(ch);
            if (opener == null) {
                stack.push(ch); // An opener waits on the stack for its closer.
            } else if (stack.isEmpty() || !stack.pop().equals(opener)) {
                return false; // A closer must match the most recent unclosed opener.
            }
        }
        return stack.isEmpty(); // Anything left was never closed.
    }

    public static void main(String[] args) {
        System.out.println(isValid("([]){}")); // true
        System.out.println(isValid("([)]")); // false
        System.out.println(isValid("((")); // false
        System.out.println(isValid("]")); // false
    }
}

OPERATORS = {"+", "-", "*", "/"}


def eval_rpn(tokens: list[str]) -> int:
    """Evaluates an expression in Reverse Polish Notation, where each operator
    comes after its two operands. Division truncates toward zero."""
    stack: list[int] = []
    for token in tokens:
        if token in OPERATORS:
            # The right operand was pushed last, so it comes off first.
            b = stack.pop()
            a = stack.pop()
            stack.append(apply(a, b, token))
        else:
            stack.append(int(token))
    return stack.pop()  # A valid expression leaves exactly one value.


def apply(a: int, b: int, op: str) -> int:
    if op == "+":
        return a + b
    if op == "-":
        return a - b
    if op == "*":
        return a * b
    return int(a / b)  # Not a // b, which rounds down: -7 // 2 is -4, not -3.


if __name__ == "__main__":
    print(eval_rpn(["2", "1", "+", "3", "*"]))  # 9
    print(eval_rpn(["4", "13", "5", "/", "+"]))  # 6
    print(eval_rpn(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]))  # 22
    print(eval_rpn(["-7", "2", "/"]))  # -3

const OPERATORS = new Set(["+", "-", "*", "/"]);

// Evaluates an expression in Reverse Polish Notation, where each operator
// comes after its two operands. Division truncates toward zero.
export function evalRPN(tokens: string[]): number {
  const stack: number[] = [];
  for (const token of tokens) {
    if (OPERATORS.has(token)) {
      // The right operand was pushed last, so it comes off first.
      const b = stack.pop()!;
      const a = stack.pop()!;
      stack.push(apply(a, b, token));
    } else {
      stack.push(Number(token));
    }
  }
  return stack.pop()!; // A valid expression leaves exactly one value.
}

function apply(a: number, b: number, op: string): number {
  switch (op) {
    case "+":
      return a + b;
    case "-":
      return a - b;
    case "*":
      return a * b;
    default:
      return Math.trunc(a / b); // Not Math.floor, which rounds down: -3.5 would become -4.
  }
}

console.log(evalRPN(["2", "1", "+", "3", "*"])); // 9
console.log(evalRPN(["4", "13", "5", "/", "+"])); // 6
console.log(evalRPN(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"])); // 22
console.log(evalRPN(["-7", "2", "/"])); // -3

package main

import (
	"fmt"
	"strconv"
)

var operators = map[string]bool{"+": true, "-": true, "*": true, "/": true}

// evalRPN evaluates an expression in Reverse Polish Notation, where each
// operator comes after its two operands. Division truncates toward zero.
func evalRPN(tokens []string) int {
	stack := []int{}
	for _, token := range tokens {
		if operators[token] {
			// The right operand was pushed last, so it comes off first.
			b, a := stack[len(stack)-1], stack[len(stack)-2]
			stack = stack[:len(stack)-2]
			stack = append(stack, apply(a, b, token))
		} else {
			n, _ := strconv.Atoi(token) // Every other token is a valid integer.
			stack = append(stack, n)
		}
	}
	return stack[len(stack)-1] // A valid expression leaves exactly one value.
}

func apply(a, b int, op string) int {
	switch op {
	case "+":
		return a + b
	case "-":
		return a - b
	case "*":
		return a * b
	default:
		return a / b // Integer division in Go already truncates toward zero.
	}
}

func main() {
	fmt.Println(evalRPN([]string{"2", "1", "+", "3", "*"}))                                             // 9
	fmt.Println(evalRPN([]string{"4", "13", "5", "/", "+"}))                                            // 6
	fmt.Println(evalRPN([]string{"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"})) // 22
	fmt.Println(evalRPN([]string{"-7", "2", "/"}))                                                      // -3
}

using System;
using System.Collections.Generic;

public class Solution
{
    static readonly HashSet<string> Operators = new() { "+", "-", "*", "/" };

    // Evaluates an expression in Reverse Polish Notation, where each operator
    // comes after its two operands. Division truncates toward zero.
    public static int EvalRpn(string[] tokens)
    {
        var stack = new Stack<int>();
        foreach (string token in tokens)
        {
            if (Operators.Contains(token))
            {
                // The right operand was pushed last, so it comes off first.
                int b = stack.Pop();
                int a = stack.Pop();
                stack.Push(Apply(a, b, token));
            }
            else
            {
                stack.Push(int.Parse(token));
            }
        }
        return stack.Pop(); // A valid expression leaves exactly one value.
    }

    static int Apply(int a, int b, string op) => op switch
    {
        "+" => a + b,
        "-" => a - b,
        "*" => a * b,
        _ => a / b, // Integer division in C# already truncates toward zero.
    };

    public static void Main()
    {
        Console.WriteLine(EvalRpn(new[] { "2", "1", "+", "3", "*" })); // 9
        Console.WriteLine(EvalRpn(new[] { "4", "13", "5", "/", "+" })); // 6
        Console.WriteLine(EvalRpn(new[] { "10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+" })); // 22
        Console.WriteLine(EvalRpn(new[] { "-7", "2", "/" })); // -3
    }
}

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Set;

public class Solution {
    static final Set<String> OPERATORS = Set.of("+", "-", "*", "/");

    // Evaluates an expression in Reverse Polish Notation, where each operator
    // comes after its two operands. Division truncates toward zero.
    static int evalRPN(String[] tokens) {
        Deque<Integer> stack = new ArrayDeque<>();
        for (String token : tokens) {
            if (OPERATORS.contains(token)) {
                // The right operand was pushed last, so it comes off first.
                int b = stack.pop();
                int a = stack.pop();
                stack.push(apply(a, b, token));
            } else {
                stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop(); // A valid expression leaves exactly one value.
    }

    static int apply(int a, int b, String op) {
        return switch (op) {
            case "+" -> a + b;
            case "-" -> a - b;
            case "*" -> a * b;
            default -> a / b; // Integer division in Java already truncates toward zero.
        };
    }

    public static void main(String[] args) {
        System.out.println(evalRPN(new String[] {"2", "1", "+", "3", "*"})); // 9
        System.out.println(evalRPN(new String[] {"4", "13", "5", "/", "+"})); // 6
        System.out.println(evalRPN(new String[] {"10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"})); // 22
        System.out.println(evalRPN(new String[] {"-7", "2", "/"})); // -3
    }
}