Trace through s = "a)b(c)d" step by step.
Index : a. Not a parenthesis. Skip.
Index : ). Stack is empty, so this is unmatched. Mark index .
Index : b. Skip.
Index : (. Push index onto the stack.
Index : c. Skip.
Index : ). Stack has index . Pop it. Matched pair.
Index : d. Skip.
Stack is now empty. Unmatched set: {1}. Build the result skipping index : "ab(c)d".
time for passes. space for the stack and result string.