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个回答
0
我称之为暴力类型的方法，我们将字符串中的每个()、{}或[]替换为""，因此字符串的长度会减少，如果字符串的长度不变，则我只是打破循环，否则如果字符串的长度降至0，则意味着字符串中的所有内容都是平衡的，否则就不是。
public class Question{
public static void main(String[] args) {
    String target="{ [ ( ) ] }",target2="( ) [ ] { }",target3="[ ( ) ] ( ( ) )",target4="( { [ )";
    target=target.replaceAll(" ","");
    target2=target2.replaceAll(" ", "");
    target3=target3.replaceAll(" ", "");
    target4=target4.replaceAll(" ", "");
    System.out.println(CheckExp(target));
    System.out.println(CheckExp(target2));
    System.out.println(CheckExp(target3));
    System.out.println(CheckExp(target4));
}
public static Boolean CheckExp(String target) {
    boolean flag = false;
    if (target.length() < 2 || target.length()%2!=0 ) {
        return flag;
    }
    int first,last;
    while(true) {
        first=target.length();
            target = target.replace("()", "");
            target = target.replace("{}","");
            target = target.replace("[]","");
            last=target.length();
            if(first==last)
                break;
            flag= target.length() == 0;
    }
    return flag;
}

}

0

平衡括号 我在一次技术面试中遇到了这个问题。应该仅使用数组来解决。 JAVA

public class Test1 {
        public static void main(String[] args) {
            
            String arr = "()()()(((12())1()))()()()"; //true
            //String arr = "()()()(((12())1()))()()("; //false
            System.out.println(isValid(arr)); 
        }
        
        static boolean isValid(String s){
            
            boolean valid;
            char[] array = s.toCharArray();
            char[] tempArray = new char[array.length];
            int parentesisCounter = 0;
            int tempCount = 0;
            
            for( int i = 0, m = 0; i < array.length; i++){
                if( array[i] == '(' || array[i] == ')' ){
                    tempArray[m] = array[i];
                    m++;     
                }
            }
            
            for(int i = 0; i < tempArray.length; i++){
                if( tempArray[i] == '(' || tempArray[i] == ')'){
                    tempCount++;
                }
            }
            
            char[] finalArray = new char[tempCount];
       
            System.arraycopy(tempArray, 0, finalArray, 0, tempCount);
            
            
            int countR = finalArray.length;
            int countL = 0;
            
            if((countR)%2 != 0){               
                return valid = false;
            }else if(finalArray[0] == ')' || finalArray[countR-1] == '(' ){
                return valid = false;
            }
            
            for( int i = 0; i < finalArray.length; i++ ){
                
                if( finalArray[countL] == '(' && finalArray[countL+1] == ')' ){
                   countL+=2;
                   i++;
                   if(countL == countR){
                       return valid = true;
                   }
                }else if( finalArray[countR-1] == ')' && finalArray[countR-2] == '(' ){
                   countR-=2;
                   if(countL == countR){
                       return valid = true;
                   }
                }else if( finalArray[countR-1] == ')' && finalArray[countR-2] == ')' ){
                   countR--;
                   parentesisCounter--;
                   if(countL == countR){
                       return valid = true;
                   } 
                }else if( finalArray[countL] == '(' && finalArray[countL+1] == '(' ){
                   countL++;
                   parentesisCounter++;
                   if(countL == countR){
                       return valid = true;
                   }
                }else if( finalArray[countL] == ')' ){
                   if(countL == countR+1){
                       return valid = true;
                   }
                   parentesisCounter--;
                }
            } 
            if(parentesisCounter == 0){
                valid = true;
            }else valid = false;
            return valid;         
        }   
    }
这个问题很老了，今天已经被认为是不相关的。在Java中，这个问题已经有了几个解决方案。你的解决方案有何不同之处？请阅读[答案]。 - Chris
为什么这会被认为是不相关的话题，@Chris？它与编程密切相关。 - Elikill58
@Elikill58，它没有说明那段代码的问题在哪里。一个主题相关的问题应该解释代码应该如何工作，显示尝试，并清楚地解释代码中的问题，以便答案可以纠正具体的错误。这个问题没有做到这一点，因此吸引了大量毫无价值的“这是我的解决方案”代码转储。SO并不是关于展示你的代码或提供要盲目复制的代码。它是有关帮助用户学习的。仅仅“与编程有关”是不足以成为主题的。请参见[help/on-topic]获取详情。 - Chris
@Chris 哦，是的，你的意思是应该关闭，因为需要更多的关注/细节和清晰度。我以为你在谈论应该在SE网络的另一个站点上的离题问题。 - Elikill58
大家好。感谢您的评论和评价。虽然这个问题已经很老了，但在技术面试中仍然非常相关。我在2021年得到了这个问题，并感到有义务分享它。网络上充满了使用Stack解决方案的内容，但不同数据结构的选择却很少。 - Tim Gertz
0
改进的方法，来自@Smartoop。
public boolean balancedParenthensies(String str) {
    List<Character> leftKeys = Arrays.asList('{', '(', '<', '[');
    List<Character> rightKeys = Arrays.asList('}', ')', '>', ']');

    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        if (leftKeys.contains(c)) {
            stack.push(c);
        } else if (rightKeys.contains(c)) {
            int index = rightKeys.indexOf(c);
            if (stack.isEmpty() || stack.pop() != leftKeys.get(index)) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}
0

利用节点引用，我们可以轻松地进行检查。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;



public class CloseBracketsBalance {
    private static final Map<String, String> closeBracket= new HashMap<>();
    private static final List<String> allBrac = new ArrayList<>();

    static {
        allBrac.add("[");
        allBrac.add("]");
        allBrac.add("{");
        allBrac.add("}");
        allBrac.add("(");
        allBrac.add(")");
        closeBracket.put("]", "[");
        closeBracket.put("}", "{");
        closeBracket.put(")", "(");
    }

    public static void main(String[] args) {
        System.out.println(checkSheetIsbalance("[{}({[]{}(dsfd)})]")); // return true
        System.out.println(checkSheetIsbalance("[{}({[]{}(dsfd}))]")); // return false
    }

    public static boolean checkSheetIsbalance(String c) {
        char[] charArr = c.toCharArray();
        Node node = null;
        for(int i=0,j=charArr.length;i<j;i++) {
            String ch = charArr[i]+"";
            if(!allBrac.contains(ch)) {
                continue;
            }

            if(closeBracket.containsKey(ch)) {
                // node close bracket               
                if(node == null) {
                    return false;
                }
                if(!(node.nodeElement).equals(closeBracket.get(ch))) {
                    return false;
                }
                node = node.parent; 
            } else {
                //make node for open bracket                
                 node = new Node(ch, node);
            }
        }       

        if(node != null) {
            return false;
        }

        return true;
    }
}


class Node {
    public String nodeElement;
    public Node parent;
    public Node(String el, Node p) {
        this.nodeElement = el;
        this.parent = p;
    }
}
0

假设字符串仅包含 '(', ')', '{', '}', '[', ']'。这里提供一个代码方法，根据方程式是否平衡返回 true 或 false。

private static boolean checkEquation(String input) {

    List<Character> charList = new ArrayList<Character>();

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

        if (input.charAt(i) == '(' || input.charAt(i) == '{' || input.charAt(i) == '[') {
            charList.add(input.charAt(i));
        } else if ((input.charAt(i) == ')' && charList.get(charList.size() - 1) == '(')
                || (input.charAt(i) == '}' && charList.get(charList.size() - 1) == '{')
                || (input.charAt(i) == ']' && charList.get(charList.size() - 1) == '[')) {
            charList.remove(charList.size() - 1);
        } else
            return false;

    }

    if(charList.isEmpty())
        return true;
    else
        return false;
}
0
public void validateExpression(){

    if(!str.isEmpty() && str != null){
        if( !str.trim().equals("(") && !str.trim().equals(")")){

            char[] chars = str.toCharArray();

            for(char c: chars){
                if(!Character.isLetterOrDigit(c) && c == '('  || c == ')') {
                    charList.add(c);
                }
            }

            for(Character ele: charList){                   
                if(operatorMap.get(ele) != null && operatorMap.get(ele) != 0){                      
                    operatorMap.put(ele,operatorMap.get(ele)+1);
                }else{
                    operatorMap.put(ele,1);
                }
            }

            for(Map.Entry<Character, Integer> ele: operatorMap.entrySet()){
                System.out.println(String.format("Brace Type \"%s\" and count is \"%d\" ", ele.getKey(),ele.getValue()));                   
            }

            if(operatorMap.get('(') == operatorMap.get(')')){
                System.out.println("**** Valid Expression ****");
            }else{
                System.out.println("**** Invalid Expression ****");
            }

        }else{
            System.out.println("**** Incomplete expression to validate ****");
        }

    }else{
        System.out.println("**** Expression is  empty or null ****");
    }       
}
0

我采用了略微不同的方法来解决这个问题，我观察到了这个问题中的两个关键点。

  1. 开括号应始终与相应的闭括号一起出现。
  2. 不同的开括号可以在一起使用，但不同的闭括号不能。

因此，我将这些要点转化为易于实现和理解的格式。

  1. 我用不同的数字表示不同的括号
  2. 对于开括号给予正数符号，对于闭括号给予负数符号。

例如："{ } ( ) [ ]" 将是 "1 -1 2 -2 3 -3" 是有效的括号。 对于平衡的括号，正数可以相邻，而负数必须在堆栈顶部的正数之上。

以下是代码：

import java.util.Stack;

public class Main {
    public static void main (String [] args)
    {
        String value = "()(){}{}{()}";
        System.out.println(Main.balancedParanthesis(value));
       
    }

public static boolean balancedParanthesis(String s) {
        
        
        
        char[] charArray=s.toCharArray();
        
        int[] integerArray=new int[charArray.length];
        
        
        // creating braces with equivalent numeric values
        for(int i=0;i<charArray.length;i++) {
            
            if(charArray[i]=='{') {
                integerArray[i]=1;
            }
            else if(charArray[i]=='}') {
                integerArray[i]=-1;
            }
            else if(charArray[i]=='[') {
                integerArray[i]=2;
            }
            else if(charArray[i]==']') {
                integerArray[i]=-2;
            }
            else if(charArray[i]=='(') {
                integerArray[i]=3;
            }
            else  {
                integerArray[i]=-3;
            }
        }
        
        Stack<Integer> stack=new Stack<Integer>();
        
        for(int i=0;i<charArray.length;i++) {
            
            if(stack.isEmpty()) {
                if(integerArray[i]<0) {
                    stack.push(integerArray[i]);
                    break;
            }
                    stack.push(integerArray[i]);
            }
            else{
                if(integerArray[i]>0) {
                    stack.push(integerArray[i]);
                }
                else {
                    if(stack.peek()==-(integerArray[i])) {
                        stack.pop();
                    }
                    else {
                        break;
                    }
                }
            }
        }
        return stack.isEmpty();
    }
}
你好，Nava Chaitanya，欢迎来到 Stack Overflow。如果您在代码中附加一些解释，人们会更加感激。 - c8999c 3f964f64
0
static void checkBalanceParan(String s){
Stack<Character>stk=new Stack<>();

int i=0;
int size=s.length();
while(i<size){
    if(s.charAt(i)=='{'||s.charAt(i)=='('||s.charAt(i)=='['){
        stk.push(s.charAt(i));
        i++;
    }
    else if(s.charAt(i)=='}'&&!stk.empty()&&stk.peek()=='{'){
            int x=stk.pop();
            i++;
    }else if(s.charAt(i)==')'&&!stk.empty()&&stk.peek()=='(')
        {
        int x=stk.pop();
        i++;
        }
    else if(s.charAt(i)==']'&&!stk.empty()&&stk.peek()=='['){
        int x=stk.pop();
        i++;
}
    else{
    System.out.println("not Balanced");
        return;
        }
    }
System.out.println("Balanced");}
0

使用 java.util.Stack 数据结构实现匹配括号的代码片段 -

    //map for storing matching parenthesis pairs
    private static final Map<Character, Character> matchingParenMap = new HashMap<>();

    //set for storing opening parenthesis
    private static final Set<Character> openingParenSet = new HashSet<>();

    static {
         matchingParenMap.put(')','(');
         matchingParenMap.put(']','['); 
         matchingParenMap.put('}','{'); 
         openingParenSet.addAll(matchingParenMap.values());  
    }

    //check if parenthesis match
    public static boolean hasMatchingParen(String input) {
      try {
         //stack to store opening parenthesis
         Stack<Character> parenStack = new Stack<>();

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

            //if an opening parenthesis then push to the stack
            if(openingParenSet.contains(ch)) {
                 parenStack.push(ch);
            } 

            //for closing parenthesis
            if(matchingParenMap.containsKey(ch)) {
                 Character lastParen = parenStack.pop();
                 if(lastParen != matchingParenMap.get(ch)) {
                    return false;
                 } 
            }
         }

         //returns true if the stack is empty else false
         return parenStack.isEmpty();
       }
         catch(StackOverflowException s) {}
         catch(StackUnderflowException s1) {}
         return false;
    }

我已经在博客http://hetalrachh.home.blog/2019/12/25/stack-data-structure/中解释了代码片段和算法的使用。

0
import java.util.Objects;
import java.util.Stack;

public class BalanceBrackets {

    public static void main(String[] args) {
        String input="(a{[d]}b)";
        System.out.println(isBalance(input));  ;
    }

    private static boolean isBalance(String input) {
        Stack <Character> stackFixLength = new Stack();

        if(input == null || input.length() < 2) {
            throw  new IllegalArgumentException("in-valid arguments");
        }

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

            if (input.charAt(i) == '(' || input.charAt(i) == '{' || input.charAt(i) == '[') {
                stackFixLength.push(input.charAt(i));
            }

            if (input.charAt(i) == ')' || input.charAt(i) == '}' || input.charAt(i) == ']') {

                if(stackFixLength.empty()) return false;

                char b = stackFixLength.pop();

                if (input.charAt(i) == ')' && b == '(' || input.charAt(i) == '}' && b == '{' || input.charAt(i) == ']' && b == '[') {
                    continue;
                } else {
                    return false;
                }
            }
        }

        return stackFixLength.isEmpty();
    }
}
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接