栈操作序列合法性验证算法 - Java实现

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

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

import java.util.Stack;

public class StackOperations {

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

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

            if (operation == 'I') {
                stack.push(operation);
            } else if (operation == 'O') {
                if (stack.isEmpty() || stack.peek() != 'I') {
                    return false;
                }
                stack.pop();
            } else {
                return false; // 如果操作序列中包含其他字符，返回false
            }
        }

        return stack.isEmpty(); // 如果栈为空，则操作序列合法，否则不合法
    }

    public static void main(String[] args) {
        String operationSequence = "IOIOIOO";
        boolean isValid = isOperationSequenceValid(operationSequence);
        System.out.println("Operation sequence is valid: " + isValid);
    }
}

在这个算法中，我们使用一个栈来模拟进栈和出栈的操作。遍历操作序列，对于每个字符，如果是'I'，则将其进栈；如果是'O'，则判断栈是否为空以及栈顶元素是否为'I'，如果满足条件，则执行出栈操作；如果不是'I'或'O'，则说明操作序列中包含其他字符，返回false。最后，判断栈是否为空，如果为空，则操作序列合法，否则不合法。

在示例代码中，操作序列为"IOIOIOO"，结果为true，表示操作序列是合法的。