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

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

下面是一个用Java实现的算法来判断给定的操作序列是否合法：

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 str = "IOIOOIOO";
        System.out.println(isValid(str)); // 输出true
        
        str = "IIIOOO";
        System.out.println(isValid(str)); // 输出false
    }
}

在这个算法中，我们使用一个栈来模拟进栈和出栈的操作。遍历给定的操作序列字符串，对于每个字符，如果是'I'，则将其压入栈中；如果是'O'，则检查栈是否为空，如果为空则返回false，否则弹出栈顶元素；如果字符既不是'I'也不是'O'，则认为是非法字符，返回false。最后，如果栈为空，则操作序列合法，返回true；否则，返回false。