How to find the matching pair of braces in a strin

问题:

Suppose I have a string "(paid for) + (8 working hours) + (company rules)" . Now I want to check whether this complete string is surrounded with parentheses or not. Basically I want to check if the string is like this or not : "((paid for) + (8 working hours) + (company rules))". If it is already surrounded with parentheses, then I will leave it as it is, otherwise I will apply parentheses to the complete string so that the ouput is : "((paid for) + (8 working hours) + (company rules))" . By counting the number of parentheses, I am not able to solve this problem.

Can anyone please suggest a solution?

回答1:

The Stack is a good idea, but as you want to see if the complete string is surrounded with parens, i suggest you put the index of the encountered opening paren on the Stack. That way, each time you pop an item on the stack, check if it's 0, meaning the opening paren that corresponds to this closing paren was on the beginning of the string. The result of this check for the last closing paren will tell you if you need to add parens.

Example:

String s = "((paid for) + (8 working hours) + (company rules))";
var stack = new Stack<int>();
bool isSurroundedByParens = false;
for (int i = 0; i < s.Length; i++) {
    switch (s[i]) {
    case '(':
        stack.Push(i);
        isSurroundedByParens = false;
        break;
    case ')':
        int index = stack.Any() ? stack.Pop() : -1;
        isSurroundedByParens = (index == 0);
        break;
    default:
        isSurroundedByParens = false;
        break;
    }
}
if (!isSurroundedByParens) {
    // surround with parens
}

回答2:

use a stack.. as in when u find a ( bracket push it and when u see ) pop the stack.. Finally when the string is parsed completely the stack should be empty... This will ensure you that the brackets are not missing..

in your case if in between the stack becomes empty then there are no surrounding brackets for entire string

for example: for input string:

(paid for) + (8 working hours) + (company rules)

the first ( would be pushed and when it encounters the ) it will pop the stack, now check if there is more string to be parsed and stack is not empty. If stack is empty that means the entire string is not in bracket.

whereas for the string:

((paid for) + (8 working hours) + (company rules))

stack will not be empty untill the last ) appears.

Hope this helps...

回答3:

Tests

static void Main()
{
    Console.WriteLine("Expected: {0}, Is: {1}", false, IsSurrounded(""));
    Console.WriteLine("Expected: {0}, Is: {1}", false, IsSurrounded("("));
    Console.WriteLine("Expected: {0}, Is: {1}", false, IsSurrounded(")"));
    Console.WriteLine("Expected: {0}, Is: {1}", true, IsSurrounded("()"));
    Console.WriteLine("Expected: {0}, Is: {1}", false, IsSurrounded("(()"));
    Console.WriteLine("Expected: {0}, Is: {1}", false, IsSurrounded("())"));
    Console.WriteLine("Expected: {0}, Is: {1}", true, IsSurrounded("(.(..)..(..)..)"));
    Console.WriteLine("Expected: {0}, Is: {1}", false, IsSurrounded("(..)..(..)"));
    Console.WriteLine("Expected: {0}, Is: {1}", false, IsSurrounded("(..)..(..)..)"));
    Console.WriteLine("Expected: {0}, Is: {1}", false, IsSurrounded("(.(..)..(..)"));
}

---

Method

Very fast

• No stack
• No loop through entire string

If the first opening parenthesis has its closing counterpart, then the result can't be true. Same thing about last closing parenthesis.

static bool IsSurrounded(string text)
{
    if (text.Length < 2 || text.First() != '(' || text.Last() != ')')
        return false;

    for (var i = 1; i < text.Length - 1; i++)
    {
        if (text[i] == ')')
            return false;

        if (text[i] == '(')
            break;
    }

    for (var i = text.Length - 2; i > 0; i--)
    {
        if (text[i] == '(')
            return false;

        if (text[i] == ')')
            break;
    }

    return true;
}

---

Limitations

Should be not used when there are more recursive parentheses such as ((..)) + ((..))

回答4:

To ensure there are parenthesis you could simply add them:

text = "(" + text + ")"

Otherwise the suggested stack by Botz3000:

string text = "(paid for)";

Stack<int> parenthesis = new Stack<int>();
int last = 0;

for (int i = 0; i < text.Length; i++)
{
    if (text[i] == '(')
        parenthesis.Push(i);
    else if (text[i] == ')')
    {
        last = parenthesis.Pop();
    }
}

if (last == 0)
{
    // The matching parenthesis was the first letter.
}

回答5:

You can check the right number of parenthesises by using something like a stack. Count up for each opening and count down for each closing brace. The same number of opening and closing braces means it matches. If you ever encounter a closing brace while your count is zero, that's a mismatch. If you want to know if your string is completely enclosed by paranthesises, check if all of them match, then check if your string starts with one.

static void BraceMatch(string text)
{
  int level = 0;

  foreach (char c in text)
  {
    if (c == '(')
    {
      // opening brace detected
      level++;
    }

    if (c == ')')
    {
      level--;

      if (level < 0)
      {
        // closing brace detected, without a corresponding opening brace
        throw new ApplicationException("Opening brace missing.");
      }
    }
  }

  if (level > 0)
  {
    // more open than closing braces
    throw new ApplicationException("Closing brace missing.");
  }
}