well formed string with special characters c#

Question

My program needs to output "true" if the string in the input is well formed with parantheses, brackets or curly brackets

Examples :

Input : {([]){}()} ouput : true

Input : {L{}[{[a]}R]{2}} output : true

Input : {(}) output : false

Input : ][ output : false

The trick is the alignment, not counting opened and closed special character.

Is there a Linq or conditional solution to that?

Answer 1

As mentioned in the comments, you can use a stack to check whether the closing parenthesis matches the last one that was open.

bool IsSequenceValid(string value)
{
    var openParenthesisStack = new Stack<char>();
    var isValid = true;

    using (var character = value.GetEnumerator())
        while (isValid && character.MoveNext())
            switch (character.Current)
            {
                case '(':
                case '[':
                case '{':
                    openParenthesisStack.Push(character.Current);
                    break;

                case ')':
                    if (openParenthesisStack.Count == 0 || openParenthesisStack.Pop() != '(')
                        isValid = false;
                    break;

                case ']':
                    if (openParenthesisStack.Count == 0 || openParenthesisStack.Pop() != '[')
                        isValid = false;
                    break;

                case '}':
                    if (openParenthesisStack.Count == 0 || openParenthesisStack.Pop() != '{')
                        isValid = false;
                    break;
            }

    return isValid && openParenthesisStack.Count == 0;
}

Answer 2

We want to make sure that the () and [] and {} are used correctly.

We use a stack. When a range opener is observed, it is placed inside the stack.

When an end separator is reached, the top element of the stack is compared. If the stack is empty, this range terminator does not match any opener and the string is invalid.

If the stack is not empty, the element is removed from the top of the stack, and if its type is the same as the type of range terminator, we continue to scroll.

After reaching the end of the string, the stack must be empty, otherwise the range is not closed and the string is invalid.

bool ValidBraces(string infix)
{
    bool valid = true;
    int i = 0;
    Stack<char> symbls = new Stack<char>();

    while (i < infix.Length)
    {
       if (infix[i] == '(' || infix[i] == '[' || infix[i] == '{')
           symbls.Push(infix[i]);

       if (infix[i] == ')' || infix[i] == ']' || infix[i] == '}')
          if (symbls.Count == 0)
          {
             valid = false;
             break;
          }
          else
          {
             char ch = symbls.Pop();
             switch(ch)
             {
                case '(':
                  if (')' != infix[i])
                  {
                     valid = false;
                     break;
                  }
                  break;
                case '[':
                  if (']' != infix[i])
                  {
                     valid = false;
                     break;
                  }
                  break;
                case '{':
                  if ('}' != infix[i])
                  {
                     valid = false;
                     break;
                  }
                  break;
              }
         }

         i++;
    }

    if (symbls.Count > 0)
        valid = false;

    return valid;
}

test code

string infix = "{L{}[{[a]}R]{2}}";
bool validate = ValidBraces(infix);
MessageBox.Show(validate.ToString());

infix = "][";
validate = ValidBraces(infix);
MessageBox.Show(validate.ToString());