Introduction

A well-formed permutation of parentheses, often referred to as a "valid permutation," is a sequence that is correctly balanced and properly nested. Valid parentheses are a common feature in various computational domains, including mathematical expressions, programming languages, and data structures like trees.

Problem Definition

The problem of determining whether a sequence of parentheses is valid can be stated as follows: Given a string consisting only of the characters `(` and `)`, determine if it is a valid permutation. A valid sequence must satisfy the following conditions:

1. The number of opening parentheses `(` must equal the number of closing parentheses `)`.
2. At any point in the string, the number of closing parentheses should not exceed the number of opening parentheses.

Examples

Example 1

Input: `(()())`
Output: Valid

Example 2

Input: `())(`
Output: Invalid
Explanation: The third closing parenthesis does not match an opening one.

Example 3

Input: `((()))`
Output: Valid

Algorithm

A common approach to solving this problem is using a stack data structure. The stack helps efficiently manage the opening parentheses that need matching.

Step-by-Step Solution

1. Initialize an empty stack.
2. Iterate through each character in the string:
   • If the character is an `(`, push it onto the stack.
   • If it is a `)`, check if the stack is empty:
     • If the stack is not empty, pop an element from the stack.
     • If the stack is empty, the sequence is invalid.
3. After processing all characters, if the stack is empty, the sequence is valid. Otherwise, it is invalid.

Complexity

• Time Complexity: $O(n)$, where $n$ is the length of the string, because each character is processed once.
• Space Complexity: $O(n)$, as in the worst case, all characters could be opening parentheses.

Code Example

• Compilers: Ensuring that parentheses in expressions are balanced.
• Data Parsing: Validating structured text formats like JSON and XML.
• Mathematical Expressions: Ensuring correctness in complex expressions involving nested functions or operations.