自定义泛型栈实现布尔表达式合法性验证的栈操作问题求助

1. Peek方法的核心错误 #

你的peek方法逻辑存在两个关键问题：

• 栈的top变量是下一个可插入元素的索引（push操作时先将元素放入stack[top]，再执行top++），因此栈顶元素的实际索引是top-1，而非top。
• 未做空栈判断，空栈时调用peek会返回stack[0]（值为null），不符合栈的规范，应该抛出自定义的EmptyStackException。

修正后的peek方法：

public T peek() {
    if (isEmpty()) {
        throw new EmptyStackException();
    }
    return this.stack[top - 1];
}

2. 代码中其他潜在问题 #

（1）无用且危险的索引访问 #

main方法里的char x = separate.charAt(i);属于冗余代码，还存在数组越界风险：比如循环到i=2时，若当前separate是长度为2的字符串（如"or"），charAt(2)会直接抛出StringIndexOutOfBoundsException，直接删除该行即可。

（2）未处理括号平衡 #

任务要求需检查括号是否平衡，但当前代码完全未处理括号逻辑，需新增一个栈专门处理括号：遇到(入栈，遇到)则弹出栈顶的(；若弹出时栈为空，或最终栈不为空，均说明括号不平衡，表达式非法。

（3）表达式合法性验证逻辑缺失 #

当前代码仅完成了布尔值和运算符的入栈操作，未通过弹栈验证表达式结构是否合法，比如：

• 单目运算符not仅需一个布尔值，双目运算符（and/or/iff/implies）需要两个布尔值
• 运算符与布尔值的顺序是否符合语法规则

3. 修正后的完整示例（含基础合法性检查） #

import java.util.Scanner;

public class MyStack<T> {

    class StackOverFlowException extends RuntimeException{}
    class EmptyStackException extends RuntimeException{}
    
    private T[] stack;
    private int top;
    
    public MyStack(int size) {
        this.stack = (T[]) new Object[size];
        this.top = 0;   
    }
    
    public boolean isEmpty() {
        return this.top == 0;
    }
    
    public boolean isFull() {
        return this.top == stack.length;
    }
    
    public void push(T x) {
        if(top == stack.length) {
            throw new StackOverFlowException();
        }
        this.stack[top] = x;
        top++;
    }
    
    public T pop() {
        if(isEmpty()) {
            throw new EmptyStackException();
        }
        T value = this.stack[--top];
        return value;
    }
    
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return this.stack[top - 1];
    }
    
    public static void main(String[] args) {
        MyStack<String> boolValues = new MyStack<>(100);
        MyStack<String> operators = new MyStack<>(100);
        MyStack<Character> brackets = new MyStack<>(100);
        
        System.out.println("请输入布尔表达式：");
        Scanner scn = new Scanner(System.in);   
        String expression = scn.nextLine();
        String tokens[] = expression.split(" ");
        boolean isValid = true;
        
        for(String token : tokens) {
            token = token.trim();
            if (token.isEmpty()) continue;
            
            // 处理括号
            if (token.equals("(")) {
                brackets.push('(');
            } else if (token.equals(")")) {
                try {
                    brackets.pop();
                } catch (EmptyStackException e) {
                    isValid = false;
                    break;
                }
            } 
            // 处理布尔值
            else if(token.equalsIgnoreCase("true") || token.equalsIgnoreCase("false")) {
                boolValues.push(token);
            } 
            // 处理运算符
            else if(token.equalsIgnoreCase("and") || token.equalsIgnoreCase("or") 
                   || token.equalsIgnoreCase("iff") || token.equalsIgnoreCase("implies")) {
                operators.push(token);
            } else if(token.equalsIgnoreCase("not")) {
                operators.push(token);
            } else {
                isValid = false;
                break;
            }
        }
        
        // 检查括号是否平衡
        if (!brackets.isEmpty()) {
            isValid = false;
        }
        
        // 基于运算符类型验证布尔值数量是否匹配
        if (isValid) {
            int boolCount = 0;
            while (!boolValues.isEmpty()) {
                boolCount++;
                boolValues.pop();
            }
            int opCount = 0;
            int notCount = 0;
            while (!operators.isEmpty()) {
                String op = operators.pop();
                opCount++;
                if (op.equalsIgnoreCase("not")) {
                    notCount++;
                }
            }
            // 公式：布尔值数量 = 双目运算符数量 + 1 + 单目运算符数量
            if (boolCount != (opCount - notCount) + 1 + notCount) {
                isValid = false;
            }
        }
        
        System.out.println(isValid ? "表达式合法" : "表达式非法");
        scn.close();
    }
}

内容的提问来源于stack exchange，提问作者Jose Espinoza