C# 检查字符串是否有平衡括号

Checking string has balanced parentheses

提问by Navaneeth K N

I am reading the Algorithm Design Manual Second Editionand this is from an exercise question. Quoting the question

我正在阅读算法设计手册第二版，这是来自一个练习题。引用问题

A common problem for compilers and text editors is determining whether the parentheses in a string are balanced and properly nested. For example, the string ((())())() contains properly nested pairs of parentheses, which the strings )()( and ()) do not. Give an algorithm that returns true if a string contains properly nested and balanced parentheses, and false if otherwise. For full credit, identify the position of the first offending parenthesis if the string is not properly nested and balanced.

编译器和文本编辑器的一个常见问题是确定字符串中的括号是否平衡并正确嵌套。例如，字符串 ((())())() 包含正确嵌套的括号对，而字符串 )()( 和 ()) 则没有。给出一个算法，如果字符串包含正确嵌套和平衡的括号，则返回 true，否则返回 false。如果字符串没有正确嵌套和平衡，请确定第一个违规括号的位置，以获得完整的分数。

Question is under stacks,queues and lists category. Here is what I wrote in C#.

问题在堆栈、队列和列表类别下。这是我用 C# 写的。

const char LeftParenthesis = '(';
const char RightParenthesis = ')';
bool AreParenthesesBalanced(string str, out int errorAt)
{
    var items = new Stack<int>(str.Length);
    errorAt = -1;
    for (int i = 0; i < str.Length; i++)
    {
        char c = str[i];
        if (c == LeftParenthesis)
            items.Push(i);
        else if (c == RightParenthesis)
        {
            if (items.Count == 0)
            {
                errorAt = i + 1;
                return false;
            }
            items.Pop();
        }
    }
    if (items.Count > 0)
    {
        errorAt = items.Peek() + 1;
        return false;
    }
    return true;
}

This works well. But I am not sure that this is the right method to approach this problem. Any better ideas are welcome.

这很好用。但我不确定这是解决这个问题的正确方法。欢迎任何更好的想法。

采纳答案by nlucaroni

I think this is the intention, but really you just need to decrement and increment a counter if you are only dealing with parenthesis. If you are dealing with the pairings of square brackets, angle brackets, curly braces or whatever character pairing you'd like to use, you'll need a stack like you have done.

我认为这是意图，但实际上，如果您只处理括号，您只需要减少和增加计数器。如果您正在处理方括号、尖括号、花括号或任何您想使用的字符配对，您将需要一个堆栈，就像您所做的那样。

You can also use a list, pulling the head element off and on, but really a stack is probably implemented as a list anyway --at least it is in ocaml.

您也可以使用列表，将头元素拉断或拉开，但实际上堆栈可能无论如何都实现为列表——至少它在 ocaml 中。

回答by Steven Sudit

As TheVillageIdiot said, it's fine. You could also implement it recursively, which might be more elegant, or might not. Finally, you might want to require that matching parentheses contain something valid between them, so as to allow "(a)" but not "()".

正如 TheVillageIdiot 所说，这很好。您也可以递归地实现它，这可能更优雅，也可能不是。最后，您可能想要要求匹配的括号在它们之间包含一些有效的东西，以便允许“(a)”而不是“()”。

回答by Bill

Why have a return value and an out parameter that give the same information?

为什么有一个返回值和一个输出参数提供相同的信息？

You could return an int: -1 = balanced, otherwise the index of the error.

您可以返回 int: -1 = balance，否则为错误索引。

回答by SK9

1. Remove all non-'(' and -')' characters from an input string. This gives you a string of '(' and ')' only.

2. If the string has odd length, return false.

3. Else, start reading along our string, adding +1 to a "signature" for each '(' and -1 for each ')'; if this signature is ever negative, return false.

4. Return true.

1. 从输入字符串中删除所有非 '(' 和 -')' 字符。这仅给您一串 '(' 和 ')' 。

2. 如果字符串的长度为奇数，则返回 false。

3. 否则，开始阅读我们的字符串，为每个 '(' 和 -1 为每个 ')' 添加 +1 到“签名”；如果此签名为负，则返回 false。

4. 返回真。

回答by alex

int i;
int len; 
char popped;
stack<char> st;
string a = "({<<";
len = a.length();

for(i=0;i<len;i++)
{
    if(a[i] == '<' || a[i] == '(' || a[i] == '[' || a[i] == '{')
    {
        st.push(a[i]); 
        continue;
    }
    if(a[i] == '>' || a[i] == ')' || a[i] == ']' || a[i] == '}')
    {
        if(st.empty())
        {
            cout << "stack is empty, when popped , not balanced" << endl;
            return 0;
        }
        else
        {
            popped = st.top(); 
            st.pop();
            if (!((a[i] == '>' && popped == '<') || (a[i] == ')' && popped == '(') || (a[i] == '}' && popped == '{') || (a[i] == '>' && popped == '<'))) //ok
            {
                cout << "not balanced on character" + std::string(1,a[i]) << endl;
                return 0;
            }
        }

    }

}
if(st.empty())
{
    cout << "balanced" << endl;
}
else
{
    cout << "not balanced stack not empty" << endl;
}

回答by Russell Stephan

    static public bool CheckForBalancedBracketing(string IncomingString)
    {
    /*******************************************************************
     * The easiest way to check for balanced bracketing is to start    *
     * counting left to right adding one for each opening bracket, '(' *
     * and subtracting 1 for every closing bracket, ')'.  At the end   *
     * the sum total should be zero and at no time should the count    *
     * fall below zero.                                                *
     *                                                                 *
     * Implementation:  The bracket counting variable is an unsigned   *
     * integer and we trap an overflow exception.  This happens if the *
     * unsigned variable ever goes negative.  This allows us to abort  *
     * at the very first imbalance rather than wasting time checking   *
     * the rest of the characters in the string.                       *
     *                                                                 *
     * At the end all we have to do is check to see if the count       *
     * is equal to zero for a "balanced" result.                       *
     *                                                                 *
     *******************************************************************/
        const char LeftParenthesis = '(';
        const char RightParenthesis = ')';
        uint BracketCount = 0;

        try
        {
            checked  // Turns on overflow checking.
            {
                for (int Index = 0; Index < IncomingString.Length; Index++)
                {
                    switch (IncomingString[Index])
                    {
                        case LeftParenthesis:
                            BracketCount++;
                            continue;
                        case RightParenthesis:
                            BracketCount--;
                            continue;
                        default:
                            continue;
                    }  // end of switch()

                }
            }
        }

        catch (OverflowException)
        {
            return false;
        }

        if (BracketCount == 0)
        {
            return true;
        }

        return false;

    }  // end of CheckForBalancedBracketing()

回答by ravi

Checking balanced parentheses
package parancheck;

import java.util.EmptyStackException;
import java.util.Stack;

public class ParnCheck 
{
    public static void main(String args[])
    {
        int pu = 0;
        int po = 0;
        String str = "()())";
        System.out.println(str); 
        Stack st = new Stack();
       for(int i=0; i<str.length();i++)
       {
        if(str.charAt(i)=='(')
        {
           doPush(st, str.charAt(i));
           pu++;
         }
        else 
        {
             try
              {
                doPop(st);
              }
             catch(EmptyStackException e)
              {
                System.out.println("");
              }
              po++;
        }
     }


       if(pu == po)
       {
           System.out.println("Correct");
       }
       else
       {
           System.out.println("Wrong");
       }

    }
    static void doPush(Stack st,char ch)
    {
        st.push(ch);
    }
    static void doPop(Stack st)
    {
        char c = (char)st.pop();
    }
}

回答by user1139428

import java.util.Stack;

public class CheckBalancedParenthesis {

    public static void main (String args[]){
        CheckBalancedParenthesis checker = new CheckBalancedParenthesis();
        System.out.println(checker.checkBalancedParenthesis("{}}{}{}{}{}"));
    }

    public boolean checkBalancedParenthesis(String pattern){
        Stack stack = new Stack();
        for(int i = 0; i < pattern.length();i++){
            char c = pattern.charAt(i);
            if(c == '{'){
                stack.push(c);
            }else if (c == '}'){
                if(!stack.isEmpty()){
                    stack.pop();
                } else{
                    System.out.println("Error at - " + i);
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

回答by Abdullah

using System;
class Solution
{
    public int solution(string S)
    {
        int x1 = 0;
        int x2 = 0;
        for (int i = 0; i < S.Length; i++)
        {
            if (S[i] == ')')
                if (x1 <= 0) return 0;
                else x1--;
            else if (S[i] == '(')
                x1++;
        }
        if (x1 == 0)
            return 1;
        else
            return 0;
    }
}

回答by Yadira Garnica

Time order O(n) and spatial order O(1)

时间顺序 O(n) 和空间顺序 O(1)

public static bool IsBalanced(string input)
{
   int count = 0;
   for (int i = 0; i < input.Length; i++)
   {
       if (input[i] == '(') count++;
       if (input[i] == ')') count--;
       if (count < 0) return false;
    }
    if (count == 0) return true;
    return false;
}