Reverse a string / queue using a stack; check balanced parentheses

Easy

Problem

Three warm-ups that show how a stack works: reverse a string with a stack; reverse a queue with a stack; check that a string of brackets is balanced.

Example 1

Input:  reverse "stack"
Output: "kcats"

Example 2

Input:  balanced? "[()]{}"
Output: true

Also asked as: Reverse a String using Stack · Reverse a Queue using recursion · Check the expression has valid or Balanced parenthesis or not

Test cases

Case 1

Input:    "[()]{}"
Expected: true

Case 2

Input:    "([)]"
Expected: false

Case 3

Input:    "(("
Expected: false

Case 4

Input:    ")"
Expected: false

Case 5

Input:    ""
Expected: true

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Stack fundamentals

Time O(n)Space O(n)

Push all characters/elements and pop them to reverse. For balanced parentheses, push openers and match each closer against the stack top. To reverse a queue recursively: dequeue the front, recurse, then enqueue the saved front at the back.

const reverseWithStack = (s) => { const st = [...s]; let r = ''; while (st.length) r += st.pop(); return r; };
function isBalanced(s) {
const pair = { ')': '(', ']': '[', '}': '{' }, st = [];
for (const c of s) {
if ('([{'.includes(c)) st.push(c);
else if (st.pop() !== pair[c]) return false;
}
return st.length === 0;
}
function reverseQueue(q) {
if (q.length === 0) return;
const front = q.shift();
reverseQueue(q);
q.push(front);
}