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

Question

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

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

更新- 抱歉忘记发布我已经做的部分。一开始我使用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;
    }
  }


}

- Jess Anastasio

---

伪代码算法看起来很准确，为什么不把你目前的实现发出来呢？ - Jeff Ward

抱歉有些严厉，但你甚至都有伪代码，必须将其翻译成Java。或者至少试一试，自己尝试失败...也许，如果你的问题中有任何努力的迹象 - 如[FAQ]中所述的那样 - 将有助于获得一些帮助，而不是一些陈旧的愤世嫉俗... void main(String[] args...) { //在此处编写代码 }; - ppeterka

我发布了我迄今为止所做的工作，我忘记在开始时发布，非常感谢。 - Jess Anastasio

你可以先将循环的索引推入栈中，然后尝试弹出一个字符。你应该使用一个字符栈，并将开放括号推入其中。当你找到一个闭合括号时，弹出栈顶元素并检查它是否正确匹配开放括号，然后继续执行。如果在最后栈为空，则字符串是平衡的。 - Neurax

查看此链接，您将获得更好的理解：http://codereview.stackexchange.com/questions/45916/check-for-balanced-parentheses - pratik deshai

Answer 1

我希望这段代码能够帮到你：

import java.util.Stack;

public class BalancedParenthensies {

    public static void main(String args[]) {

        System.out.println(balancedParenthensies("{(a,b)}"));
        System.out.println(balancedParenthensies("{(a},b)"));
        System.out.println(balancedParenthensies("{)(a,b}"));
    }

    public static boolean balancedParenthensies(String s) {
        Stack<Character> stack  = new Stack<Character>();
        for(int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if(c == '[' || c == '(' || c == '{' ) {     
                stack.push(c);
            } else if(c == ']') {
                if(stack.isEmpty() || stack.pop() != '[') {
                    return false;
                }
            } else if(c == ')') {
                if(stack.isEmpty() || stack.pop() != '(') {
                    return false;
                }           
            } else if(c == '}') {
                if(stack.isEmpty() || stack.pop() != '{') {
                    return false;
                }
            }

        }
        return stack.isEmpty();
    }
}

- Smartoop

---

我看到你可以合并嵌套的IF语句。 - O.Badr

Answer 2

public static boolean isBalanced(String expression) {
  if ((expression.length() % 2) == 1) return false;
  else {
    Stack<Character> s = new Stack<>();
    for (char bracket : expression.toCharArray())
      switch (bracket) {
        case '{': s.push('}'); break;
        case '(': s.push(')'); break;
        case '[': s.push(']'); break;
        default :
          if (s.isEmpty() || bracket != s.peek()) { return false;}
          s.pop();
      }
    return s.isEmpty();
  }
}

public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    String expression = in.nextLine();
    boolean answer = isBalanced(expression);
    if (answer) { System.out.println("YES");}
    else { System.out.println("NO");}

}

- Madalina Raicu

Answer 3

该算法的伪代码 Java 实现如下。

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

/**
 * @author Yogen Rai
 */

public class BalancedBraces
{
    public static void main(String[] args) {
        System.out.println(isBalanced("{{}}") ? "YES" : "NO"); // YES
        System.out.println(isBalanced("{{}(") ? "YES" : "NO"); // NO 
        System.out.println(isBalanced("{()}") ? "YES" : "NO"); // YES 
        System.out.println(isBalanced("}{{}}") ? "YES" : "NO"); // NO
    }

    public static boolean isBalanced(String brackets) {
        // set matching pairs
        Map<Character, Character> braces = new HashMap<>();
        braces.put('(', ')');
        braces.put('[',']');
        braces.put('{','}');

        // if length of string is odd, then it is not balanced
        if (brackets.length() % 2 != 0) {
            return false;
        }

        // travel half until openings are found and compare with
        // remaining if the closings matches
        Stack<Character> halfBraces = new Stack();
        for(char ch: brackets.toCharArray()) {
            if (braces.containsKey(ch)) {
                halfBraces.push(braces.get(ch));
            }
            // if stack is empty or if closing bracket is not equal to top of stack,
            // then braces are not balanced
            else if(halfBraces.isEmpty() || ch != halfBraces.pop()) {
                return false;
            }
        }
        return halfBraces.isEmpty();
    }
}

- Yogen Rai

---

不错！这个比其他答案更加数据驱动 - 所以你可以很容易地扩展它，包括100种不同类型的括号，而不需要改变代码（当然，如果你传递了“braces”数据的话！） - Brad Parks

@Yogen Rai 我的评论与字符串的长度有关，我认为即使长度不是偶数也不会导致它不平衡。例如，"(A)"的长度为3，但由于它具有平衡的括号数量（开括号和闭括号相等），所以它是平衡的。也就是说，我会移除只假设偶数长度字符串是平衡的逻辑。 - Ebillson GRAND JEAN

@EbillsonGRANDJEAN 我同意，如果输入字符串可以包含除了 ( { [ ] } ) 之外的字符，但问题中说它只包含 ( { [ ] } ) 字符。 - undefined

Answer 4

使用栈将开放符号推入其中非常重要，当您遇到闭合括号时，弹出栈顶元素，然后检查它是否与闭合括号类型匹配。这是Java的实现。

import java.util.Stack;

public class Balanced {
    public static void main (String [] args)
    {
        String test_good = "()(){}{}{()}";
        String test_bad = "((({}{}))()";

        System.out.println(checkBalanced(test_good));
        System.out.println(checkBalanced(test_bad));
    }

    public static boolean checkBalanced(String check)
    {
        Stack<Character> S = new Stack<Character>();
        for(int a = 0; a < check.length(); a++)
        {
            char let = check.charAt(a);
            if(let == '[' || let == '{' || let == '(')
                S.push(let);
            else if(let == ']' || let == '}' || let == ')')
            {
                if(S.empty())
                    return false;
                switch(let)
                {
                    // Opening square brace
                    case ']':
                        if (S.pop() != '[')
                            return false;
                        break;
                    // Opening curly brace
                    case '}':
                        if (S.pop() != '{')
                            return false;
                        break;
                    // Opening paren brace
                    case ')':
                        if (S.pop() != '(')
                            return false;
                        break;
                    default:
                        break;
                }
            }
        }
        if(S.empty())
            return true;
        return false;
    }
}

- Neurax

---

你可以在 switch 语句中使用 char，并且你也可以将 (甚至是 int) 与一个 char 字面量进行比较。 - Maarten Bodewes

^实际上最好使用 char，现在会更新。 - Neurax

Answer 5

你介意我基于 JavaScript 添加一种古怪的解决方案吗？

这是一种临时用品，不适合生产环境，但适用于面试或类似场合。或者只是为了好玩。

代码如下:

function reduceStr (str) {
  const newStr = str.replace('()', '').replace('{}', '').replace('[]', '')
  if (newStr !== str) return reduceStr(newStr)
  return newStr
}

function verifyNesting (str) {
  return reduceStr(str).length === 0
}

检查项:

console.log(verifyNesting('[{{[(){}]}}[]{}{{(())}}]')) //correct
console.log(verifyNesting('[{{[(){}]}}[]{}{({())}}]')) //incorrect

解释: 它将递归地删除成对的闭合符号 "()", "[]" 和 "{}":

'[{{[(){}]}}[]{}{{(())}}]'
'[{{}}[]{}{{(())}}]'
'[{}{}{{()}}]'
'[{}{{}}]'
'[{{}}]'
'[{}]'
'' 

如果字符串最终长度为空，则返回true，否则返回false。 P.S. 一些回答

• 为什么不用于生产环境？

因为它速度较慢，并且不关心成对字符之间可能存在其他字符的可能性。

• 为什么使用JS？我们喜欢Java

因为我是前端开发人员，但遇到了相同的任务，所以也许对某些人有用。而JS也是JVM语言=）

• 但为什么...

因为所有JS开发人员都疯了，这就是为什么。

- S Panfilov

Answer 6

这是我自己实现的。我尽可能地让它变得最短和最清晰：

public static boolean isBraceBalanced(String braces) {
    Stack<Character> stack = new Stack<Character>();

    for(char c : braces.toCharArray()) {
        if(c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else if((c == ')' && (stack.isEmpty() || stack.pop() != '(')) ||
                  (c == ']' && (stack.isEmpty() || stack.pop() != '[')) ||
                  (c == '}' && (stack.isEmpty() || stack.pop() != '{'))) {
            return false;
        }
    }

    return stack.isEmpty();
}

- FerDensetsu

Answer 7

请尝试这个。

    import java.util.Stack;

    public class PatternMatcher {
        static String[] patterns = { "{([])}", "{}[]()", "(}{}]]", "{()", "{}" };
        static String openItems = "{([";

        boolean isOpen(String sy) {
            return openItems.contains(sy);
        }

        String getOpenSymbol(String byCloseSymbol) {
            switch (byCloseSymbol) {
            case "}":
                return "{";
            case "]":
                return "[";
            case ")":
                return "(";

            default:
                return null;
            }
        }

        boolean isValid(String pattern) {

            if(pattern == null) {
                return false;
            }

            Stack<String> stack = new Stack<String>();
            char[] symbols = pattern.toCharArray();

            if (symbols.length == 0 || symbols.length % 2 != 0) {
                return false;
            }

            for (char c : symbols) {
                String symbol = Character.toString(c);
                if (isOpen(symbol)) {
                    stack.push(symbol);
                } else {
                    String openSymbol = getOpenSymbol(symbol);
                    if (stack.isEmpty() 
                            || openSymbol == null 
                            || !openSymbol.equals(stack.pop())) {
                        return false;
                    }
                }
            }
            return stack.isEmpty();
        }

        public static void main(String[] args) {
            PatternMatcher patternMatcher = new PatternMatcher();

            for (String pattern : patterns) {
                boolean valid = patternMatcher.isValid(pattern);
                System.out.println(pattern + "\t" + valid);
            }
        }

    }

- Sami

Answer 8

你正在将索引 i 推送到栈上，并与 ch 进行比较。你应该推送和弹出 ch。

- Maarten Bodewes

Answer 9

使用switch-case语句可以提高可读性并处理其他情况：

最初的回答

import java.util.Scanner;
import java.util.Stack;

public class JavaStack
{
    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String input = sc.next();
            System.out.println(isStringBalanced(input));
        }
        scanner.close();

    }

    private static boolean isStringBalanced(String testString)
    {
        Stack<Character> stack = new Stack<Character>();
        for (char c : testString.toCharArray()) {
            switch (c) {
                case '[':
                case '(':
                case '{':
                    stack.push(c);
                    break;
                case ']':
                    if (stack.isEmpty() || stack.pop() != '[') {
                        return false;
                    }
                    break;
                case ')':
                    if (stack.isEmpty() || stack.pop() != '(') {
                        return false;
                    }
                    break;
                case '}':
                    if (stack.isEmpty() || stack.pop() != '{') {
                        return false;
                    }
                    break;
                default:
                    break;
            }
        }
        // stack has to be empty, if not, the balance was wrong
        return stack.empty();
    }
}

- TechFree

Answer 10

类似于上面的JAVA代码，但是需要添加一个else语句以避免与除大括号之外的字符进行堆栈比较：

else if（bracketPair.containsValue（strExpression.charAt（i）））

public boolean isBalanced(String strExpression){
 Map<Character,Character> bracketPair = new HashMap<Character,Character>();
  bracketPair.put('(', ')');
  bracketPair.put('[', ']');
  bracketPair.put('{', '}');
  Stack<Character> stk = new Stack<Character>();
        for(int i =0;i<strExpression.length();i++){
            if(bracketPair.containsKey(strExpression.charAt(i)))
                stk.push(strExpression.charAt(i));
            else if(bracketPair.containsValue(strExpression.charAt(i))) 
                if(stk.isEmpty()||bracketPair.get(stk.pop())!=strExpression.charAt(i))
                return false;
        }

        if(stk.isEmpty())
            return true;
            else
                return false;
        }

- Ali Faisal