给定入栈序列，判断出栈序列是否合法 Java

思路：

使用栈模拟整个过程，遍历入栈序列，每次将一个数入栈。然后判断栈顶元素是否等于出栈序列的第一个元素，如果相等则弹出栈顶元素和出栈序列的第一个元素；否则继续入栈。最后判断栈是否为空，若为空则说明出栈序列合法。

Java 代码实现：

import java.util.*;

public class Solution {
    public boolean isPopOrder(int[] pushA, int[] popA) {
        if (pushA == null || popA == null || pushA.length != popA.length) {
            return false;
        }
        Stack<Integer> stack = new Stack<>();
        int i = 0, j = 0;
        while (i < pushA.length) {
            stack.push(pushA[i++]);
            while (!stack.isEmpty() && stack.peek() == popA[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }
}

相关问题

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

在Java中，可以设计一个栈（Stack）数据结构，并利用它的特性来判断给定的字符串`str`是否表示了有效的栈操作序列。这里我们可以使用一个布尔变量来跟踪栈的状态，初始状态为`true`，代表栈为空。然后遍历字符串`str`，对于每一个字符：

1. 如果字符是'I'（入栈），检查当前栈是否已满（如果已经满了，那么这个序列就是无效的）。如果栈不满，则将状态置为`true`。
2. 如果字符是'O'（出栈），先检查栈是否非空，因为出栈需要有元素存在。如果栈不为空，弹出栈顶元素并将状态保持为`true`；如果栈为空，说明出栈操作在无元素的情况下发生，所以序列无效，将状态置为`false`。

遍历完成后，如果状态仍然是`true`，说明所有的O操作都有对应的I操作，并且栈在最后是空的，因此`str`是合法的。反之，如果状态变为`false`，则`str`是非法的。

以下是简单的Java代码实现：

public class StackChecker {
    private boolean isValid = true;

    public boolean isValidSeq(String str) {
        Stack<Character> stack = new Stack<>();
        for (char c : str.toCharArray()) {
            if (c == 'I') {
                if (!stack.isEmpty()) {
                    isValid = false;
                    break;
                }
                stack.push('I');
            } else if (c == 'O') {
                if (stack.isEmpty()) {
                    isValid = false;
                } else {
                    stack.pop();
                }
            }
        }
        return isValid && stack.isEmpty();
    }

    // 

写一份用java判断括号合法性的代码

### 回答1：

public static boolean isValidBrackets(String str) {
Stack<Character> stack = new Stack<Character>();
char c;
for(int i=0; i<str.length(); i++) {
c = str.charAt(i);
if(c=='(' || c=='[' || c=='{') {
stack.push(c);
} else if(c==')' || c==']' || c=='}') {
if(stack.isEmpty()) {
return false;
}
char topChar = stack.pop();
if(c==')' && topChar!='(') {
return false;
}
if(c==']' && topChar!='[') {
return false;
}
if(c=='}' && topChar!='{') {
return false;
}
}
}
return stack.isEmpty();
}

### 回答2：
以下是一个用Java编写的判断括号合法性的代码：

import java.util.Stack;

public class BracketValidator {
    public static boolean validate(String input) {
        Stack<Character> stack = new Stack<>();

        for (char c : input.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else if (c == ')' || c == ']' || c == '}') {
                if (stack.isEmpty()) {
                    return false;
                }

                char top = stack.pop();

                if (c == ')' && top != '(') {
                    return false;
                } else if (c == ']' && top != '[') {
                    return false;
                } else if (c == '}' && top != '{') {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String input = "[{()}]"; // 括号序列
        boolean isValid = validate(input);

        if (isValid) {
            System.out.println("括号序列是合法的");
        } else {
            System.out.println("括号序列是非法的");
        }
    }
}

以上代码使用了一个栈数据结构，并遍历输入的括号序列。对于每个字符，如果是左括号，则入栈；如果是右括号，则与栈顶元素比较，如果匹配，则将栈顶元素出栈，否则返回false。最后，如果栈为空，则括号序列是合法的，否则是非法的。

以上代码的时间复杂度为O(n)，其中n是括号序列的长度。

### 回答3：
以下是用Java编写的代码来判断括号的合法性：

import java.util.Stack;

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

        for (char ch : str.toCharArray()) {
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            } else if (ch == ')' || ch == '}' || ch == ']') {
                if (stack.isEmpty()) {
                    return false;
                }

                char top = stack.pop();
                if ((ch == ')' && top != '(') || (ch == '}' && top != '{') || (ch == ']' && top != '[')) {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }

    public static void main(String[] args) {
        String str1 = "{[()]}";
        String str2 = "{[()]}(())";
        String str3 = "{[()]}{]}";
        String str4 = "{[()]}(";

        System.out.println(str1 + " 括号合法性：" + validateParentheses(str1));
        System.out.println(str2 + " 括号合法性：" + validateParentheses(str2));
        System.out.println(str3 + " 括号合法性：" + validateParentheses(str3));
        System.out.println(str4 + " 括号合法性：" + validateParentheses(str4));
    }
}

该代码使用了一个栈来存储左括号，在遍历字符串中的每个字符时，当遇到左括号时，将其压入栈中；当遇到右括号时，将栈顶的字符弹出，并判断弹出的字符与右括号是否匹配。如果栈为空或栈顶字符与右括号不匹配，则说明括号不合法。最后，如果栈为空，则说明括号是合法的。

使用给定的示例字符串进行测试，输出结果如下：

{[()]} 括号合法性：true
{[()]}(()) 括号合法性：true
{[()]}{]} 括号合法性：false
{[()]}( 括号合法性：false

以上代码可以判断给定字符串中的括号是否合法。