How would I go about using a parenthesized string to create a binary tree? Would a possible solution also make use of a stack in some way?
Example: the string: "(A(B)(C))" should create a tree that looks like the following:
A
/ \
B C
Something else to note is that () would be used to denote that a node would not have a child at that position. To further illustrate, "(A()(B))",
denotes that the node "A" would have no left child but would have a right child, named "B".
Assuming your input string is well-formed, you can indeed use stacks to build a tree structure. I used a stack of flags which runs alongside a stack of parent nodes to keep track of whether a left child for each parent has been handled (either left empty or assigned a child). This flag stack is also modified for empty parenthesis signifying an empty child.
using System;
using System.Collections.Generic;
class MainClass
{
public static void Main(string[] args)
{
string[] tests = {
"()",
"(A(B(C)))",
"(A(B()))",
"(A()(B))",
"(A()(B()))",
"(A()(B()()))",
"(A()(B(C)))",
"(A()(B()(C)))",
"(A(B(E)(F))(C(G)(H()(I))))",
};
foreach (string test in tests)
{
Console.WriteLine(test + "\n");
PrintTree(ParseTree(test));
Console.WriteLine(new String('_', 26) + "\n");
}
}
static Node ParseTree(string str)
{
var parent = new Stack<Node>();
var hasLeft = new Stack<bool>();
Node root = null;
for (int i = 0; i < str.Length; i++)
{
if (str[i] == '(')
{
if (str[++i] == ')') // "()" substring
{
if (hasLeft.Count == 0)
{
return null; // empty tree
}
// mark left child as handled for this node
hasLeft.Pop();
hasLeft.Push(true);
}
else // str[i] is a node; connect it to its parent
{
var node = new Node(str[i]);
if (parent.Count > 0)
{
if (hasLeft.Peek())
{
parent.Peek().right = node;
}
else // left child hasn't been handled yet
{
parent.Peek().left = node;
hasLeft.Pop();
hasLeft.Push(true);
}
}
else // no parent found; make this the root
{
root = node;
}
parent.Push(node);
hasLeft.Push(false);
}
}
else if (str[i] == ')')
{
parent.Pop();
hasLeft.Pop();
}
}
return root;
}
static void PrintTree(Node root, int depth = 0)
{
if (root != null)
{
Console.WriteLine(new String(' ', depth) + root.val);
if (root.left != null)
{
Console.WriteLine(new String(' ', depth) + " ──L─┐");
PrintTree(root.left, depth + 6);
}
if (root.right != null)
{
Console.WriteLine(new String(' ', depth) + " ──R─┐");
PrintTree(root.right, depth + 6);
}
}
}
}
class Node
{
public Node left;
public Node right;
public char val;
public Node(char val)
{
this.val = val;
}
}
Partial output:
(A()(B(C)))
A
──R─┐
B
──L─┐
C
__________________________
(A()(B()(C)))
A
──R─┐
B
──R─┐
C
__________________________
(A(B(E)(F))(C(G)(H()(I))))
A
──L─┐
B
──L─┐
E
──R─┐
F
──R─┐
C
──L─┐
G
──R─┐
H
──R─┐
I
One way to do it would be to create a static Parse method on the Node class that returns a Node based on an input string. The logic would be something like:
Node.Parse using the "Left" stringNode.Parse using the "Right" stringI also added some code to print out the tree in a sort of rudimentary way, so you can see what the values of each node looks like.
For example the Node class below implements a Parse method that will create nodes based on your string input:
public class Node
{
public string Name { get; set; }
public Node Left { get; set; }
public Node Right { get; set; }
/// <summary>
/// Creates a Node based on a valid input string: "(Name(Left)(Right))",
/// where 'Left' and 'Right' are empty or valid strings like above.
/// </summary>
/// <param name="input">Input string to parse</param>
/// <returns>Root node of the tree</returns>
public static Node Parse(string input)
{
input = input?.Trim();
// Some light validation
if (string.IsNullOrEmpty(input) || input == "()") return null;
if (input.Length < 7)
{
throw new ArgumentException(
$"input '{input}' is not long enough to represent a valid " +
"node. The minimum string length is 7 characters: (A()())");
}
if (!input.StartsWith("(") || !input.EndsWith(")"))
{
throw new FormatException(
$"input '{input}' must be surrounded by parenthesis");
}
// Remove outer parenthesis so input is now: "Name(Left)(Right)"
input = input.Substring(1, input.Length - 2);
// Find the name and start of left node
var leftNodeStart = input.IndexOf('(', 1);
var root = new Node {Name = input.Substring(0, leftNodeStart)};
// Remove name so input is now just: "(Left)(Right)"
input = input.Substring(leftNodeStart);
// Find the end of the left node by counting opening and closing parenthesis
// When the opening count is equal to the closing count, we have our Left set
var openParenthesisCount = 0;
var closeParenthesisCount = 0;
var leftNodeLength = 0;
for (int i = 0; i < input.Length - 1; i++)
{
if (input[i] == '(') openParenthesisCount++;
else if (input[i] == ')') closeParenthesisCount++;
if (openParenthesisCount == closeParenthesisCount)
{
leftNodeLength = i + 1;
break;
}
}
// Recursive calls to create Left and Right children
root.Left = Node.Parse(input.Substring(0, leftNodeLength));
root.Right = Node.Parse(input.Substring(leftNodeLength));
return root;
}
public void Print()
{
PrintTree();
}
private static class Connector
{
public const string Empty = " ";
public const string Single = "╚═";
public const string Double = "╠═";
public const string Extension = "║";
}
private static class Position
{
public const string Empty = "";
public const string Left = "Left : ";
public const string Right = "Right: ";
}
private void PrintTree(string indent = "", string position = Position.Empty,
bool extendParentConnector = false, string connector = Connector.Empty)
{
// Extend the parent's connector if necessary by
// adding a "║" under the parent node's connector
if (extendParentConnector && indent.Length > position.Length + 2)
{
var replaceIndex = indent.Length - position.Length - 2;
indent = indent.Remove(replaceIndex, 1)
.Insert(replaceIndex, Connector.Extension);
}
Console.ForegroundColor = ConsoleColor.DarkMagenta;
Console.Write(indent + connector);
Console.ForegroundColor = position == Position.Left
? ConsoleColor.DarkCyan
: ConsoleColor.DarkYellow;
Console.Write(position);
Console.BackgroundColor = ConsoleColor.DarkGray;
Console.ForegroundColor = ConsoleColor.DarkBlue;
Console.WriteLine($" {Name} ");
Console.ResetColor();
var nextIndent = indent + new string(' ', position.Length + 2);
var extendParent = connector == Connector.Double;
Left?.PrintTree(nextIndent, Position.Left, extendParent,
Right == null ? Connector.Single : Connector.Double);
Right?.PrintTree(nextIndent, Position.Right, extendParent, Connector.Single);
}
}
In use, this would look like:
static void Main(string[] args)
{
var nodeString = "(A(B(C(L()())(M()()))(D()()))(E(F(G(H()())())(I()(J()())))(K()())))";
var rootNode = Node.Parse(nodeString);
rootNode.Print();
Console.Write("\nDone! Press any key to exit...");
Console.ReadKey();
}
And the output looks like:
