如何找到一串括号、花括号和方括号的有效性?

I recently came in contact with this interesting problem. You are given a string containing just the characters '(', ')', '{', '}', '[' and ']', for example, "[{()}]", you need to write a function which will check validity of such an input string, function may be like this:
bool isValid(char* s);
these brackets have to close in the correct order, for example "()" and "()[]{}" are all valid but "(]", "([)]" and "{{{{" are not!

我最近接触到了这个有趣的问题。你得到一个字符串，包含字符'('，')'，' '，'}'，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，'，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，' '，'这些方括号必须以正确的顺序关闭，例如“()”和“(){}”都是有效的，但是“()”、“([)]”和“{{”不是!

I came out with following O(n) time and O(n) space complexity solution, which works fine:

我提出了以下O(n)时间和O(n)空间复杂度的解决方案，这很好:

1. Maintain a stack of characters.
2. 维护一堆字符。
3. Whenever you find opening braces '(', '{' OR '[' push it on the stack.
4. 无论何时，当你发现打开的括号' ' ' '或' '[' '把它推到堆栈上。
5. Whenever you find closing braces ')', '}' OR ']' , check if top of stack is corresponding opening bracket, if yes, then pop the stack, else break the loop and return false.
6. 无论何时找到结束括号')'、'}'或']'，检查堆栈顶部是否相应的打开括号，如果是，则打开堆栈，否则断开循环并返回false。
7. Repeat steps 2 - 3 until end of the string.
8. 重复步骤2 - 3直到字符串结束。

This works, but can we optimize it for space, may be constant extra space, I understand that time complexity cannot be less than O(n) as we have to look at every character.

这是可行的，但是我们可以对空间进行优化，可以是常数的额外空间，我知道时间复杂度不能小于O(n)因为我们必须要看每个字符。

So my question is can we solve this problem in O(1) space?

所以我的问题是我们能否在O(1)空间中解决这个问题?

17 个解决方案

#1

Actually, there's a deterministic log-space algorithm due to Ritchie and Springsteel: http://dx.doi.org/10.1016/S0019-9958(72)90205-7 ( paywalled, sorry not online). Since we need log bits to index the string, this is space-optimal.

实际上，由于Ritchie和Springsteel，有一种确定性的逻辑空间算法:http://dx.doi.org/10.1016/S0019-9958(72)90205-7(付费墙，抱歉不在网上)。由于我们需要日志位来索引字符串，所以这是空间优化的。

---

If you're willing to accept one-sided error, then there's an algorithm that uses n polylog(n) time and polylog(n) space: http://www.eccc.uni-trier.de/report/2009/119/

如果你愿意接受片面的错误，那么有一个算法使用了n个多log(n)时间和多log(n)空间:http://www.eccc.uni-trier.de/report/2009/119/。

#2

With reference to the excellent answer from Matthieu M., here is an implementation in C# that seems to work beautifully.

关于马蒂厄姆的精彩回答。这里是c#的一个实现，看起来效果很好。

/// <summary>
/// Checks to see if brackets are well formed.
/// Passes "Valid parentheses" challenge on www.codeeval.com,
/// which is a programming challenge site much like www.projecteuler.net.
/// </summary>
/// <param name="input">Input string, consisting of nothing but various types of brackets.</param>
/// <returns>True if brackets are well formed, false if not.</returns>
static bool IsWellFormedBrackets(string input)
{
    string previous = "";
    while (input.Length != previous.Length)
    {
        previous = input;
        input = input
            .Replace("()", String.Empty)
            .Replace("[]", String.Empty)
            .Replace("{}", String.Empty);                
    }
    return (input.Length == 0);
}

Essentially, all it does is remove pairs of brackets until there are none left to remove; if there is anything left the brackets are not well formed.

从本质上说，它所做的就是删除一对括号，直到没有剩下的括号;如果有什么东西留在括号里，就不会形成。

Examples of well formed brackets:

格式良好的括号示例:

()[]
{()[]}

Example of malformed brackets:

畸形的括号的例子:

([)]
{()[}]

#3

If the input is read-only, I don't think we can do O(1) space. It is a well known fact that any O(1) space decidable language is regular (i.e writeable as a regular expression). The set of strings you have is not a regular language.

如果输入是只读的，我认为我们不能做O(1)空间。众所周知，任何O(1)空间可判定语言都是规则的(i。e可写作为一个正则表达式)。您所拥有的字符串集不是常规语言。

Of course, this is about a Turing Machine. I would expect it to be true for fixed word RAM machines too.

当然，这是关于一个图灵机。我希望它也适用于固定字RAM机器。

#4

Edit: Although simple, this algorithm is actually O(n^2) in terms of character comparisons. To demonstrate it, one can simply generate a string as '(' * n + ')' * n.

编辑:这种算法虽然简单,但是实际上是O(n ^ 2)的字符比较。为了演示它，我们可以简单地生成一个字符串为'(' * n + ')' * n。

I have a simple, though perhaps erroneous idea, that I will submit to your criticisms.

我有一个简单的，虽然可能是错误的想法，我将服从你的批评。

It's a destructive algorithm, which means that if you ever need the string it would not help (since you would need to copy it down).

这是一种破坏性的算法，这意味着如果您需要字符串，它就不会有帮助(因为您需要将它复制下来)。

Otherwise, the algorithm work with a simple index within the current string.

否则，该算法使用当前字符串中的一个简单索引。

The idea is to remove pairs one after the others:

这个想法是为了消除对另一个人的影响:

1. ([{}()])
2. (({ }()))
3. ([()])
4. ((()))
5. ([])
6. ([])
7. ()
8. ()
9. empty -> OK
10. 空- >好吧

It is based on the simple fact that if we have matching pairs, then at least one is of the form () without any pair character in between.

它基于一个简单的事实:如果我们有匹配的对，那么至少有一个是表单()，中间没有任何对字符。

Algorithm:

算法:

1. i := 0
2. 我:= 0
3. Find a matching pair from i. If none is found, then the string is not valid. If one is found, let i be the index of the first character.
4. 找到与i匹配的一对，如果没有找到，则该字符串无效。如果找到一个，让我成为第一个字符的索引。
5. Remove [i:i+1] from the string
6. 从字符串中删除[i:i+1]。
7. If i is at the end of the string, and the string is not empty, it's a failure.
8. 如果我在字符串的末尾，并且字符串不是空的，那么它就是一个失败。
9. If [i-1:i] is a matching pair, i := i-1 and back to 3.
10. 如果[i-1:i]是匹配的一对，i:= i-1，返回到3。
11. Else, back to 1.
12. 别的,回1。

The algorithm is O(n) in complexity because:

该算法复杂度为O(n)，因为:

• each iteration of the loop removes 2 characters from the string
• 循环的每个迭代从字符串中删除两个字符。
• the step 2., which is linear, is naturally bound (i cannot grow indefinitely)
• 步骤2。它是线性的，是自然约束的(我不能无限增长)

And it's O(1) in space because only the index is required.

在空间中是O(1)因为只需要索引。

Of course, if you can't afford to destroy the string, then you'll have to copy it, and that's O(n) in space so no real benefit there!

当然，如果你不能破坏字符串，那么你必须复制它，这是在空间中的O(n)所以没有真正的好处!

Unless, of course, I am deeply mistaken somewhere... and perhaps someone could use the original idea (there is a pair somewhere) to better effect.

当然，除非我在某个地方被深深误解了……也许有人可以用最初的想法(在某个地方有一对)更好的效果。

#5

I doubt you'll find a better solution, since even if you use internal functions to regexp or count occurrences, they still have a O(...) cost. I'd say your solution is the best :)

我怀疑您是否会找到一个更好的解决方案，因为即使您使用内部函数来regexp或计数事件，它们仍然有一个O(…)成本。我认为你的解决方案是最好的:)

To optimize for space you could do some run-length encoding on your stack, but I doubt it would gain you very much, except in cases like {{{{{{{{{{}}}}}}}}}}.

为了优化空间，你可以在你的堆上做一些长时间的编码，但我怀疑它会使你的工作效率提高，除非你的工作是在你的工作中。

#6

http://www.sureinterview.com/shwqst/112007

http://www.sureinterview.com/shwqst/112007

It is natural to solve this problem with a stack.

用堆栈来解决这个问题是很自然的。

If only '(' and ')' are used, the stack is not necessary. We just need to maintain a counter for the unmatched left '('. The expression is valid if the counter is always non-negative during the match and is zero at the end.

如果只使用“(”和“)”，则不需要堆栈。我们只需要为不匹配的左边保留一个计数器。如果计数器在匹配过程中始终是非负的，并且在结束时为零，该表达式是有效的。

In general case, although the stack is still necessary, the depth of the stack can be reduced by using a counter for unmatched braces.

一般情况下，虽然堆栈仍然是必需的，但是可以通过使用一个不匹配的括号来减少堆栈的深度。

#7

The following modification of Sbusidan's answer is O(n²) time complex but O(log n) space simple.

对Sbusidan的答案的修改是O(n2)时间复杂度，但是O(log n)空间简单。

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

char opposite(char bracket) {
 switch(bracket) {
  case '[':
   return ']';
  case '(':
   return ')';
 }
}

bool is_balanced(int length, char *s) {
int depth, target_depth, index;
char target_bracket;
 if(length % 2 != 0) {
  return false;
 }

 for(target_depth = length/2; target_depth > 0; target_depth--) {
  depth=0;
  for(index = 0; index < length; index++) {
   switch(s[index]) {
    case '(':
    case '[':
     depth++;
     if(depth == target_depth) target_bracket = opposite(s[index]);
     break;
    case ')':
    case ']':
     if(depth == 0) return false;
     if(depth == target_depth && s[index] != target_bracket) return false;
     depth--;
     break;
   }
  }
 }
}

void main(char* argv[]) {
  char input[] = "([)[(])]";
  char *balanced = is_balanced(strlen(input), input) ? "balanced" : "imbalanced";
  printf("%s is %s.\n", input, balanced);
}

#8

If you can overwrite the input string (not reasonable in the use cases I envision, but what the heck...) you can do it in constant space, though I believe the time requirement goes up to O(n²).

如果您可以覆盖输入字符串(在我设想的用例中不合理)，您可以在常量空间中执行它，尽管我认为时间要求会上升到O(n2)。

Like this:

是这样的:

string s = input
char c = null
int i=0
do
  if s[i] isAOpenChar()
    c = s[i]
  else if
    c = isACloseChar()
      if closeMatchesOpen(s[i],c)
         erase s[i]
         while s[--i] != c ;
         erase s[i]
         c == null
         i = 0;      // Not optimal! It would be better to back up until you find an opening character
      else 
         return fail
  end if
while (s[++i] != EOS)
if c==null
  return pass
else
  return fail

The essence of this is to use the early part of the input as the stack.

其本质是将输入的早期部分用作堆栈。

#9

I know I'm a little late to this party; it's also my very first post on *.

我知道我参加这个派对有点晚了;这也是我在*上的第一篇文章。

But when I looked through the answers, I thought I might be able to come up with a better solution.

但是当我看完答案后，我想我也许能想出一个更好的解决方案。

So my solution is to use a few pointers.
It doesn't even have to use any RAM storage, as registers can be used for this.
I have not tested the code; it's written it on the fly.
You'll need to fix my typos, and debug it, but I believe you'll get the idea.

所以我的解决方案是使用几个指针。它甚至不需要使用任何RAM存储，因为寄存器可以用于此。我没有测试过代码;它是写在苍蝇上的。您需要修复我的错误，并调试它，但是我相信您会明白的。

Memory usage: Only the CPU registers in most cases.
CPU usage: It depends, but approximately twice the time it takes to read the string.
Modifies memory: No.

内存使用:大多数情况下只有CPU寄存器。CPU使用情况:它取决于，但大约是读取字符串所需时间的两倍。修改内存:没有。

b: string beginning, e: string end.
l: left position, r: right position.
c: char, m: match char

b:弦开始，e:弦端。左:右位，右位。c: char, m: match char。

if r reaches the end of the string, we have a success.
l goes backwards from r towards b.
Whenever r meets a new start kind, set l = r.
when l reaches b, we're done with the block; jump to beginning of next block.

如果r到达弦的末端，我们就成功了。从r到b，每当r遇到一个新的开始类型，集合l = r，当l到达b，我们就完成了这个block;跳转到下一个块开始。

const char *chk(const char *b, int len) /* option 2: remove int len */
{
  char c, m;
  const char *l, *r;

  e = &b[len];  /* option 2: remove. */
  l = b;
  r = b;
  while(r < e) /* option 2: change to while(1) */
  {
    c = *r++;
    /* option 2: if(0 == c) break; */
    if('(' == c || '{' == c || '[' == c)
    {
      l = r;
    }
    else if(')' == c || ']' == c || '}' == c)
    {
      /* find 'previous' starting brace */
      m = 0;
      while(l > b && '(' != m && '[' != m && '{' != m)
      {
        m = *--l;
      }
      /* now check if we have the correct one: */
      if(((m & 1) + 1 + m) != c)  /* cryptic: convert starting kind to ending kind and match with c */
      {
        return(r - 1);  /* point to error */
      }
      if(l <= b) /* did we reach the beginning of this block ? */
      {
        b = r; /* set new beginning to 'head' */
        l = b; /* obsolete: make left is in range. */
      }
    }
  }
  m = 0;
  while(l > b && '(' != m && '[' != m && '{' != m)
  {
    m = *--l;
  }
  return(m ? l : NULL); /* NULL-pointer for OK */
}

After thinking about this approach for a while, I realized that it will not work as it is right now.
The problem will be that if you have "[()()]", it'll fail when reaching the ']'.
But instead of deleting the proposed solution, I'll leave it here, as it's actually not impossible to make it work, it does require some modification, though.

在思考了一段时间之后，我意识到它不会像现在这样有效。问题是，如果你有“[()]”，当到达“]”时它会失败。但是，我不会删除建议的解决方案，而是把它放在这里，因为它实际上并不是不可能完成的，但是它确实需要一些修改。

#10

This is an working java code where I filter out the brackets from the string expression and then check the well formedness by replacing wellformed braces by nulls

这是一个工作的java代码，我从字符串表达式中过滤出括号，然后用null替换大括号来检查格式是否正确。

Sample input = (a+{b+c}-[d-e])+[f]-[g] FilterBrackets will output = ({}[])[][] Then I check for wellformedness.

样本输入= (a+{b+c}-[d-e])+[f]-[g] filter括号将输出=[][][][]，然后我检查是否有良好的状态。

Comments welcome.

欢迎评论。

public class ParanString {

    public static void main(String[] args) {

        String s = FilterBrackets("(a+{b+c}-[d-e])[][]");

        while ((s.length()!=0) && (s.contains("[]")||s.contains("()")||s.contains("{}")))
        {
        //System.out.println(s.length());
        //System.out.println(s);
        s = s.replace("[]", "");
        s = s.replace("()", "");
        s = s.replace("{}", "");
        }

        if(s.length()==0)
        {
            System.out.println("Well Formed");
        }
        else
        {
            System.out.println("Not Well Formed");
        }
    }

    public static String FilterBrackets(String str)
    {
        int len=str.length();
        char arr[] = str.toCharArray();
        String filter = "";
        for (int i = 0; i < len; i++)
        {
            if ((arr[i]=='(') || (arr[i]==')') || (arr[i]=='[') || (arr[i]==']') || (arr[i]=='{') || (arr[i]=='}'))
            {
                filter=filter+arr[i];
            }
        }
        return filter;
    }

}

#11

/**
 *
 * @author madhusudan
 */
public class Main {

/**
 * @param args the command line arguments
 */
public static void main(String[] args) {
    new Main().validateBraces("()()()()(((((())))))()()()()()()()()");
    // TODO code application logic here
}

/**
 * @Use this method to validate braces
 */
public void validateBraces(String teststr)
{
    StringBuffer teststr1=new StringBuffer(teststr);
    int ind=-1;
    for(int i=0;i<teststr1.length();)
    {

    if(teststr1.length()<1)
    break;
    char ch=teststr1.charAt(0);
    if(isClose(ch))
    break;
    else if(isOpen(ch))
    {
        ind=teststr1.indexOf(")", i);
        if(ind==-1)
        break;
        teststr1=teststr1.deleteCharAt(ind).deleteCharAt(i);
    }
    else if(isClose(ch))
    {
        teststr1=deleteOpenBraces(teststr1,0,i);
    }
    }
    if(teststr1.length()>0)
    {
        System.out.println("Invalid");

    }else
    {
        System.out.println("Valid");
    }
}
public boolean  isOpen(char ch)
{
    if("(".equals(Character.toString(ch)))
    {
        return true;
    }else
        return false;
}
public boolean  isClose(char ch)
{
    if(")".equals(Character.toString(ch)))
    {
        return true;
    }else
        return false;
}
public StringBuffer deleteOpenBraces(StringBuffer str,int start,int end)
{
    char ar[]=str.toString().toCharArray();
    for(int i=start;i<end;i++)
    {
        if("(".equals(ar[i]))
         str=str.deleteCharAt(i).deleteCharAt(end); 
        break;
    }
    return str;
}

}

#12

Instead of putting braces into the stack, you could use two pointers to check the characters of the string. one start from the beginning of the string and the other start from end of the string. something like

您可以使用两个指针来检查字符串的字符，而不是将括号放入堆栈中。一个从字符串的开头开始，另一个从字符串的末尾开始。类似的

bool isValid(char* s) {
    start = find_first_brace(s);
    end = find_last_brace(s);
    while (start <= end) {
        if (!IsPair(start,end)) return false;
        // move the pointer forward until reach a brace
        start = find_next_brace(start);
        // move the pointer backward until reach a brace
        end = find_prev_brace(end);
    }
    return true;
}

Note that there are some corner case not handled.

注意，这里有一些没有处理的角。

#13

I think that you can implement an O(n) algorithm. Simply you have to initialise an counter variable for each type: curly, square and normal brackets. After than you should iterate the string and should increase the coresponding counter if the bracket is opened, otherwise to decrease it. If the counter is negative return false. AfterI think that you can implement an O(n) algorithm. Simply you have to initialise an counter variable for each type: curly, square and normal brackets. After than you should iterate the string and should increase the coresponding counter if the bracket is opened, otherwise to decrease it. If the counter is negative return false. After you count all brackets, you should check if all counters are zero. In that case, the string is valid and you should return true.

我认为你可以实现一个O(n)算法。简单来说，您必须为每种类型初始化一个计数器变量:卷曲、方括号和普通方括号。之后，您应该迭代字符串，如果括号打开，则应该增加相应的计数器，否则将减少它。如果计数器为负返回false。在我认为你可以实现一个O(n)算法。简单来说，您必须为每种类型初始化一个计数器变量:卷曲、方括号和普通方括号。之后，您应该迭代字符串，如果括号打开，则应该增加相应的计数器，否则将减少它。如果计数器为负返回false。当你数完所有的括号之后，你应该检查所有的计数器是否为零。在这种情况下，字符串是有效的，您应该返回true。

#14

You could provide the value and check if its a valid one, it would print YES otherwise it would print NO

您可以提供该值并检查其是否有效，否则将打印YES，否则将打印NO。

static void Main(string[] args)
        {
            string value = "(((([{[(}]}]))))";
            List<string> jj = new List<string>();
            if (!(value.Length % 2 == 0))
            {
                Console.WriteLine("NO");
            }
            else
            {
                bool isValid = true;


                List<string> items = new List<string>();

                for (int i = 0; i < value.Length; i++)
                {
                    string item = value.Substring(i, 1);
                    if (item == "(" || item == "{" || item == "[")
                    {
                        items.Add(item);
                    }
                    else
                    {
                        string openItem = items[items.Count - 1];
                        if (((item == ")" && openItem == "(")) || (item == "}" && openItem == "{") || (item == "]" && openItem == "["))
                        {
                            items.RemoveAt(items.Count - 1);

                        }
                        else
                        {
                            isValid = false;
                            break;
                        }



                    }
                }


                if (isValid)
                {
                    Console.WriteLine("Yes");
                }
                else
                {
                    Console.WriteLine("NO");
                }
            }
            Console.ReadKey();

        }

#15

var verify = function(text) 
{
  var symbolsArray = ['[]', '()', '<>'];
  var symbolReg = function(n) 
  {
    var reg = [];
    for (var i = 0; i < symbolsArray.length; i++) {
      reg.push('\\' + symbolsArray[i][n]);
    }
    return new RegExp('(' + reg.join('|') + ')','g');
  };
  // openReg matches '(', '[' and '<' and return true or false
  var openReg = symbolReg(0);
  // closeReg matches ')', ']' and '>' and return true or false
  var closeReg = symbolReg(1);
  // nestTest matches openSymbol+anyChar+closeSymbol
  // and returns an obj with the match str and it's start index
  var nestTest = function(symbols, text) 
  {
    var open = symbols[0]
      , close = symbols[1]
      , reg = new RegExp('(\\' + open + ')([\\s\\S])*(\\' + close + ')','g')
      , test = reg.exec(text);
    if (test) return {
      start: test.index,
      str: test[0]
    };
    else return false;
  };
  var recursiveCheck = function(text) 
  {
    var i, nestTests = [], test, symbols;
    // nestTest with each symbol
    for (i = 0; i < symbolsArray.length; i++) 
    {
      symbols = symbolsArray[i];
      test = nestTest(symbols, text);
      if (test) nestTests.push(test);
    }
    // sort tests by start index
    nestTests.sort(function(a, b) 
    {
      return a.start - b.start;
    });
    if (nestTests.length) 
    {
      // build nest data: calculate match end index
      for (i = 0; i < nestTests.length; i++) 
      {
        test = nestTests[i];
        var end = test.start + ( (test.str) ? test.str.length : 0 );
        nestTests[i].end = end;
        var last = (nestTests[i + 1]) ? nestTests[i + 1].index : text.length;
        nestTests[i].pos = text.substring(end, last);
      }
      for (i = 0; i < nestTests.length; i++) 
      {
        test = nestTests[i];
        // recursive checks  what's after the nest 
        if (test.pos.length && !recursiveCheck(test.pos)) return false;
        // recursive checks  what's in the nest 
        if (test.str.length) {
          test.str = test.str.substring(1, test.str.length - 1);
          return recursiveCheck(test.str);
        } else return true;
      }
    } else {
      // if no nests then check for orphan symbols
      var closeTest = closeReg.test(text);
      var openTest = openReg.test(text);
      return !(closeTest || openTest);
    }
  };
  return recursiveCheck(text);
};

#16

Using c# OOPS programming... Small and simple solution

使用c#编程哦…小而简单的解决方案

Console.WriteLine("Enter the string");
            string str = Console.ReadLine();
            int length = str.Length;
            if (length % 2 == 0)
            {
                while (length > 0 && str.Length > 0)
                {
                    for (int i = 0; i < str.Length; i++)
                    {
                        if (i + 1 < str.Length)
                        {
                            switch (str[i])
                            {
                                case '{':
                                    if (str[i + 1] == '}')
                                        str = str.Remove(i, 2);
                                    break;
                                case '(':
                                    if (str[i + 1] == ')')
                                        str = str.Remove(i, 2);
                                    break;
                                case '[':
                                    if (str[i + 1] == ']')
                                        str = str.Remove(i, 2);
                                    break;
                            }
                        }
                    }
                    length--;
                }
                if(str.Length > 0)
                    Console.WriteLine("Invalid input");
                else
                    Console.WriteLine("Valid input");
            }
            else
                Console.WriteLine("Invalid input");
            Console.ReadKey();

#17

This is my solution to the problem. O(n) is the complexity of time without complexity of space. Code in C.

这是我解决这个问题的办法。O(n)是时间的复杂性，没有空间的复杂性。在C代码。

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

bool checkBraket(char *s)
{
    int curly = 0, rounded = 0, squre = 0;
    int i = 0;
    char ch = s[0];
    while (ch != '\0')
    {
        if (ch == '{') curly++;
        if (ch == '}') {
            if (curly == 0) {
                return false;
            } else {
                curly--; }
        }
        if (ch == '[') squre++;
        if (ch == ']') {
            if (squre == 0) {
                return false;
            } else {
                squre--;
            }
        }
        if (ch == '(') rounded++;
        if (ch == ')') {
            if (rounded == 0) {
                return false;
            } else {
                rounded--;
            }
        }
        i++;
        ch = s[i];
    }
    if (curly == 0 && rounded == 0 && squre == 0){
        return true;
    }
    else {
        return false;
    }
}
void main()
{
    char mystring[] = "{{{{{[(())}}]}}}";
    int answer = checkBraket(mystring);
    printf("my answer is %d\n", answer);
    return;
}