Базовая рекурсия, проверка сбалансированной скобки

Ответ 1

Существует много способов сделать это, но самый простой алгоритм состоит в том, чтобы просто обрабатывать вперёд слева направо, передавая стек как параметр

FUNCTION isBalanced(String input, String stack) : boolean
  IF isEmpty(input)
    RETURN isEmpty(stack)
  ELSE IF isOpen(firstChar(input))
    RETURN isBalanced(allButFirst(input), stack + firstChar(input))
  ELSE IF isClose(firstChar(input))
    RETURN NOT isEmpty(stack) AND isMatching(firstChar(input), lastChar(stack))
      AND isBalanced(allButFirst(input), allButLast(stack))
  ELSE
    ERROR "Invalid character"

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

static String open  = "([<{";
static String close = ")]>}";

static boolean isOpen(char ch) {
    return open.indexOf(ch) != -1;
}
static boolean isClose(char ch) {
    return close.indexOf(ch) != -1;
}
static boolean isMatching(char chOpen, char chClose) {
    return open.indexOf(chOpen) == close.indexOf(chClose);
}

static boolean isBalanced(String input, String stack) {
    return
        input.isEmpty() ?
            stack.isEmpty()
        : isOpen(input.charAt(0)) ?
            isBalanced(input.substring(1), input.charAt(0) + stack)
        : isClose(input.charAt(0)) ?
            !stack.isEmpty() && isMatching(stack.charAt(0), input.charAt(0))
              && isBalanced(input.substring(1), stack.substring(1))
        : isBalanced(input.substring(1), stack);
}

Жгут проводов:

    String[] tests = {
        "()[]<>{}",
        "(<",
        "]}",
        "()<",
        "(][)",
        "{(X)[XY]}",
    };
    for (String s : tests) {
        System.out.println(s + " = " + isBalanced(s, ""));
    }

Вывод:

()[]<>{} = true
(< = false
]} = false
()< = false
(][) = false
{(X)[XY]} = true

Ответ 2

Во-первых, к вашему первоначальному вопросу, просто имейте в виду, что если вы работаете с очень длинными строками, вы не хотите делать точные копии за вычетом одной буквы каждый раз, когда вы совершаете вызов функции. Поэтому вам следует использовать индексы или убедиться, что ваш язык выбора не делает копии за кулисами.

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

Я продемонстрирую программу C, которая соответствует ( и ). Добавление других типов, таких как [ и ], является упражнением для читателя. Все, что я поддерживаю в функции, это мое положение в строке (передано как указатель), потому что рекурсия - это мой стек.

/* Search a string for matching parentheses.  If the parentheses match, returns a
 * pointer that addresses the nul terminator at the end of the string.  If they
 * don't match, the pointer addresses the first character that doesn't match.
 */
const char *match(const char *str)
{
        if( *str == '\0' || *str == ')' ) { return str; }
        if( *str == '(' )
        {
                const char *closer = match(++str);
                if( *closer == ')' )
                {
                        return match(++closer);
                }
                return str - 1;
        }

        return match(++str);
}

Протестировано с помощью этого кода:

    const char *test[] = {
            "()", "(", ")", "", "(()))", "(((())))", "()()(()())",
            "(() ( hi))) (())()(((( ))))", "abcd"
    };

    for( index = 0; index < sizeof(test) / sizeof(test[0]); ++index ) {
            const char *result = match(test[index]);

            printf("%s:\t", test[index]);
            *result == '\0' ? printf("Good!\n") :
                    printf("Bad @ char %d\n", result - test[index] + 1);
    }

Вывод:

(): Good!
(:  Bad @ char 1
):  Bad @ char 1
:   Good!
(())):      Bad @ char 5
(((()))):   Good!
()()(()()): Good!
(() ( hi))) (())()(((( )))):    Bad @ char 11
abcd:       Good!

Ответ 3

Идея состоит в том, чтобы сохранить список открытых скобок, и если вы найдете закрывающий брекет, проверьте, закрывает ли он последнее открытое:

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

Когда строка окончательно пуста, если список скобок также пуст (так что все скобки были закрыты) return true, else false

ALGORITHM (на Java):

public static boolean isBalanced(final String str1, final LinkedList<Character> openedBrackets, final Map<Character, Character> closeToOpen) {
    if ((str1 == null) || str1.isEmpty()) {
        return openedBrackets.isEmpty();
    } else if (closeToOpen.containsValue(str1.charAt(0))) {
        openedBrackets.add(str1.charAt(0));
        return isBalanced(str1.substring(1), openedBrackets, closeToOpen);
    } else if (closeToOpen.containsKey(str1.charAt(0))) {
        if (openedBrackets.getLast() == closeToOpen.get(str1.charAt(0))) {
            openedBrackets.removeLast();
            return isBalanced(str1.substring(1), openedBrackets, closeToOpen);
        } else {
            return false;
        }
    } else {
        return isBalanced(str1.substring(1), openedBrackets, closeToOpen);
    }
}

TEST

public static void main(final String[] args) {
    final Map<Character, Character> closeToOpen = new HashMap<Character, Character>();
    closeToOpen.put('}', '{');
    closeToOpen.put(']', '[');
    closeToOpen.put(')', '(');
    closeToOpen.put('>', '<');

    final String[] testSet = new String[] { "abcdefksdhgs", "[{aaa<bb>dd}]<232>", "[ff{<gg}]<ttt>", "{<}>" };
    for (final String test : testSet) {
        System.out.println(test + "  ->  " + isBalanced(test, new LinkedList<Character>(), closeToOpen));
    }
}

OUTPUT

abcdefksdhgs  ->  true
[{aaa<bb>dd}]<232>  ->  true
[ff{<gg}]<ttt>  ->  false
{<}>  ->  false

Обратите внимание, что я импортировал следующие классы:

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

Ответ 4

Это не имеет никакого значения с логической точки зрения - если вы сохраняете стек всех не сбалансированных в настоящий момент парен, которые вы передаете каждому шагу рекурсии, вам никогда не придется оглядываться назад, поэтому неважно, вырезаете строку на каждом рекурсивном вызове или просто увеличиваете индекс и смотрите только на текущий первый символ.

В большинстве языков программирования, которые имеют непеременные строки, вероятно, более дорого (с точки зрения производительности) сократить строку, чем передавать немного большую строку в стеке. С другой стороны, на языке, подобном C, вы можете просто увеличить указатель внутри массива char. Я думаю, что это довольно зависящий от языка, какой из этих двух подходов более "эффективен". Они оба эквивалентны с концептуальной точки зрения.

Ответ 5

 public static boolean isBalanced(String str) {
    if (str.length() == 0) {
        return true;
    }
    if (str.contains("()")) {
        return isBalanced(str.replaceFirst("\\(\\)", ""));
    }

    if (str.contains("[]")) {
        return isBalanced(str.replaceFirst("\\[\\]", ""));
    }
    if (str.contains("{}")) {
        return isBalanced(str.replaceFirst("\\{\\}", ""));
    } else {
        return false;
    }
}

Ответ 6

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

Ответ 7

На языке программирования Scala я бы сделал это следующим образом:

  def balance(chars: List[Char]): Boolean = {

    def process(chars: List[Char], myStack: Stack[Char]): Boolean =

      if (chars.isEmpty) myStack.isEmpty

      else {
        chars.head match {
          case '(' => process(chars.tail, myStack.push(chars.head))
          case ')' => if (myStack.contains('(')) process(chars.tail, myStack.pop)
          else false
          case '[' => process(chars.tail, myStack.push(chars.head))
          case ']' => {
            if (myStack.contains('[')) process(chars.tail, myStack.pop) else false
          }
          case _ => process(chars.tail, myStack)
        }
      }

    val balancingAuxStack = new Stack[Char]

    process(chars, balancingAuxStack)
  }

Пожалуйста, отредактируйте, чтобы сделать его идеальным.

Я предлагал только преобразование в Scala.

Ответ 8

func evalExpression(inStringArray:[String])-> Bool{
    var status = false
    var inStringArray = inStringArray
    if inStringArray.count == 0 {
        return true
    }

    // determine the complimentary bracket.
    var complimentaryChar = ""
    if (inStringArray.first == "(" || inStringArray.first == "[" || inStringArray.first == "{"){
        switch inStringArray.first! {
        case "(":
            complimentaryChar = ")"
            break
        case "[":
            complimentaryChar = "]"
            break
        case "{":
            complimentaryChar = "}"
            break
        default:
            break
        }
    }else{
        return false
    }

    // find the complimentary character index in the input array.
    var index = 0
    var subArray = [String]()
    for i in 0..<inStringArray.count{
        if inStringArray[i] == complimentaryChar {
            index = i
        }
    }
    // if no complimetary bracket is found,so return false.
    if index == 0{
        return false
    }
    // create a new sub array for evaluating the brackets.
    for i in 0...index{
        subArray.append(inStringArray[i])
    }

    subArray.removeFirst()
    subArray.removeLast()

    if evalExpression(inStringArray: subArray){
        // if part of the expression evaluates to true continue with the rest.
        for _ in 0...index{
            inStringArray.removeFirst()
        }
        status = evalExpression(inStringArray: inStringArray)
    }

    return status
}

Ответ 9

PHP Решение для проверки сбалансированных круглых скобок

<?php
/**
 * @param string $inputString
 */
function isBalanced($inputString)
{
    if (0 == strlen($inputString)) {
        echo 'String length should be greater than 0';
        exit;
    }

    $stack = array();
    for ($i = 0; $i < strlen($inputString); $i++) {
        $char = $inputString[$i];
        if ($char === '(' || $char === '{' || $char === '[') {
            array_push($stack, $char);
        }
        if ($char === ')' || $char === '}' || $char === ']') {
            $matchablePairBraces = array_pop($stack);
            $isMatchingPair = isMatchingPair($char, $matchablePairBraces);
            if (!$isMatchingPair) {
                echo "$inputString is NOT Balanced." . PHP_EOL;
                exit;
            }
        }
    }
    echo "$inputString is Balanced." . PHP_EOL;
}

/**
 * @param string $char1
 * @param string $char2
 * @return bool
 */
function isMatchingPair($char1, $char2)
{
    if ($char1 === ')' && $char2 === '(') {
        return true;
    }
    if ($char1 === '}' && $char2 === '{') {
        return true;
    }
    if ($char1 === ']' && $char2 === '[') {
        return true;
    }
    return false;
}

$inputString = '{ Swatantra (() {} ()) Kumar }';
isBalanced($inputString);
?>

Ответ 10

Это должно быть простое использование стека.

private string tokens = "{([<})]>";        
    Stack<char> stack = new Stack<char>();   

    public bool  IsExpressionVaild(string exp)
    {
        int mid = (tokens.Length / 2)  ;  

        for (int i = 0; i < exp.Length; i++)
        {
            int index = tokens.IndexOf(exp[i]);
            if (-1 == index) { continue; }

            if(index<mid ) stack .Push(exp[i]);
            else 
            {
                if (stack.Pop() != tokens[index - mid]) { return false; }       

            }          

        }
        return true;       

    }

Ответ 11

@indiv ответ хорош и достаточно, чтобы решить проблемы с грамматикой в ​​круглых скобках. Если вы хотите использовать стек или не хотите использовать рекурсивный метод, вы можете посмотреть на python script на github. Это просто и быстро.

BRACKET_ROUND_OPEN = '('
BRACKET_ROUND__CLOSE = ')'
BRACKET_CURLY_OPEN = '{'
BRACKET_CURLY_CLOSE = '}'
BRACKET_SQUARE_OPEN = '['
BRACKET_SQUARE_CLOSE = ']'

TUPLE_OPEN_CLOSE = [(BRACKET_ROUND_OPEN,BRACKET_ROUND__CLOSE),
                    (BRACKET_CURLY_OPEN,BRACKET_CURLY_CLOSE),
                    (BRACKET_SQUARE_OPEN,BRACKET_SQUARE_CLOSE)]
BRACKET_LIST = [BRACKET_ROUND_OPEN,BRACKET_ROUND__CLOSE,BRACKET_CURLY_OPEN,BRACKET_CURLY_CLOSE,BRACKET_SQUARE_OPEN,BRACKET_SQUARE_CLOSE]

def balanced_parentheses(expression):
    stack = list()
    left = expression[0]
    for exp in expression:
        if exp not in BRACKET_LIST:
            continue
        skip = False
        for bracket_couple in TUPLE_OPEN_CLOSE:
            if exp != bracket_couple[0] and exp != bracket_couple[1]:
                continue
            if left == bracket_couple[0] and exp == bracket_couple[1]:
                if len(stack) == 0:
                    return False
                stack.pop()
                skip = True
                left = ''
                if len(stack) > 0:
                    left = stack[len(stack) - 1]
        if not skip:
            left = exp
            stack.append(exp)

    return len(stack) == 0
if __name__ == '__main__':
    print(balanced_parentheses('(()())({})[]'))#True
    print(balanced_parentheses('((balanced)(parentheses))({})[]'))#True
    print(balanced_parentheses('(()())())'))#False