Стеки на Си

[majuw]

Здраствуйте.
В строке записан текст что сбалансированный за круглыми скобками:
<текст>::=<пусто>|<елемент><текст >
<елемент>::=<буква>|(<текст>)
Надо для каждой пары скобок открывающиеся и закрывающиеся напечатать номера их позиций в тексте, упорядочив пары номеров по возрастанию номеров позиций скобок видкриваються.Наприклад, для текста А + (45-F (X)*(B-C)) нужно напечатать 3 17;8 10;12 16.

[majuw]

Что никто не может помочь?

[Abstraction]

На уровне концепции: завести список пар позиций, как глобальный объект. Функция подсчёта скобок принимает указатель на позицию в строке, идёт по строке, пока не найдёт закрывающую, открывающую скобку или конец строки.
Если находит закрывающую скобку - возвращает то, до какой позиции она дошла.
Если находит открывающую скобку - запоминает её и вызывает сама себя начиная со следующего символа, принимает возвращённое значение, проверяет, что там закрывающая скобка и заносит эту пару скобок в список.
Если находит конец строки - возвращает то, до какой позиции на дошла.

После вызова этой функции с аргументом "начало строки", все пары скобок окажутся занесены в список, но в неправильном порядке. Следует упорядочить список (хотите - превратив в массив, хотите - так) по возрастанию "номеров позиций скобок видкриваються"... видимо, по первым элементам сохранённых в списке пар.

[rrrFer]

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

Держи на прологе без сортировки:

p([], _, _, R, R):-!.
p([H|T], N, Tmp, L, R):-
	NN is N + 1, (
		[H] = "(", !, p(T, NN, [N|Tmp], L, R)
		; [H] = ")", !, Tmp = [VT|TTmp], p(T, NN, TTmp, [pair(VT, N)|L], R)
		; p(T, NN, Tmp, L, R)
	).

на си оно примерно также должно выглядеть.

[debug] [4] ?- p("А+(45-F(X)*(B-C))", 1, [], [], R).
R = [pair(3, 17), pair(12, 16), pair(8, 10)].

На уровне концепции: завести список пар позиций, как глобальный объект.

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

[Abstraction]

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

Моё решение задействует системный стек (рекурсивные вызовы), так что разные активации функции должны иметь доступ к общему объекту для накопления результата, а замыканий в C++ нет.

[rrrFer]

#include <iostream>
#include <list>
#include <algorithm>

typedef std::pair<int, int> t_pair;

void f(std::string &str, std::list<t_pair> &res) {
	std::list<int> tmp;
	const int n = str.length();
	for (int idx = 0; idx < n; ++idx) {
		if ('(' == str[idx])
			tmp.push_back(idx);
		if (')' == str[idx]) {
			res.push_back(std::make_pair(tmp.back(), idx));
			tmp.pop_back();
		}
	}
}

int main() {
	std::string str = "А+(45-F(X)*(B-C))";
	std::list<t_pair> t;
	f(str, t);

	for (auto val : t) 
		std::cout << "pair(" << val.first << "," << val.second << ")" << std::endl;
}

Если очень сильно нужны стеки - замени список tmp из функции на стек, он именно так и исопльзуется, ну и отсортируешь список сам )
std::sort поможет, наверное.
ЗЫ. алгоритм тот же что и на прологе.

а замыканий в C++ нет.

ты о лямбдах? - они есть, но причем тут они?

----------
ЗЫ. некропост, но ТС попросил в личке

[Abstraction]

ты о лямбдах? - они есть, но причем тут они?

Нет, я о том, что рекурсивная функция, накапливающая результат при каждом вызове, может это делать одним из четырёх способов: или по всей цепочке вызовов в качестве одного из аргументов таскается (передаваемый по ссылке) объект-аккумулятор, или используется возвращаемое значение, или модифицируется глобальный объект, или модифицируется объект, не являющийся глобальным, но существующий на протяжении всех вызовов и доступный при всех вызовах. К примеру, в Python:

def sum_all(a, b):
  sum = 0
  def recursive(c,d):
    if(c > d):
      return sum
    sum = sum + c
    return recursive(c+1, d)
  return recursive(a,b)

Обратите внимание, что sum - локальная переменная, входящая в замыкание для recursive: все вызовы recursive будут модифицировать одну и ту же sum. Вот этот четвёртый вариант до C++11 недоступен точно, а первый и второй варианты в этой задаче не очень удобны.

ЗЫ. некропост, но ТС попросил в личке

Ох. Вот почему люди не хотят использовать форум? В этих личных сообщениях же чёрт ногу сломит при попытке воссоздать ход беседы хотя бы на десять сообщений назад, и лимит на сообщение - жалкие 4000 символов.