编写递归代码来查找字符串中不匹配的括号？

Question

我目前正在 SystemVerilog 中编写一些代码，以查找字符串中匹配的括号。该代码采用一个名为

str

的数组，其中包含

n

个字符，每个字符长 4 个字节。该字符串将包含左括号、右括号和其他任意字符，例如空格或句点。我已经有一个工作代码可以非递归地执行此操作：

module pmatch_comb_base
  #( int n = 5, wn = $clog2(n) )
   ( output logic [wn-1:0] left_out_n_unmat_close, right_out_n_unmat_open,
     input uwire [3:0] str[0:n-1] );

   always_comb begin

      left_out_n_unmat_close = 0;
      right_out_n_unmat_open = 0;

      // Scan string from left to right. (Leftmost character is at i=0.)
      for ( int i=0; i<n; i++ )

        if ( str[i] == Char_Close ) begin

           // We've found a closing parenthesis, ")".

           if ( right_out_n_unmat_open > 0 )
             right_out_n_unmat_open--;  // It matches an opening parenthesis.
           else
             left_out_n_unmat_close++;  // It's unmatched, update the count.

        end else if ( str[i] == Char_Open ) begin

           // We've found an opening parenthesis, "(".

           // Increment the count of unmatched open parentheses ..
           right_out_n_unmat_open++;
           // .. which might be decremented in a later iteration.

        end
   end

endmodule

我将如何递归地执行此操作？我发现很难准确地弄清楚如何使用递归方法来模拟上述逻辑。对于某些示例，如果字符串看起来像“))((”，则输出的值应为 open = 2 和 close = 2、“(())”、“()()”和“(()( ))" 应该给出 open = 0 和 close = 0，而 "(. ())(" 应该给出 open = 1 和 close = 0。

我首先尝试制作

n

等于 1 的基本情况。然后我制作了另一种情况，使用新变量和参数 lo 和 hi 将字符数

n

分成两个，然后递归调用模块包含这两部分，最后计算总匹配数和剩余数，但这样做总是给我带来错误，这就是我对该方法的逻辑感到困惑的地方。

Answer 1

递归调用模块

Verilog

module

表示硬件组件，例如移位寄存器或 ALU。 您实际上并不“调用”一个模块，而是像在 PCB 上放置一个模块实例一样。

更好的方法是递归调用

function

。 请参阅 IEEE Std 1800-2023 第 13.4.2 节静态和自动功能。 有一个阶乘

function

的代码示例演示了原理。