Задача. Реверс подстрок между скобками

Задача. Дана строка, состоящая из строчных английских букв и скобок.

Сделайте реверс подстроки в каждой паре скобок, начиная с самой внутренней. Получившуюся строку верните без скобок.

Примеры:

1. S = "(abcd)"
Output: "dcba"

2. S = "(u(love)i)"
Output: "iloveu"

Разбор

Для начала создадим подфункцию для реверса произвольной строки. Ключом к быстрому решению будет использование стэка.

Идея заключается в том, чтобы сохранять позиции открывающихся скобок в стеке. Тогда для каждой закрывающейся скобки мы берем элемент из стека (позиция последней открывающейся скобки) и делаем реверс полученной подстроки.

Реализация

static string ReverseParentheses(string s) {
	var stack = new Stack<int>();
	StringBuilder res = new StringBuilder();
	
	for (int i = 0; i < s.Length; i++) {
	    if (s[i] == '(') {
		    // сохраняем позицию открывающейся скобки
		    stack.Push(res.Length);
	    } else if (s[i] == ')') {
		    // берем позицию последней открывающейся скобки
		    int start = stack.Pop();

		    // делаем реверс подстроки
		    Reverse(res, start, res.Length - 1);
	    }
	    else {
		    res.Append(s[i]);
	    }
	}

	return res.ToString();
}

https://gist.github.com/unilecs/cea7e9c58a124368aac03438d6fadc02

Play-test

https://dotnetfiddle.net/Yet6dI