代码之家 › 专栏 › 技术社区 › Werokk

检查括号是否匹配总是说它们匹配

java

Werokk · 技术社区 · 6 年前

这是我编写的函数,从输入缓冲区获取输入。但是,对于第二个测试用例,我只是继续收到yes,而不是yes NO yes,但是其他两个用例是正确的。

static String[] braces(String[] values) {
Stack<Character> st = new Stack<Character>();
String[] answer = new String[values.length];
for(int i =0; i<values.length;i++){
  char[] crt = values[i].toCharArray();
  for(char c : crt){
    switch(c){
      case '{':
      case '(':
      case '[':
        st.push(c);
        break;
      case '}':
        if(st.isEmpty() || (st.peek() != '{'))
        {
          answer[i]= "NO";
            break;
        }
        st.pop();

      case ')':
        if(st.isEmpty() || (st.peek() != '('))
        {
          answer[i]= "NO";
            break;
        }
        st.pop();


      case ']':
        if(st.isEmpty() || (st.peek() != '['))
        {
          answer[i]= "NO";
            break;
        }
        st.pop();


    }
  }


  if(st.isEmpty() && answer[i].equals("NO") ){
    answer[i]="YES";
    System.out.println("I set answer[" + i + "] = YES due to stack being empty");
  }
  else
  {
    answer[i]="NO";
    System.out.println("I set answer[" + i + "] = NO due to stack being non-empty");
  }
          st.clear();
}
return answer;

}

5 回复 | 直到 6 年前

zhh 6 年前

改变 stack.firstElement() 到 stack.peek() ,则需要堆栈顶部而不是第一个元素。( firstElement Stack 方法)

that other guy 6 年前

StackOverflow的最大秘密是,它实际上并没有像Neo看待矩阵那样,满脑子都是研究代码的大师。只是人们在研究你的程序是如何运行的。

你可以自己做,最古老和最琐碎的方法是通过所谓的“打印调试”。

应该正在做。这是您的代码,添加了这样的打印语句:

import java.util.*;

public class Test {
  static String[] braces(String[] values) {
    Stack<Character> st = new Stack<Character>();
    String[] answer = new String[values.length];
    for(int i =0; i<values.length;i++){
      char[] crt = values[i].toCharArray();
      boolean an = false;
      for(char c : crt){
        switch(c){
          case '{':
          case '(':
          case '[':
            st.push(c);
            break;
          case '}':
            if(st.isEmpty() || (st.firstElement() != '{'))
            {
              answer[i]= "NO";
              System.out.println("I set answer[" + i + "] = NO due to mismatched }");
            }
            st.pop();
            break;

          case ')':
            if(st.isEmpty() || (st.firstElement() != '('))
            {
              answer[i]= "NO";
              System.out.println("I set answer[" + i + "] = NO due to mismatched )");
            }
            st.pop();
            break;

          case ']':
            if(st.isEmpty() || (st.firstElement() != '['))
            {
              answer[i]= "NO";
              System.out.println("I set answer[" + i + "] = NO due to mismatched ]");
            }
            st.pop();
            break;

        }
      }

      if(st.isEmpty()){
        answer[i]="yes";
        System.out.println("I set answer[" + i + "] = YES due to stack being empty");
      }
      else
      {
        answer[i]="no";
        System.out.println("I set answer[" + i + "] = NO due to stack being non-empty");
      }
      st.clear();
    }

    return answer;
  }
  public static void main(String[] args) {
    String[] result = braces(new String[] { "(foo}" });
    for(String s : result) System.out.println("The final result is " + s);
  }
}

(foo} :

I set answer[0] = NO due to mismatched }
I set answer[0] = YES due to stack being empty
The final result is yes

嗯,你好像在改写你以前的答案。您应该确保最终测试不会覆盖循环的结论。

最简单的办法就是检查 answer[i] 为空,但更好的方法是创建第二个helper方法 boolean braces(String) 那是免费的 return true 或 false 在任何时候,然后在 braces(String[])

无论如何,这是我的实现:

import java.util.Stack;

class Test {
  static char flip(char c) {
    switch(c) {
      case '}': return '{';
      case ')': return '(';
      case ']': return '[';
      default: throw new IllegalArgumentException("Invalid paren " + c);
    }
  }

  static boolean matched(String value) {
    Stack<Character> st = new Stack<Character>();
    for (int i=0; i<value.length(); i++) {
      char c = value.charAt(i);
      switch(c) {
          case '{':
          case '(':
          case '[':
            st.push(c);
            break;

          case '}':
          case ')':
          case ']':
            if (st.isEmpty() || st.peek() != flip(c)) {
              return false;
            }
            st.pop();
            break;
      }
    }
    return st.isEmpty();
  }

  static String[] braces(String[] values) {
    String[] result = new String[values.length];
    for(int i=0; i<result.length; i++) {
      result[i] = matched(values[i]) ? "yes" : "no";
    }
    return result;
  }

  public static void main(String[] args) {
    String[] input = new String[] { "}", "{}", "{()}", "asdf", "", "{[", "{[[([])]]}", "((foo))" };
    String[] actual = braces(input);
    String[] expected = new String[] { "no", "yes", "yes", "yes", "yes", "no", "yes", "yes" };
    for(int i=0; i<actual.length; i++) {
      if(!actual[i].equals(expected[i])) {
        System.out.println("Failed: " + input[i] + " should have been " + expected[i]);
        System.exit(1);
      }
    }
    System.out.println("OK");
  }
}

user1373164 6 年前

import java.util.*;
import java.util.stream.Collectors;

public class Test {

    static final Map<Character, Character> PARENS;
    static final Set<Character> CLOSING_PARENS;
    static {
        PARENS = new HashMap<>();
        PARENS.put('{', '}');
        PARENS.put('[', ']');
        PARENS.put('(', ')');
        CLOSING_PARENS = new HashSet<>(PARENS.values());
    }

    public static void main(String[] args) {

        print(braces("(foo}","[]","()","{}","[{}]","([{}])","[[]]"));
        print(braces("[","]","][","[{]}"));

        // test case 2 ...

        print(braces("{[()]}","{[(])}","{{[[(())]]}}"));

        // ... prints YES NO YES  ...
    }

    static void print(String ... values){
        for(String str : values){
            System.out.print(str + " ");
        }
        System.out.println();
    }

    static String [] braces(String ... values) {
        return Arrays.stream(values)
                .map(Test::isBalanced)
                .map(b -> b ? "YES" : "NO")
                .collect(Collectors.toList()).toArray(new String[values.length]);
    }

    static boolean isBalanced(String token){

        Stack<Character> stack = new Stack<>();
        for(char c : token.toCharArray()){

            if (PARENS.keySet().contains(c)){

                stack.push(c);

            } else if(CLOSING_PARENS.contains(c)){

                if(stack.isEmpty() || !PARENS.get(stack.pop()).equals(c)) {
                    return false;
                }
            }
        }

        return stack.isEmpty();

    }

}

The Scientific Method 6 年前

你只需要做以下改变

firstElement() 具有 peek() 在所有情况下
```
      stack.pop();
      break;
```
1. 检查stack在最后一种情况下是否是empity
如果(!stack.isEmpty())

更正代码:

public class ParenMatch{

    public static void main(String[] args){
    String[] str = { "{}[](){[}]","{[()]}{[(])}{{[[(())]]}}","", "}][}}(}][))][](){()}()({}([][]))[](){)[](}]}]}))}(())(([[)"}; 
    System.out.println(Arrays.toString(braces(str)));
    }

public static String[] braces(String[] values)
{
    Stack<Character> stack = new Stack<Character>();
    String[] isCorrect = new String[values.length];
    for (int i = 0; i < values.length; i++)
    {
        char[] crt = values[i].toCharArray();
        boolean an = false;
        for (char c : crt)
        {
            switch(c)
            {
                case '{':
                case '(':
                case '[':
                    stack.push(c);
                    break;
                case '}':
                    if (stack.isEmpty() || (stack.peek() != '{'))
                    {
                        isCorrect[i] = "NO";
                    }
                    //stack.pop();
                    //break;

                case ')':
                    if (stack.isEmpty() || (stack.peek() != '('))
                    {
                        isCorrect[i] = "NO";
                    }
                    //stack.pop();
                    //break;

                case ']':
                    if (stack.isEmpty() || (stack.peek() != '['))
                    {
                        isCorrect[i] = "NO";
                    }
                    if(!stack.isEmpty())
                    stack.pop();
                    break;
            }
        }
        if (stack.isEmpty())
        {
            isCorrect[i] = "yes";
        }
        else
        {
            isCorrect[i] = "no";
        }
        stack.clear();
    }

    return isCorrect;
}
}

String[] str = { "{}[](){[}]","{[()]}{[(])}{{[[(())]]}}","", "}][}}(}][))][](){()}()({}([][]))[](){)[](}]}]}))}(())(([[)"};

输出:

[是的,是的,是的,不是]

Werokk 6 年前

static String[] braces(String[] values) {
    Stack<Character> st = new Stack<Character>();
     String []answer = new String[values.length];
     Boolean isCorrect = false;

    for(int i =0; i< values.length;i++)
     {
         isCorrect = true;
        st.clear();
         char crt[] = values[i].toCharArray();

        for(char c : crt)
         { 
             switch(c)
             {
             case'{':
             case'[':
             case'(':
                 st.push(c);
                 break;

                 case'}':
                 if(st.isEmpty() || st.peek() != '{')
                 {
                     System.out.println("Hellooo");
                     answer[i] ="NO";
                     isCorrect = false;
                 }
                 if(!st.isEmpty()) 
                 {
                    st.pop();
                 }
                 break;

                 case']':
                 if(st.isEmpty() || st.peek() != '[')
                 { 
                     System.out.println("Hell");
                     answer[i] ="NO";
                     isCorrect = false;
                 }
                 if(!st.isEmpty()) 
                 {
                     st.pop();
                }

                 break;

                case')':
                 if(st.isEmpty() || st.peek() != '(')
                 {
                     isCorrect = false;
                 }

                 if(!st.isEmpty()) {

                     st.pop();

                     }

                 break;
             }
         }

         if(isCorrect && st.isEmpty())

         {
             answer[i] = "YES";
             System.out.println("Hello");
         }else answer[i] = "NO";
     }
    return answer;
}