Efficient PHP Method to Reverse Substrings Within Parentheses

Common Problems in String Manipulation

String manipulation is a frequent requirement in programming. Handling parentheses and their nested structures, especially reversing substrings within parentheses, can be challenging. This article systematically introduces the problem description, algorithm design, and implementation details for reversing substrings inside every pair of parentheses.

Problem Description

Given a string containing regular characters and parentheses, the goal is to reverse the content inside each pair of parentheses. For example, input "(abc)de(fgh)" should output "cbadehgf". Clear rules and steps allow effective solving of this problem.

Input and Output Examples

The following examples help clarify the problem:

Input: "(xyz)(abc)"
Output: "zyxcba"

Input: "a(bc(de)fg)h"
Output: "ahgfedcba"

Approach

The stack data structure is most suitable here because it conveniently manages nested parentheses levels. The overall approach is:

• Initialize a stack and a variable for the current string.
• Iterate over each character in the string:
• When encountering a left parenthesis "(", push the current string onto the stack and clear the current string to start processing the content inside parentheses.
• When encountering a right parenthesis ")", reverse the current string and append it to the string popped from the stack, then update the current string.
• For other characters, directly append them to the current string.
• After iteration, the current string is the final result.

PHP Code Example

function reverseParentheses($s) {
    $stack = [];
    $currentString = "";
    for ($i = 0; $i < strlen($s); $i++) {
        $char = $s[$i];
        if ($char === '(') {
            array_push($stack, $currentString);
            $currentString = "";
        } elseif ($char === ')') {
            $currentString = strrev($currentString);
            if (!empty($stack)) {
                $currentString = array_pop($stack) . $currentString;
            }
        } else {
            $currentString .= $char;
        }
    }
    return $currentString;
}

// Example usage
echo reverseParentheses("(abc)de(fgh)"); // Outputs cbadehgf

Performance Analysis

The time complexity of this method is O(n), where n is the length of the input string, as each character is processed once. Space complexity is also O(n), used by the stack and the current string.

Conclusion

Using a stack to reverse substrings inside parentheses is an efficient solution for this problem. The approach and code provided here are practical references for similar string manipulation tasks in real projects, helping developers improve coding efficiency and problem-solving skills.