2705:扩号匹配问题（递归与非递归）

扩号匹配问题是指在一个字符串中，括号是否匹配的问题。例如，字符串 "((()))" 中的括号是匹配的，而字符串 "(()))" 中的括号是不匹配的。

解决这个问题有两种常见的方法：递归和非递归。

递归方法的思路是，遇到左括号 "(" 就将其入栈，遇到右括号 ")" 就将栈顶元素出栈，并检查是否与当前右括号匹配。如果匹配，则继续扫描字符串；如果不匹配，则返回 false。最后，如果栈为空，则说明所有括号都匹配，返回 true；如果栈不为空，则说明左括号比右括号多，返回 false。

非递归方法的思路是，遍历字符串中的每个字符，遇到左括号就将其入栈，遇到右括号就将栈顶元素出栈，并检查是否与当前右括号匹配。如果匹配，则继续扫描字符串；如果不匹配，则返回 false。最后，如果栈为空，则说明所有括号都匹配，返回 true；如果栈不为空，则说明左括号比右括号多，返回 false。

两种方法的时间复杂度都是 O(n)，其中 n 是字符串的长度。但是递归方法由于需要使用递归函数，会占用更多的栈空间。因此，在实际应用中，非递归方法更常用。

相关问题

递归下降语法分析程序的设计与实现

递归下降语法分析程序是一种自顶向下的语法分析方法，它通过递归地向下分析输入的语法单元，最终确定输入是否符合给定的语法规则。下面是递归下降语法分析程序的设计与实现步骤：

1. 根据给定的文法规则，将其转换为一个递归下降语法分析程序的形式。

2. 对于每个非终结符，编写一个相应的递归函数，用于分析该非终结符所对应的语法单元。

3. 对于每个终结符，编写一个相应的函数，用于匹配该终结符。

4. 在递归函数中，按照文法规则的顺序调用其他递归函数或终结符匹配函数，以分析输入的语法单元。

5. 如果输入的语法单元符合文法规则，则返回true，否则返回false。

6. 在主函数中，调用文法规则的起始非终结符的递归函数，以开始语法分析过程。

下面是一个简单的递归下降语法分析程序的例子，用于分析一个简单的四则运算表达式：

# 定义终结符匹配函数
def match(token):
    global lookahead
    if lookahead == token:
        lookahead = next_token()
        return True
    else:
        return False

# 定义递归函数
def expr():
    global lookahead
    if term():
        while lookahead in ['+', '-']:
            if match('+'):
                if not term():
                    return False
            elif match('-'):
                if not term():
                    return False
        return True
    else:
        return False

def term():
    global lookahead
    if factor():
        while lookahead in ['*', '/']:
            if match('*'):
                if not factor():
                    return False
            elif match('/'):
                if not factor():
                    return False
        return True
    else:
        return False

def factor():
    global lookahead
    if lookahead.isdigit():
        return match(lookahead)
    elif match('('):
        if not expr():
            return False
        if not match(')'):
            return False
        return True
    else:
        return False

# 主函数
def main():
    global lookahead
    lookahead = next_token()
    if expr() and lookahead == '$':
        print("Valid expression")
    else:
        print("Invalid expression")

# 测试用例
test_case = "2+3*4$"
next_token = iter(test_case).__next__
lookahead = None
main()

递归下降yu法分析程序

递归下降法是一种语法分析方法，通过递归的方式从上到下分析输入的语法结构。它通常用于解析简单的语法，例如算术表达式或条件语句。

编写递归下降法分析程序时，首先需要定义文法规则，包括终结符和非终结符，然后编写与每个非终结符相关的递归函数。递归函数用于分析语法规则中的每个部分，并根据输入的符号进行相应的处理。

对于每个非终结符，递归下降法程序会首先匹配输入的终结符，然后调用递归函数去处理与该非终结符相关的语法规则。递归函数会递归地调用自身，直到分析完整个语法结构或者发现语法错误。

在编写递归下降法分析程序时，需要考虑文法的歧义性和左递归的处理方法，以及避免产生无限递归的情况。此外，还需要处理错误情况，例如发现不符合语法规则的输入。

递归下降法分析程序的编写过程需要考虑语法规则的复杂性和结构的清晰性，以便有效地分析各种输入情况。通过递归下降法分析程序，可以有效地验证输入的字符串是否符合给定的语法规则，并将其转化为相应的语法树或其他数据结构。