判断栈操作序列是否合法的算法 - Java实现

假设以'I'和'O'分别表示进栈和出栈操作，栈的初态和终态均为空，进栈和出栈的操作序列str可表示为仅由'I'和'O'组成的字符串。设计一个算法判定str是否合法。

下面是一个使用Java编写的算法，用于判断给定的操作序列str是否合法：

import java.util.Stack;

public class StackOperations {
    public static boolean isValid(String str) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);

            if (c == 'I') {
                stack.push(c);
            } else if (c == 'O') {
                if (stack.isEmpty()) {
                    return false; // 出栈操作时栈为空，不合法
                }
                stack.pop();
            } else {
                return false; // 除了'I'和'O'之外的字符，不合法
            }
        }

        return stack.isEmpty(); // 所有操作序列处理完毕后，栈为空才合法
    }

    public static void main(String[] args) {
        String str1 = "IOIOIO"; // 合法操作序列
        String str2 = "IOOIOO"; // 不合法操作序列

        System.out.println(isValid(str1)); // 输出: true
        System.out.println(isValid(str2)); // 输出: false
    }
}

在上面的代码中，我们使用一个Stack来模拟栈的操作。遍历操作序列str的每个字符，如果是'I'则表示进栈操作，将字符压入栈中；如果是'O'则表示出栈操作，从栈中弹出一个字符。如果遍历完所有字符后，栈为空，则操作序列合法，否则不合法。