// 1039: Stack Using Vec
// Vec's push/pop operate at the end — perfect LIFO stack
/// A simple stack wrapper around Vec
struct Stack<T> {
items: Vec<T>,
}
impl<T> Stack<T> {
fn new() -> Self {
Stack { items: Vec::new() }
}
fn push(&mut self, value: T) {
self.items.push(value);
}
fn pop(&mut self) -> Option<T> {
self.items.pop()
}
fn peek(&self) -> Option<&T> {
self.items.last()
}
fn is_empty(&self) -> bool {
self.items.is_empty()
}
fn size(&self) -> usize {
self.items.len()
}
}
fn basic_stack() {
let mut s = Stack::new();
assert!(s.is_empty());
s.push(10);
s.push(20);
s.push(30);
assert_eq!(s.size(), 3);
assert_eq!(s.peek(), Some(&30));
assert_eq!(s.pop(), Some(30));
assert_eq!(s.pop(), Some(20));
assert_eq!(s.pop(), Some(10));
assert_eq!(s.pop(), None);
}
/// Vec directly as a stack (no wrapper needed)
fn vec_as_stack() {
let mut stack: Vec<i32> = Vec::new();
stack.push(1);
stack.push(2);
stack.push(3);
assert_eq!(stack.last(), Some(&3));
assert_eq!(stack.pop(), Some(3));
assert_eq!(stack.len(), 2);
}
/// RPN (Reverse Polish Notation) calculator using a stack
fn eval_rpn(tokens: &[&str]) -> i32 {
let mut stack: Vec<i32> = Vec::new();
for &token in tokens {
match token {
"+" | "-" | "*" => {
let b = stack.pop().unwrap();
let a = stack.pop().unwrap();
let result = match token {
"+" => a + b,
"-" => a - b,
"*" => a * b,
_ => unreachable!(),
};
stack.push(result);
}
n => stack.push(n.parse().unwrap()),
}
}
stack.pop().unwrap()
}
fn eval_test() {
// 3 4 + 2 * = (3 + 4) * 2 = 14
assert_eq!(eval_rpn(&["3", "4", "+", "2", "*"]), 14);
// 5 1 2 + 4 * + 3 - = 5 + (1+2)*4 - 3 = 14
assert_eq!(eval_rpn(&["5", "1", "2", "+", "4", "*", "+", "3", "-"]), 14);
}
/// Balanced parentheses checker
fn is_balanced(s: &str) -> bool {
let mut stack = Vec::new();
for ch in s.chars() {
match ch {
'(' | '[' | '{' => stack.push(ch),
')' => if stack.pop() != Some('(') { return false; },
']' => if stack.pop() != Some('[') { return false; },
'}' => if stack.pop() != Some('{') { return false; },
_ => {}
}
}
stack.is_empty()
}
fn balance_test() {
assert!(is_balanced("({[]})"));
assert!(is_balanced(""));
assert!(!is_balanced("({[})"));
assert!(!is_balanced("(("));
}
fn main() {
basic_stack();
vec_as_stack();
eval_test();
balance_test();
println!("✓ All tests passed");
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn test_basic() { basic_stack(); }
#[test]
fn test_vec_stack() { vec_as_stack(); }
#[test]
fn test_rpn() { eval_test(); }
#[test]
fn test_balanced() { balance_test(); }
}
(* 1039: Stack Using List *)
(* OCaml's list IS a stack — cons and pattern match are push and pop *)
(* Approach 1: List as a stack (idiomatic OCaml) *)
let list_stack () =
let stack = [] in
let stack = 1 :: stack in
let stack = 2 :: stack in
let stack = 3 :: stack in
assert (List.hd stack = 3); (* top *)
let (top, stack) = (List.hd stack, List.tl stack) in
assert (top = 3);
assert (List.hd stack = 2)
(* Approach 2: Module-based stack *)
module Stack : sig
type 'a t
val empty : 'a t
val push : 'a -> 'a t -> 'a t
val pop : 'a t -> ('a * 'a t) option
val peek : 'a t -> 'a option
val is_empty : 'a t -> bool
val size : 'a t -> int
val to_list : 'a t -> 'a list
end = struct
type 'a t = { items: 'a list; size: int }
let empty = { items = []; size = 0 }
let push x s = { items = x :: s.items; size = s.size + 1 }
let pop s = match s.items with
| [] -> None
| x :: xs -> Some (x, { items = xs; size = s.size - 1 })
let peek s = match s.items with
| [] -> None
| x :: _ -> Some x
let is_empty s = s.items = []
let size s = s.size
let to_list s = s.items
end
let module_stack () =
let s = Stack.empty in
let s = Stack.push 10 s in
let s = Stack.push 20 s in
let s = Stack.push 30 s in
assert (Stack.size s = 3);
assert (Stack.peek s = Some 30);
let (v, s) = Option.get (Stack.pop s) in
assert (v = 30);
assert (Stack.peek s = Some 20)
(* Approach 3: Stack-based expression evaluator *)
let eval_rpn tokens =
let stack = List.fold_left (fun stack token ->
match token with
| "+" | "-" | "*" ->
let b = List.hd stack in
let a = List.hd (List.tl stack) in
let rest = List.tl (List.tl stack) in
let result = match token with
| "+" -> a + b
| "-" -> a - b
| "*" -> a * b
| _ -> failwith "impossible"
in
result :: rest
| n -> int_of_string n :: stack
) [] tokens in
List.hd stack
let eval_test () =
(* 3 4 + 2 * = (3 + 4) * 2 = 14 *)
let result = eval_rpn ["3"; "4"; "+"; "2"; "*"] in
assert (result = 14)
let () =
list_stack ();
module_stack ();
eval_test ();
Printf.printf "✓ All tests passed\n"