java - 检查每个 if 是否都有匹配的 endif

Question

我最近不得不为比特币的脚本语言编写一个解释器；其中一部分涉及提出一种算法来检查给定脚本中的控制流是否有意义(即每个 OP_IF 都有一个匹配的 OP_ENDIF，每个 OP_ELSE 和 OP_ENDIF 有匹配的 OP_IF 等)。

这是我想出的:

public class if_else_checker {

public static boolean search(String[] commands, String[] tracker, int if_index) {
    boolean seenElse = false;
    for (int i = if_index; i < commands.length; i++) {
        if (commands[i].equals("OP_ELSE")) {
            if (seenElse == true && tracker[i] == null) return false;
            if (tracker[i] == null) {
                tracker[i] = "OP_ELSE";
                seenElse = true;
            }
        }

        else if (commands[i].equals("OP_ENDIF")) {
            if (tracker[i] != null && tracker[i].equals("OP_ENDIF")) 
            {
                continue;
            }
            tracker[i] = "OP_ENDIF";
            return true;
        }

        else if (commands[i].equals("OP_IF")) {
            if (tracker[i] != null && tracker[i].equals("OP_IF")) {
                continue;
            }
            tracker[i] = "OP_IF";
            if (search(commands, tracker, i + 1) == false) return false;
        }
    }

    return false;
}

public static boolean validate(String[] args) 
{
    String[] tracker = new String[args.length];

    for (int i = 0; i < args.length; i++) 
    {
        if (args[i].equals("OP_IF")) 
        {
            if (tracker[i] == null || !tracker[i].equals("OP_IF")) 
            {
                tracker[i] = "OP_IF";
                if (search(args, tracker, i + 1) == false) return false;
            }

            else continue;
        }

        else if (args[i].equals("OP_ELSE"))
        {
            if (tracker[i] == null || !tracker[i].equals("OP_ELSE")) return false;
        }

        else if (args[i].equals("OP_ENDIF"))
        {
            if (tracker[i] == null || !tracker[i].equals("OP_ENDIF")) return false;
        }
    }

    return true;
}

public static void main(String[] args)
{
    System.out.println(validate(args));
}

它有效，但我想知道是否有优化它的方法/是否有执行此操作的标准方法？ (一种优化是让 validate() 返回它找到的 OP_ENDIF 的索引，而不是 boolean 值；这会将运行时间从二次时间更改为线性时间)。

Answer 1

解决这个问题的最好方法是使用 Stack 数据结构。每条新的打开指令(例如 OP_IF)都被压入堆栈。当您找到关闭指令(例如 OP_ENDIF)时，您弹出堆栈的顶部元素并检查它是否是该关闭指令的相应打开指令。如果是这样，那么它是有效的，你继续下一步。最后，如果堆栈为空，则您正在检查的控制流是正确的。否则，它不是。