如何在 C 中的字符串中找到平衡? [英] How can I go about finding balance in a string in C?

问题描述

我希望这个程序使用带有push和pop的堆栈实现递归地解决这个问题.我已经完成了 push 和 pop 以及这些功能:

I want this program to recursively solve this using a stack implementation with push and pop. I have the push and pop done, as well as these functions:

用户输入的字符串只能由这些字符组成.任何其他字符，它返回不平衡.

A string the users enter can only be made up of these characters. Any other characters and it returns unbalanced.

'(', ')', '{', '}', '[', ']'

一个平衡字符串的例子是这样的

An example of a balanced string is like this

()
(())
()()
{()()}
[]
[()[]{}]()
etc..

不平衡的字符串如下所示:

An unbalanced string looks like this:

{}}
()[}
[()}
etc..

这是平衡字符串的递归定义:

This is the recursive definition of a balanced string:

1. (BASIS)空字符串是平衡的
2. (NESTING) 如果 s 也是平衡字符串，则 (s)、[s] 和 {s} 是平衡的.
3. (CONCATENATION) 如果 A 和 B 都是字符串，那么 AB 也是平衡的.

我不知道我的基本情况是什么，也不知道如何在递归中实现这一点.我可以没有，但我想学习递归.有什么帮助吗?

I do not know what my base case would be or how to implement this in recursion. I can without but I want to learn recursion. Any help?

推荐答案

这是一个用 C++ 编写的演示程序，您可以将其用作算法并用 C 重写

Here is a demonstrative program written in C++ that you can use as an algorithm and rewrite it in C

#include <iostream>
#include <iomanip>
#include <stack>
#include <cstring>

bool balance( const char *s, std::stack<char> &st )
{
    const char *open  = "({[<";
    const char *close = ")}]>";

    if ( *s == '\0' )
    {
        return st.empty();
    }

    const char *p;

    if ( ( p = std::strchr( open, *s ) ) != nullptr )
    {
        st.push( *s );
        return balance( s + 1, st );
    }
    else if ( ( p = std::strchr( close, *s ) ) != nullptr )
    {
        if ( !st.empty() && st.top() == open[p-close] )
        {
            st.pop();
            return balance( s + 1, st );
        }
        else
        {
            return false;
        }
    }
    else
    {
        return false;
    }
}   

int main() 
{

    for ( const char *s : { 
                            "()", "(())", "()()", "{()()}", "[]", "[()[]{}]()",
                            "{}}", "()[}", "[()}"

                          } )
    {
        std::stack<char> st;

        std::cout <<'\"' << s << "\" is balanced - "
                  << std::boolalpha << balance( s, st )
                  << std::endl;
    }


    return 0;
}

程序输出为

"()" is balanced - true
"(())" is balanced - true
"()()" is balanced - true
"{()()}" is balanced - true
"[]" is balanced - true
"[()[]{}]()" is balanced - true
"{}}" is balanced - false
"()[}" is balanced - false
"[()}" is balanced - false

这篇关于如何在 C 中的字符串中找到平衡?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！