Implement stack and interval algorithms with tests

Implement three coding tasks and design your own unit tests for each.

1. Validate Bracket String with a Stack

• Input: a string s containing only '(', ')', '[', ']', '{', '}'.
• Output: return true if brackets are correctly matched and nested; otherwise false.
• Constraints: O(n) time, O(n) auxiliary space; do not modify the input.
• Edge cases to consider: empty string; strings starting with a closing bracket; long runs of the same bracket; deeply nested pairs.

2. Merge Intervals with Open/Closed Endpoints

• Input: a list of intervals, each represented as (start: int, end: int, leftClosed: bool, rightClosed: bool) with start <= end.
• Task: return the union of the intervals as a minimal, sorted list after merging any that overlap or “touch” under endpoint semantics. Two intervals [a,b] and [c,d] should merge if b > c, or if b == c and (the first is rightClosed OR the second is leftClosed). For example, [1,3] and [3,

5. merge to [1, 5), but [1,
6. and (3,5] remain separate.

• Constraints: O(n log n) due to sorting; O(n) extra space.
• Edge cases: zero-length intervals like [3,3]; mixed open/closed boundaries; duplicate intervals; very large lists.

3. Evaluate Arithmetic Expression Using Stacks

• Input: a string expr containing non-negative integers, '+', '-', ' ', '/', parentheses '()', spaces, and unary minus (e.g., "-3+5", "2 (-3+ 4)").
• Output: compute the integer result; division truncates toward zero.
• Constraints: O(n) time, O(n) space; handle whitespace and unary operators correctly; assume the expression is valid and the intermediate results fit in 32-bit signed integer range.
• Edge cases: multiple nested parentheses, consecutive operators with unary minus (e.g., "1+-2"), spaces in arbitrary places, long inputs.

Testing requirement: For each task, write comprehensive unit tests you design yourself (at least 6 per task) covering typical cases, boundary conditions, and tricky edge cases.