java - 使用 Stack 和 HashMap 的格式良好的字符串

Question

格式良好和格式不正确的字符串的示例是:

1.  “A3{DJE(DG[FF]K)WA65}”      - well formed
2.  “BBB[BM98{WJHG]333}”    - Not well formed
3.  “CBY(DDD(WKLP)BEHOP”    - Not well formed

支持的括号是 {}、[] 和 ()

这是我正在尝试做的事情，但由于某种原因它总是返回 false。

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

public class WellFormedStringCheck {



    public static boolean isWellFormed(String input){

        if(input == null) return true;

        Stack<Character> stack = new Stack<>();

        Map<Character,Character> map = new HashMap<Character,Character>();

        map.put('{', '}');
        map.put('(', ')');
        map.put('[', ']');



        for(int i = 0 ; i < input.length(); i++){

                char s = input.charAt(i);

                if(s == '[' || s == '{' || s == '(' )
                    stack.push(s);
                if(s == ']' || s == '}' || s == ')'){

                    if(stack.isEmpty()) return false;

                    if(map.get(s) != stack.pop()); return false;


                }

            }

        if(!stack.isEmpty()) return false;

         return true;


    }

    public static void main(String[] args) {

      System.out.println(isWellFormed("A3{DJE(DG[FF]K)WA65}"));

    }

}

谁能告诉我上述方法有什么问题吗？

Answer 1

您犯了一个愚蠢的错误，您为圆括号、大括号和括号向后 构建了引用映射。以下是您最初构建 map 的方式:

map.put('{', '}');
map.put('(', ')');
map.put('[', ']');

但是您在 map 中查找右圆括号、大括号和方括号，而键实际上是开始字符。这将返回 null 并导致您的方法返回 false。

这是您的方法的完整代码:

public static boolean isWellFormed(String input) {
    if (input == null) return true;

    Stack<Character> stack = new Stack<Character>();
    Map<Character,Character> map = new HashMap<Character,Character>();

    map.put('}', '{');
    map.put(')', '(');
    map.put(']', '[');

    for (int i=0; i < input.length(); i++) {
        char s = input.charAt(i);

        if (s == '[' || s == '{' || s == '(') {
            stack.push(s);
        }
        if (s == ']' || s == '}' || s == ')') {
            if (map.get(s) != stack.pop()) {
                return false;
            }
        }
    }

    if (!stack.isEmpty()) {
        return false;
    }
    else {
        return true;
    }
}

我使用 IntelliJ 中的这一更改测试了您的代码，它似乎可以正常运行。