Как в SQL построить таблицу, описывающую бинарное дерево по строке, описывающей его с помощью скобок?

Question

[Alex Serov]

Делаю лабу по MS SQL, нужно написать какую-нибудь табличную многооператорную функцию.
Придумал себе задачку: из строки вида 'one (two (three (four ( ) five ( )))) (six ( ))', которая представляет бинарное дерево, в узлах которого находятся строки, построить таблицу.
Хочу получить таблицу вида

item parent level

one NULL 0
two one 1
six one 1
three two 2

и так далее.

Как подступить к решению? Вопросы вызывает то, как пользоваться SQL.

Comments

[Дмитрий Беляев]

Я Вас правильно понимаю, что вы это хотите реализовать на чистом SQL?
То есть, делаем некотурую процедуру, которая на запрос типа:
CALL your_procedure('target_table', 'one (two (three (four ( ) five ( )))) (six ( ))');
генерит Вам в target_table развертывание данного би-дерева

Answer 1

[Alex Serov]

--3) многооператорная табличная функция
-- построить бинарное дерево из строки
IF OBJECT_ID (N'dbo.BuildBinaryTree') IS NOT NULL
	DROP FUNCTION dbo.BuildBinaryTree
GO
CREATE FUNCTION dbo.BuildBinaryTree(@TreeStr nvarchar(max))
RETURNS @Tree table (ItemID int NOT NULL PRIMARY KEY, Name nvarchar(max) NOT NULL, ParentID int, Level int)
BEGIN
	DECLARE @curr_pos int;	-- итератор строки

	SET @curr_pos = CHARINDEX('(', @TreeStr, 0)

	IF @curr_pos = 0
	BEGIN
		INSERT @Tree (ItemID, Name, ParentID, Level) VALUES (1, LTRIM(RTRIM(@TreeStr)), NULL, 0)
		RETURN
	END
	ELSE
		INSERT @Tree (ItemID, Name, ParentID, Level) VALUES (1, LTRIM(RTRIM(SUBSTRING(@TreeStr, 1, @curr_pos - 1))), NULL, 0)

	DECLARE @curr_id int = 1
	DECLARE @curr_level int = 0

	WHILE (@curr_pos < LEN(@TreeStr))
	BEGIN
		DECLARE @nearest_open int = CHARINDEX('(', @TreeStr, @curr_pos)
		DECLARE @nearest_close int = CHARINDEX(')', @TreeStr, @curr_pos)

		IF @nearest_open < @nearest_close AND @nearest_open > 0
		BEGIN
			DECLARE @tmp_parent_id int
			SELECT @tmp_parent_id = MAX(ItemID) FROM @Tree WHERE Level = @curr_level

			SET @curr_pos = @nearest_open + 1
			SET @curr_level = @curr_level + 1
			SET @curr_id = @curr_id + 1

			DECLARE @tmp_nearest_open int = CHARINDEX('(', @TreeStr, @curr_pos);
			DECLARE @tmp_nearest_close int = CHARINDEX(')', @TreeStr, @curr_pos);

			IF @tmp_nearest_open < @tmp_nearest_close AND @tmp_nearest_open > 0
			BEGIN
				INSERT @Tree (ItemID, Name, ParentID, Level) VALUES (@curr_id, LTRIM(SUBSTRING(@TreeStr, @curr_pos, @tmp_nearest_open - @curr_pos)), @tmp_parent_id, @curr_level)
				SET @curr_pos = @tmp_nearest_open
			END
			ELSE
			BEGIN
				INSERT @Tree (ItemID, Name, ParentID, Level) VALUES (@curr_id, LTRIM(SUBSTRING(@TreeStr, @curr_pos, @tmp_nearest_close - @curr_pos)), @tmp_parent_id, @curr_level)
				SET @curr_pos = @tmp_nearest_close
			END
		END
		ELSE
		BEGIN
			SET @curr_pos = @nearest_close + 1
			SET @curr_level = @curr_level - 1
		END
	END

	RETURN
END
GO

SELECT * FROM dbo.BuildBinaryTree('hello')
SELECT * FROM dbo.BuildBinaryTree('hello (fisrt)')
SELECT * FROM dbo.BuildBinaryTree('hello(fisrt)(second)')
SELECT * FROM dbo.BuildBinaryTree('hello (fisrt (second))')
SELECT * FROM dbo.BuildBinaryTree('hello (fisrt (second  (third (fourth (fifth)))))')
SELECT * FROM dbo.BuildBinaryTree('hello (fisrt (second (third (fourth (fifth))))) (by)')
SELECT * FROM dbo.BuildBinaryTree('hello (world (my (pi (put)) (beer)) (by (pie (he)) (boy))) (hi)')
GO

Answer 2

[xmoonlight]

Вопросы вызывает то, как пользоваться SQL.

Видимо надо учить теоретическую часть и читать документацию.

Comments

[Alex Serov]

Просто два года я учился процедурному программированию, теперь сложно понять декларативные языки.

[xmoonlight]

Bosca Bosca: Однако, это - не отговорка и сути никак не меняет.