Подтвердить что ты не робот

Контрольная строка имеет сбалансированные круглые скобки

Я читаю Второе издание "Руководство по разработке алгоритмов", и это связано с вопросом упражнения. Цитируя вопрос

Общая проблема для компиляторов и текстовые редакторы определяют, круглые скобки в строке сбалансированным и правильно вложенным. Для Например, строка ((())())() содержит правильно вложенные пары круглые скобки, в которых строки)() ( и не. Дайте алгоритм, который возвращает true, если строка содержит правильно вложенные и сбалансированные скобки и false, если в противном случае. Для получения полного кредита укажите позицию первой оскорбительной круглой скобки, если строка не является надлежащим образом вложенной и сбалансированным.

Вопрос находится в категории стеков, очередей и списков. Вот что я написал в С#.

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;
}

Это хорошо работает. Но я не уверен, что это правильный метод для решения этой проблемы. Любые лучшие идеи приветствуются.

4b9b3361

ОТВЕТЫ

Ответ 1

Я думаю, что это намерение, но на самом деле вам просто нужно уменьшить и увеличить счетчик, если вы имеете дело только с круглыми скобками. Если вы имеете дело с сопряжениями квадратных скобок, угловых скобок, фигурных скобок или любого другого сочетания символов, которое вы хотели бы использовать, вам понадобится стек, как вы это сделали.

Вы также можете использовать список, вытаскивая элемент head и включаться, но на самом деле стек, вероятно, реализован как список в любом случае - по крайней мере, он находится в ocaml.

Ответ 2

    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()

Ответ 3

  • Удалите все не-'(' и - ')' символы из входной строки. Это дает вам только строку '(' и ')'.

  • Если строка имеет нечетную длину, верните false.

  • Иначе, начните читать по нашей строке, добавив +1 к "сигнатуре" для каждого '(' и -1 для каждого ')'; если эта подпись всегда отрицательная, верните false.

  • Возвращает true.

Ответ 4

Это будет работать для комбинации (), {} и [].

Также обнаруживает ошибки, такие как: ([)], )[]() и ()( ,...

bool isWellFormatted(string line)
{           
        Stack<char> lastOpen = new Stack<char>();
        foreach (var c in line)
        {               
            switch (c)
            {
                case ')':
                    if (lastOpen.Count == 0 || lastOpen.Pop() != '(') return false;
                    break;
                case ']':
                    if (lastOpen.Count == 0 || lastOpen.Pop() != '[' ) return false;
                    break;
                case '}':
                    if (lastOpen.Count == 0 || lastOpen.Pop() != '{') return false;
                    break;
                case '(': lastOpen.Push(c); break;
                case '[': lastOpen.Push(c); break;
                case '{': lastOpen.Push(c); break;
            }                                                                       
        }
        if (lastOpen.Count == 0) return true;
        else return false;
    }

Ответ 5

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;
    }
}

Ответ 6

Временной порядок 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;
}

С http://yadiragarnicabonome.com/parentheses-algorithms/

Ответ 7

Как сказал TheVillageIdiot, все в порядке. Вы также можете реализовать его рекурсивно, что может быть более элегантным, а может и нет. Наконец, вы можете потребовать, чтобы соответствующие круглые скобки содержали что-то действительное между ними, чтобы разрешить "(a)", но не "()".

Ответ 8

Почему у вас есть возвращаемое значение и параметр out, которые дают одну и ту же информацию?

Вы можете вернуть int: -1 = сбалансированный, в противном случае индекс ошибки.

Ответ 9

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;
}

Ответ 10

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();
    }
}

Ответ 11

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();
    }
}

Ответ 12

Вот простое решение для проверки скобок:
1. Сохраните скобки и скобки завершения в строке.
2. Прокрутите список, которому мы хотим проверить и проверить следующую логику:

              a) Если элемент находится в стартовых скобках, PUSH IT IN STACK
              b) Если элемент находится в конечных скобках, сравните его индекс (в конечной скобке) с элементом верхнего стека                   index (в стартовых скобках).
              c) Если индекс является одним и тем же POP TOP ITEM OF STACK. Иначе его недопустимая строка.
              d) Заключительный шаг, проверьте наличие стека, если он имеет элемент /s, это означает его недопустимую строку.

    string starters = "({[<";
    string enders = ")}]>";
    Stack stack  = new Stack();
    foreach(char c in txtValue.Text.Trim())
    {
        if(starters.Contains(c))
        {
            stack.Push(c);
        }
        else if (enders.Contains(c))
        {
            if (stack.Count > 0)
            {

                if (enders.IndexOf(c) == starters.IndexOf(Convert.ToChar(stack.Peek())))
                {
                    stack.Pop();
                }
                else
                {
                    lblResult.Text = "Invaluid string";
                }
            }
        }
    }

    if(stack.Count == 0)
    {
        lblResult.Text = "Valid string";
    }
    else
    {
        lblResult.Text = "InValid string";
    }

Ответ 13

Вершина обратной связи с идеей @Russell:

public class BalancedBrackets
{
    private readonly char[] _leftBrackets = new char[] {'[', '(', '{', '<'};
    private readonly char[] _rightBrackets = new char[] {']', ')', '}', '>'};

    public bool IsBalanced(string input)
    {
        int count = 0;
        foreach (var character in input.ToCharArray())
        {
            if (_leftBrackets.Contains(character)) count++;
            if (_rightBrackets.Contains(character)) count--;
        }
        return count == 0;
    }
}

Ответ 14

Здесь один вкладыш для С# с использованием System.Linq:

expression.Aggregate(0, (state, ch) => state == -1 ? -1 : state + (ch == '(' ? 1 : ch == ')' ? -1 : 0)) == 0

он использует тот факт, что строка на самом деле IEnumerable символов, поэтому мы можем запустить на ней функцию Aggregate. Мы увеличиваем счетчик на 1, когда мы сталкиваемся с '(' char и уменьшаем его на 1 на ')' char. Как только мы достигнем отрицательного значения -1, мы остаемся там, чтобы указать недопустимое состояние.

У него нет раннего выхода, поэтому он будет медленнее, чем большинство реализаций, представленных здесь, но, возможно, кому-то это будет полезно:)

Ответ 15

Это должно работать:

public class Balanced {
    public static boolean isbalanced(String input) {
        int open = 0;
        int close = 0;
        for (int i=0; i< input.length();i++) {
            switch (input.charAt(i)) {
                case '{':
                case '(':
                case '[':
                    open++;
                    break;
                case '}':
                case ')':
                case ']':
                    close++;
            default:
                break;
            }
        }
        if (open == close){
            return true;
        }
        else {
            return false;
        }
    }

public static void main(String args[]) {
    System.out.println(Balanced.isbalanced("()"));
}
}

Ответ 16

Я бы использовал очередь и стек, чтобы проверить на открытие и закрытие матча

        var dictionary = new Dictionary<string, string>() {
            { "{", "}" },
            {"[", "]" },
            {"(",")" }
        };


        var par = "{()}";
        var queue = new Queue();
        var stack = new Stack();

        bool isBalanced = true;

        var size = par.ToCharArray().Length;

        if(size % 2 != 0)
        {
            isBalanced = false;
        }
        else
        {
            foreach (var c in par.ToCharArray())
            {
                stack.Push(c.ToString());
                queue.Enqueue(c.ToString());
            }

            while (stack.Count > size/2 && queue.Count > size/2)
            {
                var a = (string)queue.Dequeue();
                var b = (string)stack.Pop();

                if (dictionary.ContainsKey(a) && b != dictionary[a])
                {
                    isBalanced = false;

                }


            }


        }

        Console.WriteLine(isBalanced?"balanced!":"Not Balanced");

        Console.ReadLine();

например, в первой итерации a = '{' and b = '}', поэтому вы проверяете, сбалансирован он или нет

Ответ 17

Я сделал это немного более общим Java

public static boolean isBalanced(String expression)
{
    // pairs at the same index
    List<Character> openers = Arrays.asList('{', '(', '[');
    List<Character> closers = Arrays.asList('}', ')', ']');
    char[] exp = expression.toCharArray();
    Stack<Character> stack = new Stack<>();
    for(Character character: exp){
        if (openers.contains(character))
            stack.push(character);
        if(closers.contains(character)){
            if (stack.empty())
                return false;
            //matching pair should be at the same index
            Character opener = stack.pop();
            int openerIndex = openers.indexOf(opener);
            int closerIndex = closers.indexOf(character);
            if (openerIndex != closerIndex)
                return false;
        }
    }
    return stack.empty();
}

Ответ 18

С# 7 или около того теперь также есть кортежи. Вам больше не нужен аргумент out. Как отмечали многие другие, нет необходимости в стеке, очереди или чем-то подобном.
Достаточно просто счетчика баланса.

    -- Checks the balance of braces in a string.
    -- Error case 1: More closes than open. We can identify the first culprit by index.
    -- Error case 2: More opens than closes. We return the length of the String, 
    --               indicating that there are closed braces missing.
    -- Good case: As many opens as closes. We return (True,Nothing)
    checkBraces :: String -> (Bool,Maybe Int)
    checkBraces [] = (True,Nothing)
    checkBraces s =
        let (balance,offender) = foldl account (0,-1) $ zip [0..] s in
        if balance == 0 
            then (True,Nothing) 
            else (False,Just $ if -1 == offender then length s else offender)
        where
            account :: (Int,Int) -> (Int, Char) -> (Int,Int)
            account [email protected](_,off) _ | off /= -1 = acc     -- Once there was an error we stop looking what happens.
            account [email protected](b,off) (i,'(') = (b+1,off)     -- One more open brace.
            account (b,off) (i,')')                     -- One more closed brace.
                    | b <= 0 = (b-1,i)                  -- Ouch. We closed more than we opened!
                    | otherwise = (b-1,off)             -- Okay.
            account acc (i,_) = acc                     -- Some other character (Not in ['(',')'])


    testCases =
        [ ("",True)
        , ("(",False)
        , (")",False)
        , ("))((",False)
        , ("()()",True)
        , ("(()))",False)
        ]

    test = 
        all ((==) True) . fmap testOne $ testCases
        where
            testOne (tc,expected) =
                let (actual,_) = checkBraces tc in
                actual == expected

Дополнительное примечание: Подсветка синтаксиса для Haskell здесь нуждается в некотором улучшении, верно? :)