logo标签列表

Java平衡表达式检查 {[()]}

javastackpseudocode
25

我正在尝试创建一个程序，它以字符串作为参数传递给其构造函数。我需要一个方法来检查字符串是否为平衡的括号表达式。它需要处理 ( { [ ] } ) 中的每个开放符号都需要与其对应的闭合括号配对。例如，用户可以输入 [({})] 这将是平衡的，而 }{ 将是不平衡的。这不需要处理字母或数字。我需要使用栈来完成这个操作。

我得到了这个伪代码，但不知道如何在Java中实现它。任何建议都会很棒。 pseudocode

更新- 抱歉忘记发布我已经做的部分。一开始我使用char，然后我尝试过数组 ... 我不确定该怎么办。

import java.util.*;

public class Expression
{
  Scanner in = new Scanner(System.in);
  Stack<Integer> stack = new Stack<Integer>();



  public boolean check()
  {
    System.out.println("Please enter your expression.");
    String newExp = in.next();
    String[] exp = new String[newExp];
    for (int i = 0; i < size; i++)
    { 


      char ch = exp.charAt(i);
      if (ch == '(' || ch == '[' || ch == '{')
        stack.push(i);
      else if (ch == ')'|| ch == ']' || ch == '}')
      {
        //nothing to match with
        if(stack.isEmpty())
        {  
          return false;
        }
        else if(stack.pop() != ch)
        { 
          return false;
        } 

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


}
1
伪代码算法看起来很准确，为什么不把你目前的实现发出来呢？ - Jeff Ward
抱歉有些严厉，但你甚至都有伪代码，必须将其翻译成Java。或者至少试一试，自己尝试失败...也许，如果你的问题中有任何努力的迹象 - 如[FAQ]中所述的那样 - 将有助于获得一些帮助，而不是一些陈旧的愤世嫉俗... void main(String[] args...) { //在此处编写代码 }; - ppeterka
我发布了我迄今为止所做的工作，我忘记在开始时发布，非常感谢。 - Jess Anastasio
1
你可以先将循环的索引推入栈中，然后尝试弹出一个字符。你应该使用一个字符栈，并将开放括号推入其中。当你找到一个闭合括号时，弹出栈顶元素并检查它是否正确匹配开放括号，然后继续执行。如果在最后栈为空，则字符串是平衡的。 - Neurax
查看此链接，您将获得更好的理解：http://codereview.stackexchange.com/questions/45916/check-for-balanced-parentheses - pratik deshai
37个回答
1
迟到的文章。
package com.prac.stack;

public class BalanceBrackets {

public static void main(String[] args) {
    String str = "{()}[]";
    char a[] = str.toCharArray();
    System.out.println(check(a));
}

static boolean check(char[] t) {
    Stackk st = new Stackk();
    for (int i = 0; i < t.length; i++) {
        if (t[i] == '{' || t[i] == '(' || t[i] == '[') {
            st.push(t[i]);
        }
        if (t[i] == '}' || t[i] == ')' || t[i] == ']') {
            if (st.isEmpty()) {
                return false;
            } else if (!isMatching(st.pop(), t[i])) {
                return false;
            }
        }
    }

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

static boolean isMatching(char a, char b) {
    if (a == '(' && b == ')') {
        return true;
    } else if (a == '{' && b == '}') {
        return true;
    } else if (a == '[' && b == ']') {
        return true;
    } else {
        return false;
    }
}

}
1

除了Hashmap之外，一种高效的替代方法是使用Deque：

public boolean isValid(String s) 
{
    if(s == null || s.length() == 0)
        return true;

     Deque<Character> stack = new ArrayDeque<Character>();
     for(char c : s.toCharArray()) 
     {
         if(c == '{')
            stack.addFirst('}');

          else if(c == '(')
            stack.addFirst(')');

           else if(c == '[')
              stack .addFirst(']');

            else if(stack.isEmpty() || c != stack.removeFirst())
               return false;
     }
             return stack.isEmpty();
}
我认为检查s == null是没有用的，因为在这种情况下s.length()会抛出异常。 - Animesh Jaiswal
1
在s == null的情况下，它不会到达检查s.length()的条件。这被称为Java中的短路评估，如果操作数是||并且第一个条件本身为真，则它将返回true而不检查其他条件。这就是为什么我们首先检查null条件的原因。 - p_flame
1
这段代码适用于包括括号在内的所有字符组合，例如：
请输入输入内容

{ibrahim[k]}
为真

()[]{}[][]
为真

saddsd] 为假

public class Solution {

    private static Map<Character, Character> parenthesesMapLeft = new HashMap<>();
    private static Map<Character, Character> parenthesesMapRight = new HashMap<>();

    static {
        parenthesesMapLeft.put('(', '(');
        parenthesesMapRight.put(')', '(');
        parenthesesMapLeft.put('[', '[');
        parenthesesMapRight.put(']', '[');
        parenthesesMapLeft.put('{', '{');
        parenthesesMapRight.put('}', '{');
    }

    public static void main(String[] args) {
        System.out.println("Please enter input");
        Scanner scanner = new Scanner(System.in);

        String str = scanner.nextLine();

        System.out.println(isBalanced(str));
    }

    public static boolean isBalanced(String str) {

        boolean result = false;
        if (str.length() < 2)
            return false;
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < str.length(); i++) {

            char ch = str.charAt(i);
            if (!parenthesesMapRight.containsKey(ch) && !parenthesesMapLeft.containsKey(ch)) {
                continue;
            }
            if (parenthesesMapLeft.containsKey(ch)) {
                stack.push(ch);
            } else {
                if (!stack.isEmpty() && stack.pop() == parenthesesMapRight.get(ch).charValue()) {
                    result = true;
                } else {
                    return false;
                }
            }

        }
        if (!stack.isEmpty())
            return result = false;
        return result;
    }
}
1
这是针对该问题的我的实现。该程序允许输入数字、字母和特殊字符，但在处理字符串时会简单地忽略它们。
代码：
import java.util.Scanner;
import java.util.Stack;

public class StringCheck {

    public static void main(String[] args) {
        boolean flag =false;
        Stack<Character> input = new Stack<Character>();
        System.out.println("Enter your String to check:");
        Scanner scanner = new Scanner(System.in);
        String sinput = scanner.nextLine();
        char[] c = new char[15];
        c = sinput.toCharArray();
        for (int i = 0; i < c.length; i++) {
            if (c[i] == '{' || c[i] == '(' || c[i] == '[')
                input.push(c[i]);
            else if (c[i] == ']') {
                if (input.pop() == '[') {
                    flag = true;
                    continue;
                } else {
                    flag = false;
                    break;
                }
            } else if (c[i] == ')') {
                if (input.pop() == '(') {
                    flag = true;
                    continue;
                } else {
                    flag = false;
                    break;
                }
            } else if (c[i] == '}') {
                if (input.pop() == '{') {
                    flag = true;
                    continue;
                } else {
                    flag = false;
                    break;
                }
            }
        }
        if (flag == true)
            System.out.println("Valid String");
        else
            System.out.println("Invalid String");
        scanner.close();

    }

}
1
class ParenthesisChecker
{

public static void main(String[] args) {

    // sample input
    //[{()}]
    // {}{(}))}  -> unbalanced
    //  [{()}{()}]

    Scanner sc = new Scanner(System.in);

    //Reading total number of testcases
    int t= sc.nextInt();

    while(t-- >0)
    {
        //reading the string
        String st = sc.next();
        System.out.println(isBalancedParenthesis(st));
    }
}

//Function to check if brackets are balanced or not.
public static boolean isBalancedParenthesis(String x)
{
    
    String open = "[{(";
    String close = ")}]";

    int n = x.length();

    /*
    
    base case :
    if (n is odd means either opening or closing parenthesis is missing in x ,
        first character of x contains closing parenthesis ,
        last character of x contains opening parenthesis)
            return false
    
     Note: code works fine without this if block.
    */

    /*
    if( n%2 != 0 ||
        close.contains(String.valueOf(x.charAt(0))) ||
            open.contains(String.valueOf(x.charAt(n-1))))
        return false;
    */
    //else {

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

        for (int i = 0; i < n; i++) {
            char ch = x.charAt(i);
            if (open.contains(String.valueOf(ch)))
                bracketStack.push(ch);
            else if (!bracketStack.isEmpty() &&
                        (bracketStack.peek() == '[' && (ch == ']') ||
                        bracketStack.peek() == '{' && (ch == '}') ||
                        bracketStack.peek() == '(' && (ch == ')')))
                bracketStack.pop();
            else
                return false;
        }
        return bracketStack.isEmpty();
    //}
}
}
你好，欢迎来到SO。一般来说，除了提供代码之外，添加某种评论或解释会更好。因此，请[编辑]您的答案并尝试描述它的功能和工作原理。谢谢！ - Fabio says Reinstate Monica
1
请查看代码，详细的描述已经作为注释插入其中。希望对您有所帮助。 - Vinay Gade
1
public static void main(String[] args) {
    
    String exp = "{[()()]()}";
    if(isBalanced(exp)){
        System.out.println("Balanced");
    }else{
        System.out.println("Not Balanced");
    }
    
}

public static boolean isBalanced(String exp){
    Stack<Character> stack = new Stack<Character>();
    
    for (int i = 0; i < exp.length(); i++) {
        char a = exp.charAt(i);
        char b =' ';
        if(!stack.isEmpty()){
            b = stack.peek();
        }
        if(a == '(' || a == '[' || a == '{'){
            stack.push(a);
            continue;
        }
        else if((b == '(' && a == ')') || (b == '[' && a == ']') || (b == '{' && a == '}')){
            stack.pop();
            continue;
        }
        else{
            return false;
        }
    }
    return stack.isEmpty();
}

在这种情况下，堆栈始终是最优先的数据结构，您可以通过考虑时间和空间复杂度来尝试此操作。

0

这里是代码。我已经在Hacker Rank上测试了所有可能的测试用例。

static String isBalanced(String input) {

    Stack<Character> stack = new Stack<Character>();
    for (int i = 0; i < input.length(); i++) {
        Character ch = input.charAt(i);
        if (input.charAt(i) == '{' || input.charAt(i) == '['
                || input.charAt(i) == '(') {
            stack.push(input.charAt(i));
        } else {
            if (stack.isEmpty() 
                    || (stack.peek() == '[' && ch != ']')
                    || (stack.peek() == '{' && ch != '}')
                    || (stack.peek() == '(' && ch != ')')) {
                return "NO";
            } else {
                stack.pop();
            }
        }
    }
    if (stack.empty())
        return "YES";
    return "NO";

}
0
请尝试这个，我已经检查过了。它可以正常工作。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
public class CloseBrackets {
    private static Map<Character, Character> leftChar = new HashMap<>();
    private static Map<Character, Character> rightChar = new HashMap<>();

    static {
        leftChar.put('(', '(');
        rightChar.put(')', '(');
        leftChar.put('[', '[');
        rightChar.put(']', '[');
        leftChar.put('{', '{');
        rightChar.put('}', '{');
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String st = bf.readLine();
        System.out.println(isBalanced(st));
    }

    public static boolean isBalanced(String str) {

        boolean result = false;
        if (str.length() < 2)
            return false;
        Stack<Character> stack = new Stack<>();
        /* For Example I gave input 
         * str = "{()[]}" 
         */

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

            char ch = str.charAt(i);
            if (!rightChar.containsKey(ch) && !leftChar.containsKey(ch)) {
                continue;
            }
            // Left bracket only add to stack. Other wise it will goes to else case 
            // For both above input how value added in stack 
            // "{(" after close bracket go to else case
            if (leftChar.containsKey(ch)) {
                stack.push(ch);
            } else {
                if (!stack.isEmpty()) {
                    // For both input how it performs
                    // 3rd character is close bracket so it will pop . pop value is "(" and map value for ")" key will "(" . So both are same . 
                    // it will return true. 
                    // now stack will contain only "{" , and travers to next up to end.
                    if (stack.pop() == rightChar.get(ch).charValue() || stack.isEmpty()) {
                        result = true;
                    } else {
                        return false;
                    }
                } else {
                    return false;
                }
            }

        }
        if (!stack.isEmpty())
            return result = false;
        return result;
    }
}
0

这可以使用。通过了所有测试。

static String isBalanced(String s) {

    if(null == s){
        return "";
    }

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


    int length = s.length();

    if(length < 2 || length > 1000){
        return "NO";
    }


    for(int i = 0; i < length; i++){
        Character c= s.charAt(i);
        if(c == '(' || c == '{' || c == '[' ){
            bracketStack.push(c);
        } else {
            if(!bracketStack.isEmpty()){
               char cPop = bracketStack.pop();

               if(c == ']' && cPop!= '['){
                  return "NO";
               }

               if(c == ')' && cPop!= '('){
                  return "NO";
               }

               if(c == '}' && cPop!= '{'){
                  return "NO";
               }
            } else{
                return "NO";
            }

        }
    }

    if(bracketStack.isEmpty()){
        return "YES";
    } else {
        return "NO";
    }

}
0

我们正在使用双端队列来快速轻松地查找平衡的字符串。在这里，我们检查字符串是否包含相等数量的闭合和开放这些'（）'，'{}'和'[]'。在此过程中，我们还要检查关闭括号应该在打开括号之后。

import java.util.Deque;
import java.util.LinkedList;
public class TestPattern{

    public static String pattern(String str){
        Deque<Character> deque = new LinkedList<>(); 
    for (char ch: str.toCharArray()) {
    if (ch == '{' || ch == '[' || ch == '(') {
        deque.addFirst(ch);
    } else {
        if (!deque.isEmpty() && ((deque.peekFirst() == '{' && ch == '}')
            || (deque.peekFirst() == '[' && ch == ']')
            || (deque.peekFirst() == '(' && ch == ')'))) {
            deque.removeFirst();
        } else {
            return "Not Balanced";
        }}}return "Balanced";}

// the above method is retur balanced or not balanced string.


     public static void main(String []args){
       
        System.out.println(pattern("{}()"));
          System.out.println(pattern("}({)"));
     }
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接