java - Java - 检查给定的 Character[] 是否有匹配的括号

Question

//Given an array of Character consisting of "{[()]}" 
//return true if all parentheses match like above
//return false if all pairs of parentheses expression is say "([{])}" 

public boolean parenthesesMatch(Character [] input) {
    char c1 = '';
    char c2 = '';
    
    for(int i = 0; i < input.length/2; i ++) {
        c1 = input[i];
        c2 = input[input.length-1-i];
        if(c1 == '(') {
           if(c1 + 1 != c2) {
             return false;
           }
        }
        else {
            if(c1+2 != c2) {
               return false;
            }
        }
    }
 return true;
}

我意识到 Character[] 输入不是 char[] 输入，所以使用 ascii 值是行不通的。有什么想法会起作用吗？我应该使用堆栈吗？

标签： java

Answer 1

Use a stack which is LIFO.

Check if character is opening or closing, if it's opening push it onto the stack, if it's closing pop one from the stack and check if the closing character matches the closing brace for the opening brace you have popped.

In the end the stack should be empty if all chars have a matching closing character.

import java.util.Map;
import java.util.Stack;

public class Linter {

    public static boolean lint(char[] input){
        Stack<Character> stack = new Stack<>();
        for (char c: input) {
            if (isOpeningBrace(c)) {
                stack.push(c);
            } else if (isClosingBrace(c)){
                Character poppedChar = stack.pop();

                if (poppedChar == null){
                    return false; // stack is empty, no matching closing character
                }

                if (isNotMatching(poppedChar, c)){
                    return false; // the popped brace is not matching the closing char
                }
            }
        }

        return stack.isEmpty();
    }

    private static boolean isNotMatching(char openingBrace, char closingBrace){
        Map<Character, Character> matching = Map.of(
            '(',')','[',']','{','}'
        );
        return closingBrace != matching.get(openingBrace);
    }

    private static boolean isOpeningBrace(char c){
        Map<Character, Boolean> openingBraces = Map.of(
            '(', true, '[', true, '{', true
        );
        return openingBraces.get(c) != null;
    }

    private static boolean isClosingBrace(char c){
        Map<Character, Boolean> closingBraces = Map.of(
            ')', true, ']', true, '}', true
        );
        return closingBraces.get(c) != null;
    }

}