搜索匹配的括号

Question

所以我的背景不是 CS，我把编程作为一种爱好。无论如何，我需要解决这个问题：给定一个像“([])”这样的表达式，检查这个表达式是否有匹配的括号样式，即匹配“[”和匹配“(”。

我确实知道有解决方案，但这些解决方案涉及堆栈，我还没有了解它。所以我尝试了我自己的，它看起来很像意大利面，但它确实有效。

/* Program to check if parens are balanced */

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

int main(){

  char expr[100] = "[)";

  int roundcounter = 0, squarecounter = 0, i = 0;

  while (expr[i] != '[=10=]') {
    if (expr[i] == '(') {
      roundcounter++;
    }
    else if (expr[i] == ')') {
      roundcounter--;
      if (roundcounter < 0) {
    break;
      }
    }


    if (expr[i] == '[') {
      squarecounter++;
    }
    else if (expr[i] == ']') {
      squarecounter--;
      if (squarecounter < 0) {
    break;
      }
    }

    i++;
  }

  if (roundcounter == 0 && squarecounter == 0) {
    printf("Balanced parenthesis !\n");
  }

  else {
      printf("Unbalaced !\n");      

      /* Error for [ ] */
      if (squarecounter > 0) {
    printf("Missing right square bracket\n");
      }
      else if (squarecounter < 0) {
    printf("Missing left square bracket\n");
      }

      /* Error for ( ) */
      if (roundcounter > 0) {
    printf("Missing right round bracket\n");
      }
      else if (roundcounter < 0) {
    printf("Missing left round bracket\n");
      }
  }
  return 0;
}

基本上，有两个计数器，每个计数器负责比较 () 和 []，如果左括号则增加 (+1)，如果右括号则减少 (-1)。如果 counters = 0 那么我们有余额表达式。

有更好的方法吗？我正在考虑创建一个封闭和开放的字符数组：

char openarr[] = {'[', '('};
char closenarr[] = {']', ')'};

但是我不确定如何进行。我可以遍历 openarr 并说如果 expr[i] 匹配 openarr 然后增加计数器，并对 closearr 执行相同的操作。

但是，由于以下情况，我们仍然需要1个以上的计数器。假设我们有 expr = "[)" 并且只有 1 个计数器，比如 x。

For loop for openarr will pass because: expr[i] has [ element, counter = 1
For loop for closearr will pass because: expr[i] has ) element, counter = 0

expr = "[)"

肯定不是这种情况

请让我知道如何改进它。

Answer 1

不可能在没有堆栈的情况下正确地做到这一点。你这样做的方式不能正确处理嵌套。例如它会错误地接受“[(])”

Answer 2

您的解决方案遇到的问题是您需要记住遇到左括号和方括号的顺序。我建议你只有一个计数器，当你遇到 [ 或 ( 时递增，当你遇到 ] 或 ) 时递减，你有一个数组记录哪种类型计数时遇到的括号。

下面的解决方案保留了一个数组，其中包含当您减少括号计数时需要匹配的括号类型。如果，当您减少括号计数时，它得到了错误类型的括号，那就是不匹配。

    char expr[100] = "[([)][]]";
    char brackets[100]; // In a real application, allocate dynamically to the same length as the string
    int bracketCount = 0;
    for (int i = 0 ; i < 100 || expr[i] == '[=10=]' ; ++i)
    {
        if (expr[i] == '[' || expr[i] == '(') 
        {
            // Record the type of *closing* bracket we expect when we get back
            // down to this bracket count
            brackets[bracketCount] = expr[i] == '[' ? ']' : ')';
            bracketCount++;
        }
        else if (expr[i] == ']' || expr[i] == ')')
        {
            bracketCount--;
            if (bracketCount < 0 || brackets[bracketCount] != expr[i] )
            {
                printf("Unmatched\n");
                return 1;
            }
        }
    }
    if (bracketCount > 0)
    {
        printf("Unmatched\n");
        return 1;
    }
    printf("matched\n");
    return 0;

你看到了：看不到堆栈的解决方案¹。

¹ 好吧我撒谎了，它确实使用了堆栈。数组brackets和intbracketCount形成一个栈

Answer 3

正如已经回答的那样，您需要一个堆栈才能匹配括号本身。这个想法是在括号离开时将括号推入stak（如果你得到一个 [ 你推它，或者如果你遇到一个左边的 ( 你推它）当你找到一个正确的 ] 或 )，然后你在栈的弹出处弹出字符，看它是否与你遇到的相同类型......如果它们是相同类型，那么它们匹配，并且你抛出两个并继续下一个。如果在某个时候你试图从堆栈中弹出并且堆栈为空，或者你到达输入的末尾并且堆栈仍然有一些内容......那么你的括号不平衡，并且你犯了一个错误。让我们用以下输入检查这个算法：

[(])

你的第一个字符是左 [，所以你推它，给你这个堆栈：

当你读取下一个字符时，因为它是一个左 (，你推它，得到这个堆栈：

[(

当下一个字符出现时，]，你弹出你的最后一个字符，得到一个 (，但它们不匹配......你在那个时候失败了。 .. 实际上这是第一个不匹配的字符。

让我们试试另一个例子：

[()]]

首先，你按下 [，然后你按下 (，然后你得到 )，然后弹出 (，得到一个匹配的对。此时栈内容为：

然后你得到下一个字符，一个 ] 与 statck 的顶部匹配（你弹出一个 [，让堆栈为空）当下一个字符到达时（]），你弹出堆栈以匹配 [，但你得到堆栈是空的，所以你发出一个错误信号，告诉你有一个未配对的权利 ] 在输入中。

搜索匹配的括号

Search for matching parenthesis

c

arrays

string

loops

parentheses