java - 尝试检查括号是否平衡或不平衡

Question

您好，我正在做作业 1-1，但我在这个作业上遇到了困难。当我在作业中提交下面的代码并输入 = [] 时，它在应该返回输出时返回输出 = 0 = 成功。知道我做错了什么吗。

下面的程序应该检查字符串是否有 balanced brackets或不，应该返回结果。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;

class Bracket {
    Bracket(char type, int position) {
        this.type = type;
        this.position = position;
    }

    boolean Match(char c) {
        if (this.type == '[' && c == ']')
            return true;
        if (this.type == '{' && c == '}')
            return true;
        if (this.type == '(' && c == ')')
            return true;
        return false;
    }

    char type;
    int position;
}

class check_brackets {
    public static void main(String[] args) throws IOException {
        InputStreamReader input_stream = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(input_stream);
        String text = reader.readLine();

        int pos = 0;

        Stack<Bracket> opening_brackets_stack = new Stack<Bracket>();
        for (int position = 0; position < text.length(); ++position) {
            char next = text.charAt(position);

            if (next == '(' || next == '[' || next == '{') {
                // Process opening bracket, write your code here
                Bracket tmp = new Bracket(next, position);

                opening_brackets_stack.push(tmp);
                break;

            }

            if (next == ')' || next == ']' || next == '}') {
                // Process closing bracket, write your code here
                Bracket item = opening_brackets_stack.pop();

                if (!item.Match(next)) {
                    pos = position + 1;
                    break;
                }
            }
        }

        // Printing answer, write your code here
        if (pos == 0 && opening_brackets_stack.isEmpty()) {
            System.out.println("Success");
        } else {
            if (pos == 0) {
                while (opening_brackets_stack.size() > 1)
                    opening_brackets_stack.pop();
                pos = opening_brackets_stack.peek().position;
            }
            System.out.println(pos);
        }
    }
}

更新的代码:

public class check_brackets {

    public static void main(String[] args) throws IOException {
        InputStreamReader input_stream = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(input_stream);
        String text = reader.readLine();

        Stack<Bracket> opening_brackets_stack = new Stack();
        //traverse the string
        for(int position=0;position<text.length();position++) {
            //Get current char
            char current = text.charAt(position);
            //if the current char is starting bracker,then push it to stack
            if(current=='(' || current=='[' || current=='{') {

                Bracket pos = new Bracket(current,position);

                opening_brackets_stack.push(pos);
            }

            if(current==')' || current==']' || current=='}') {

                Bracket newItem = opening_brackets_stack.pop();

                if(!newItem.Match(current)) {  
                    System.out.println(position+1);
                    return;
                }
            }

        }

        if(opening_brackets_stack.isEmpty()) {
            System.out.println("Success");
        }else {
            Bracket item = opening_brackets_stack.pop();

            System.out.println(item.position+1);
        }

    }


}

Answer 1

您在每个位置都打破了循环，而不是需要继续。还将最终检查放在 for 循环之外，

public class check_brackets { public static void main(String[] args) throws IOException {
    InputStreamReader input_stream = new InputStreamReader(System.in);
    BufferedReader reader = new BufferedReader(input_stream);
    String text = reader.readLine();

    int pos = 0;

    Stack<Bracket> opening_brackets_stack = new Stack<Bracket>();
    for (int position = 0; position < text.length(); ++position) {
        char next = text.charAt(position);

        if (next == '(' || next == '[' || next == '{') {
            // Process opening bracket, write your code here
            Bracket tmp = new Bracket(next, position);

            opening_brackets_stack.push(tmp);
            continue;  // continue not break

        }

        if (next == ')' || next == ']' || next == '}') {
            // Process closing bracket, write your code here
            if (opening_brackets_stack.isEmpty()) {  //condition the check if stack is empty
                pos = position + 1;
                break;
            }
            // Process closing bracket, write your code here
            Bracket item = opening_brackets_stack.pop();

            if (!item.Match(next)) {
                pos = position + 1;
                break; 
            }
        }

    }

// Printing answer, write your code here
   if (pos == 0 && opening_brackets_stack.isEmpty())
    System.out.println("Success");
 else
    System.out.println("Failure at position: "+pos);
}
}

更好的解决方案:

private static boolean checkParenthesisMap(String text) {
    Map<Character, Character> brackets = Map.of('{', '}', '(', ')', '[', ']');
    Stack<Character> bracStack = new Stack<>();
    for (int i=0; i<text.length(); i++){
        char c = text.charAt(i);
        if (brackets.containsKey(c))
            bracStack.push(brackets.get(c));
        else if (bracStack.isEmpty() || bracStack.pop() != c)
            return false;
    }
    return bracStack.isEmpty();
}