java - 尝试实现堆栈和括号匹配问题，但无法找出一些语义错误

Question

我需要使用数组编写自己的堆栈，然后我必须实现括号匹配问题。

这是我的算法:如果我们给出字符串:“(())”，当它应该说它是“平衡”时，它会返回“不平衡”。如果您查看靠近末尾的 BracketCheck.java，它会测试堆栈是否为空，如果是，则应返回 true 并表示给定的字符串:“(())”是平衡的。我在调试时遇到问题，操作结果不正确。

这是我的堆栈和主类代码:

public class Stack {
        // instance fields:
        private char array[]; // our array
        private int topOfStack; // this indicates the value for each position

        // overloaded constructor:
        public Stack(int size) {
            this.array = new char[size]; // here we instantiate a new char type array.
            this.topOfStack = -1; // we set the starting position of the topOfStack to -1.
        }
        // push method:
        public void push(char character) {
            if(isFull() == true) {
                System.out.println("Stack overflow error.");
            }
            else {
                topOfStack++;
                array[topOfStack] = character;
            }
        }
        // pop method:
        public char pop() {
            if(isEmpty() == true) {
                //System.out.println("Overflow.");
                return '\0';
            }
            else {
                char c = array[topOfStack];
                topOfStack--;
                return c;
            }

        }
        // top method:
        public int top() {
            if(isEmpty() == true) {
                System.out.println("The stack is empty.");
                return 0;
            }
            else {
                return array[topOfStack]; // returns the top element in the stack.
            }
        }
        // size method:
        public int size() {
            return topOfStack + 1;
        }

        // isEmpty method:
        public boolean isEmpty() {
            if(topOfStack == -1) {
                return true;
            }
            else {
                return false;
            }
        }
        // isFull method:
        public boolean isFull() {
            if(topOfStack == array.length -1 ) {
                System.out.println("Stack if full.");
                return true;
            }
            else {
                return false;
            }
        }

BracketCheck.java

 public class BracketCheck {
    public static void main(String args[]) {
        String text = "(())";
        //boolean check = isBalanced(text);

        if(isBalanced(text) == true) {
            System.out.println("Balanced.");
        }
        else {
            System.out.println("Not balanced");
        }
    }   
    public static boolean isBalanced(String text) {
        Stack stack = new Stack(25); // for simplicity our stack is going to be a size of 25.

        char[]arr = text.toCharArray(); // convert our string to a set of characters in an array.
        // here we are looping through our text
        for(int i = 0; i < arr.length; i++) {
            if(arr[i] == '{' || arr[i] == '(' || arr[i] == '[') {
                stack.push(arr[i]);
            }
            else if(arr[i] == '}' || arr[i] == ')' || arr[i] == ']') {
                if(stack.isEmpty()) {
                    return false; // if empty then return false.
                }
                else if((stack.pop() == '(' && arr[i] != ')') || (stack.pop() == '{' && arr[i] != '}') || (stack.pop() == '[' && arr[i] != ']')) {
                    return false; // here we return false because this tells us that there is a mismatch and not balanced. Also if we did pop out the brace and it was equal
                                  // to it's corresponding closing brace then it will just continue the loop other return false to indicate it is unbalanced.
                }
            }
        }
        if(stack.isEmpty()) {
            return true; // after looping through the text if the stack turns out to be empty then this shows that there the text is balanced indeed because
        }
        else {
            return false; 
        }
    }
}

Answer 1

在这种情况下

else if((stack.pop() == '(' && arr[i] != ')') || (stack.pop() == '{' && arr[i] != '}') || (stack.pop() == '[' && arr[i] != ']')) {

您弹出 3 次，因此您从堆栈中提取了 3 个不同的元素。要修复此问题，请弹出一次并将弹出的元素保存在局部变量中:

if(stack.isEmpty()) {
    return false; // if empty then return false.
}
else {
    char element = stack.pop();
    if((element  == '(' && arr[i] != ')') || (element  == '{' && arr[i] != '}') || (element  == '[' && arr[i] != ']')) {
        return false;
    }
}