java - 使用堆栈算法进行括号/括号匹配

Question

例如，如果括号/括号在以下内容中匹配：

({})
(()){}()
()

依此类推，但如果括号/括号不匹配，则应返回 false，例如：

{}
({}(
){})
(()

等等。你能检查一下这个代码吗？提前致谢。

public static boolean isParenthesisMatch(String str) {
    Stack<Character> stack = new Stack<Character>();

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

        if(c == '{')
            return false;

        if(c == '(')
            stack.push(c);

        if(c == '{') {
            stack.push(c);
            if(c == '}')
                if(stack.empty())
                    return false;
                else if(stack.peek() == '{')
                    stack.pop();
        }
        else if(c == ')')
            if(stack.empty())
                return false;
            else if(stack.peek() == '(')
                    stack.pop();
                else
                    return false;
        }
        return stack.empty();
}

public static void main(String[] args) {        
    String str = "({})";
    System.out.println(Weekly12.parenthesisOtherMatching(str)); 
}

Answer 1

您的代码在处理“{”和“}”字符时有些混淆。它应该与您处理“（”和“）”的方式完全平行。

这段代码稍加修改，似乎可以正常工作：

public static boolean isParenthesisMatch(String str) {
    if (str.charAt(0) == '{')
        return false;

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

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

        if(c == '(')
            stack.push(c);
        else if(c == '{')
            stack.push(c);
        else if(c == ')')
            if(stack.empty())
                return false;
            else if(stack.peek() == '(')
                stack.pop();
            else
                return false;
        else if(c == '}')
            if(stack.empty())
                return false;
            else if(stack.peek() == '{')
                stack.pop();
            else
                return false;
    }
    return stack.empty();
}

Answer 2

这段代码更容易理解：

public static boolean CheckParentesis(String str)
{
    if (str.isEmpty())
        return true;

    Stack<Character> stack = new Stack<Character>();
    for (int i = 0; i < str.length(); i++)
    {
        char current = str.charAt(i);
        if (current == '{' || current == '(' || current == '[')
        {
            stack.push(current);
        }


        if (current == '}' || current == ')' || current == ']')
        {
            if (stack.isEmpty())
                return false;

            char last = stack.peek();
            if (current == '}' && last == '{' || current == ')' && last == '(' || current == ']' && last == '[')
                stack.pop();
            else 
                return false;
        }

    }

    return stack.isEmpty();
}

Answer 3

public static boolean isValidExpression(String expression) {
    Map<Character, Character> openClosePair = new HashMap<Character, Character>();
    openClosePair.put(')', '(');
    openClosePair.put('}', '{');
    openClosePair.put(']', '[');        
    Stack<Character> stack = new Stack<Character>();
    for(char ch : expression.toCharArray()) {
        if(openClosePair.containsKey(ch)) {
            if(stack.pop() != openClosePair.get(ch)) {
                return false;
            }
        } else if(openClosePair.values().contains(ch)) {
            stack.push(ch); 
        }
    }
    return stack.isEmpty();
}

Answer 4

算法：

1. 扫描字符串，将字符串中的每个 '(' 推入堆栈
2. 如果 char ')' 被扫描，则从堆栈中弹出一个 '('

现在，括号在两个条件下是平衡的：

• '(' 可以从字符串中找到的每个 ')' 从堆栈中弹出，并且
• 堆栈最后为空（处理整个字符串时）

Answer 5

实际上，没有必要“手动”检查任何案例。您可以运行以下算法：

1. 迭代给定的序列。从一个空堆栈开始。

2. 如果当前 char 是左括号，只需将其推入堆栈即可。

3. 如果它是一个右括号，请检查堆栈是否为空，并且步骤的顶部元素是一个适当的左括号（它是，匹配这个）。如果不是，则报告错误。否则，从堆栈中弹出顶部元素。

4. 最后，如果堆栈为空，则序列是正确的。

为什么是正确的？这是一个证明的草图：如果该算法报告该序列已被纠正，则它已找到所有括号的匹配对。因此，根据定义，该序列确实是正确的。如果已经报错：

1. 如果栈最后不为空，则左括号和右括号的余额不为零。因此，这不是一个正确的顺序。

2. 如果当我们不得不弹出一个元素时堆栈是空的，那么平衡就会再次关闭。

3. 如果堆栈顶部有错误的元素，则一对“错误”的括号应该相互匹配。这意味着顺序不正确。

我已经证明：

• 如果算法报告了序列是正确的，那么它就是正确的。

• 如果算法报告序列不正确，则说明不正确（请注意，除了您的问题中提到的情况外，我没有使用没有其他情况的事实）。

这两点意味着该算法适用于所有可能的输入。

Answer 6

public static boolean isBalanced(String s) {
    Map<Character, Character> openClosePair = new HashMap<Character, Character>();
    openClosePair.put('(', ')');
    openClosePair.put('{', '}');
    openClosePair.put('[', ']'); 

    Stack<Character> stack = new Stack<Character>();
    for (int i = 0; i < s.length(); i++) {

        if (openClosePair.containsKey(s.charAt(i))) {
            stack.push(s.charAt(i));

        } else if ( openClosePair.containsValue(s.charAt(i))) {
            if (stack.isEmpty())
                return false;
            if (openClosePair.get(stack.pop()) != s.charAt(i))
                return false;
        }

        // ignore all other characters

    }
    return stack.isEmpty();
}

Answer 7

Ganesan 上面的回答不正确，StackOverflow 不允许我评论或编辑他的帖子。所以下面是正确答案。Ganesan 有一个不正确的“[”，并且缺少堆栈 isEmpty() 检查。

如果大括号正确匹配，下面的代码将返回 true。

public static boolean isValidExpression(String expression) {
    Map<Character, Character> openClosePair = new HashMap<Character, Character>();
    openClosePair.put(')', '(');
    openClosePair.put('}', '{');
    openClosePair.put(']', '[');

    Stack<Character> stack = new Stack<Character>();
    for(char ch : expression.toCharArray()) {
        if(openClosePair.containsKey(ch)) {
            if(stack.isEmpty() || stack.pop() != openClosePair.get(ch)) {
                return false;
            }
        } else if(openClosePair.values().contains(ch)) {
            stack.push(ch); 
        }
    }
    return stack.isEmpty();
}

Answer 8

您正在做一些不需要的额外检查。不会对功能产生任何差异，但编写代码的更简洁的方法是：

public static boolean isParenthesisMatch(String str) {
    Stack<Character> stack = new Stack<Character>();
    char c;

    for (int i = 0; i < str.length(); i++) {
        c = str.charAt(i);
        if (c == '(' || c == '{')
            stack.push(c);
        else if (stack.empty())
            return false;
        else if (c == ')') {
            if (stack.pop() != '(')
                return false;
        } else if (c == '}') {
            if (stack.pop() != '{')
                return false;
        }
    }
    return stack.empty();
}

在将括号从堆栈中删除之前，没有理由偷看它。我还考虑将指令块包装在括号中以提高可读性。

Answer 9

public boolean isValid(String s) {
    Map<Character, Character> map = new HashMap<>();
    map.put('(', ')');
    map.put('[', ']');
    map.put('{', '}');
    Stack<Character> stack = new Stack<>();
    for(char c : s.toCharArray()){
        if(map.containsKey(c)){
            stack.push(c);
        } else if(!stack.empty() && map.get(stack.peek())==c){
            stack.pop();
        } else {
            return false;
        }
    }
    return stack.empty();
}

Answer 10

算法是：

1)Create a stack

2)while(end of input is not reached)

   i)if the character read is not a sysmbol to be balanced ,ignore it.

   ii)if the character is {,[,( then push it to stack

   iii)If it is a },),] then if 

        a)the stack is empty report an error(catch it) i.e not balanced

        b)else pop the stack 

   iv)if element popped is not corresponding to opening sysmbol,then report error.

3) In the end,if stack is not empty report error else expression is balanced.  

在Java 代码中：

public class StackDemo {
    public static void main(String[] args) throws Exception {
        System.out.println("--Bracket checker--");
        CharStackArray stack = new CharStackArray(10);
        stack.balanceSymbol("[a+b{c+(e-f[p-q])}]") ;
        stack.display();

    }

}    

class CharStackArray {
        private char[] array;
        private int top;
        private int capacity;

        public CharStackArray(int cap) {
            capacity = cap;
            array = new char[capacity];
            top = -1;
        }

        public void push(char data) {
            array[++top] = data;
        }

        public char pop() {
            return array[top--];
        }

        public void display() {
            for (int i = 0; i <= top; i++) {
                System.out.print(array[i] + "->");
            }
        }

        public char peek() throws Exception {
            return array[top];
        }

        /*Call this method by passing a string expression*/
        public void balanceSymbol(String str) {
            try {
                char[] arr = str.toCharArray();
                for (int i = 0; i < arr.length; i++) {
                    if (arr[i] == '[' || arr[i] == '{' || arr[i] == '(')
                        push(arr[i]);
                    else if (arr[i] == '}' && peek() == '{')
                        pop();
                    else if (arr[i] == ']' && peek() == '[')
                        pop();
                    else if (arr[i] == ')' && peek() == '(')
                        pop();
                }
                if (isEmpty()) {
                    System.out.println("String is balanced");
                } else {
                    System.out.println("String is not balanced");
                }
            } catch (Exception e) {
                System.out.println("String not balanced");
            }

        }

        public boolean isEmpty() {
            return (top == -1);
        }
    }

输出：

--括号检查器--

弦是平衡的

Answer 11

使用 Stacks 和 Switch 语句优化实现：

public class JavaStack {

public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

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

    while (sc.hasNext()) {
        String input = sc.next();

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

                case '(':
                    s.push(c); break;
                case '[':
                    s.push(c); break;
                case '{':
                    s.push(c); break;
                case ')':
                    if (!s.isEmpty() && s.peek().equals('(')) {
                        s.pop();
                    } else {
                        s.push(c);
                    } break;
                case ']':
                    if (!s.isEmpty() && s.peek().equals('[')) {
                        s.pop();
                    } else {
                        s.push(c);
                    } break;
                case '}':
                    if (!s.isEmpty() && s.peek().equals('{')) {
                        s.pop();
                    } else {
                        s.push(c);
                    } break;

                default:
                    s.push('x'); break;

            }

        }
        if (s.empty()) {
            System.out.println("true");
        } else {
            System.out.println("false");
            s.clear();
        }
    }
} }

干杯！

Answer 12

import java.util.*;

class StackDemo {

    public static void main(String[] argh) {
        boolean flag = true;
        String str = "(()){}()";
        int l = str.length();
        flag = true;
        Stack<String> st = new Stack<String>();
        for (int i = 0; i < l; i++) {
            String test = str.substring(i, i + 1);
            if (test.equals("(")) {
                st.push(test);
            } else if (test.equals("{")) {
                st.push(test);
            } else if (test.equals("[")) {
                st.push(test);
            } else if (test.equals(")")) {
                if (st.empty()) {
                    flag = false;
                    break;
                }
                if (st.peek().equals("(")) {
                    st.pop();
                } else {
                    flag = false;
                    break;
                }
            } else if (test.equals("}")) {
                if (st.empty()) {
                    flag = false;
                    break;
                }
                if (st.peek().equals("{")) {
                    st.pop();
                } else {
                    flag = false;
                    break;
                }
            } else if (test.equals("]")) {
                if (st.empty()) {
                    flag = false;
                    break;
                }
                if (st.peek().equals("[")) {
                    st.pop();
                } else {
                    flag = false;
                    break;
                }
            }
        }
        if (flag && st.empty())
            System.out.println("true");
        else
            System.out.println("false");
    }
}

Answer 13

我在这里看到了答案，几乎所有的都做得很好。但是，我编写了自己的版本，它利用字典来管理括号对和堆栈来监视检测到的括号的顺序。我也为此写了一篇博文。

这是我的课

public class FormulaValidator
{
    // Question: Check if a string is balanced. Every opening bracket is matched by a closing bracket in a correct position.
    // { [ ( } ] )

    // Example: "()" is balanced
    // Example: "{ ]" is not balanced.
    // Examples: "()[]{}" is balanced.
    // "{([])}" is balanced
    // "{ ( [ ) ] }" is _not_ balanced

    // Input: string, containing the bracket symbols only
    // Output: true or false
    public bool IsBalanced(string input)
    {
        var brackets = BuildBracketMap();
        var openingBraces = new Stack<char>();
        var inputCharacters = input.ToCharArray();

        foreach (char character in inputCharacters)
        {
            if (brackets.ContainsKey(character))
            {
                openingBraces.Push(character);
            }

            if (brackets.ContainsValue(character))
            {
                var closingBracket = character;
                var openingBracket = brackets.FirstOrDefault(x => x.Value == closingBracket).Key;

                if (openingBraces.Peek() == openingBracket)
                    openingBraces.Pop();
                else
                    return false;
            }
        }

        return openingBraces.Count == 0;
    }

    private Dictionary<char, char> BuildBracketMap()
    {
        return new Dictionary<char, char>()
        {
            {'[', ']'},
            {'(', ')'},
            {'{', '}'}
        };
    }
}

Answer 14

用于检查平衡括号的算法-

1. 声明一个匹配ParenMap的映射，并分别用每种类型的右括号和左括号作为键值对对其进行初始化。
2. 声明一个set openingParenSet，并用matchingParenMap的值对其进行初始化。
3. 声明一个堆栈parenStack，它将存储左括号'{'、'('和'['。

4. 现在遍历字符串表达式input。

   1. 如果当前字符是左括号（' { ', ' ( ', ' [ ') 则将其推送到 parenStack。

   2. 如果当前字符是右括号（' } '，' ） '，' ] '）然后从 parenStack弹出，如果弹出的字符等于matchingParenMap中匹配的起始括号， 则继续循环否则返回false。

5. 完全遍历后，如果parenStack中没有左括号，则表示它是一个平衡良好的表达式。

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

Answer 15

问题陈述： 检查表达式中的平衡括号或匹配开闭括号

如果您参加了编码面试，那么您之前可能遇到过这个问题。这是一个非常常见的问题，可以通过使用 C# 中的堆栈 数据结构解决方案来解决

        public void OpenClosingBracketsMatch()
        {
            string pattern = "{[(((((}}])";
            Dictionary<char, char> matchLookup = new Dictionary<char, char>();
            matchLookup['{'] = '}';
            matchLookup['('] = ')';
            matchLookup['['] = ']';
            Stack<char> stck = new Stack<char>();
            for (int i = 0; i < pattern.Length; i++)
            {
                char currentChar = pattern[i];
                if (matchLookup.ContainsKey(currentChar))
                    stck.Push(currentChar);
                else if (currentChar == '}' || currentChar == ')' || currentChar == ']')
                {
                    char topCharFromStack = stck.Peek();
                    if (matchLookup[topCharFromStack] != currentChar)
                    {
                        Console.WriteLine("NOT Matched");
                        return;
                    }
                }
            }

            Console.WriteLine("Matched");
        }

有关更多信息，您还可以参考此链接：https ://www.geeksforgeeks.org/check-for-balanced-parentheses-in-an-expression/

Answer 16

这是我使用 c++ 的解决方案，如果括号匹配，则返回 true，否则返回 false

#include <iostream>
#include <stack>
#include <string.h>
using namespace std;

int matchbracket(string expr){
    stack<char> st;
    int i;
    char x;
    for(i=0;i<expr.length();i++){
        if(expr[i]=='('||expr[i]=='{'||expr[i]=='[')
          st.push(expr[i]);
          
        if(st.empty())
         return -1;
        switch(expr[i]){
            case ')' :
             x=expr[i];
             st.pop();
             if(x=='}'||x==']')
              return 0;
              break;
            
            case '}' :
             x=expr[i];
             st.pop();
             if(x==')'||x==']')
              return 0;
              break;
        
            case ']' :
            x=expr[i];
            st.pop();
            if(x==')'||x=='}')
             return 1;
             break;
        } 

    }
    return(st.empty());
}

int main()
{
 string expr;
 cin>>expr;
 
 if(matchbracket(expr)==1)
  cout<<"\nTRUE\n";
  else
  cout<<"\nFALSE\n";
}

Answer 17

//basic code non strack algorithm just started learning java ignore space and time.
/// {[()]}[][]{}
// {[( -a -> }]) -b -> replace a(]}) -> reverse a( }]))-> 
//Split string to substring {[()]}, next [], next [], next{}

public class testbrackets {
    static String stringfirst;
    static String stringsecond;
    static int open = 0;
    public static void main(String[] args) {
        splitstring("(()){}()");
    }
static void splitstring(String str){

    int len = str.length();
    for(int i=0;i<=len-1;i++){
        stringfirst="";
        stringsecond="";
        System.out.println("loop starttttttt");
        char a = str.charAt(i);
    if(a=='{'||a=='['||a=='(')
    {
        open = open+1;
        continue;
    }
    if(a=='}'||a==']'||a==')'){
        if(open==0){
            System.out.println(open+"started with closing brace");
            return;
        }
        String stringfirst=str.substring(i-open, i);
        System.out.println("stringfirst"+stringfirst);
        String stringsecond=str.substring(i, i+open);
        System.out.println("stringsecond"+stringsecond);
        replace(stringfirst, stringsecond);

        }
    i=(i+open)-1;
    open=0;
    System.out.println(i);
    }
    }
    static void replace(String stringfirst, String stringsecond){
        stringfirst = stringfirst.replace('{', '}');
        stringfirst = stringfirst.replace('(', ')');
        stringfirst = stringfirst.replace('[', ']');
        StringBuilder stringfirst1 = new StringBuilder(stringfirst);
        stringfirst = stringfirst1.reverse().toString();
    System.out.println("stringfirst"+stringfirst);
    System.out.println("stringsecond"+stringsecond);
if(stringfirst.equals(stringsecond)){
    System.out.println("pass");
}
    else{
        System.out.println("fail");
        System.exit(0);
        }
    }
}

Answer 18

import java.util.Stack;

class Demo
{

    char c;

    public  boolean checkParan(String word)
    {
        Stack<Character> sta = new Stack<Character>();
        for(int i=0;i<word.length();i++)
        {
           c=word.charAt(i);


          if(c=='(')
          {
              sta.push(c);
              System.out.println("( Pushed into the stack");

          }
          else if(c=='{')
          {
              sta.push(c);
              System.out.println("( Pushed into the stack");
          }
          else if(c==')')
          {
              if(sta.empty())
              {
                  System.out.println("Stack is Empty");
                  return false;
              }
              else if(sta.peek()=='(')
              {

                  sta.pop();
                  System.out.println(" ) is poped from the Stack");
              }
              else if(sta.peek()=='(' && sta.empty())
              {
                  System.out.println("Stack is Empty");
                  return false;
              }
          }
          else if(c=='}')
          {
              if(sta.empty())
              {
               System.out.println("Stack is Empty");
              return false;
              }
              else if(sta.peek()=='{')
              {
                  sta.pop();
                  System.out.println(" } is poped from the Stack");
              }

          }

          else if(c=='(')
          {
              if(sta.empty())
              {
                 System.out.println("Stack is empty only ( parenthesis in Stack ");  
              }
          }


        }
    // System.out.print("The top element is : "+sta.peek());
    return sta.empty();
    } 





}

---

public class ParaenthesisChehck {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
       Demo d1= new Demo();
     //  d1.checkParan(" ");
      // d1.checkParan("{}");
       //d1.checkParan("()");
       //d1.checkParan("{()}");
     // d1.checkParan("{123}");
       d1.checkParan("{{{}}");





    }

}

Answer 19

import java.util.*;

public class Parenthesis

 {

    public static void main(String...okok)

    {
        Scanner sc= new Scanner(System.in);
        String str=sc.next();
        System.out.println(isValid(str));

    }
    public static int isValid(String a) {
        if(a.length()%2!=0)
        {

            return 0;
        }
        else if(a.length()==0)
        {

            return 1;
        }
        else
        {

            char c[]=a.toCharArray();
            Stack<Character> stk =  new Stack<Character>();
            for(int i=0;i<c.length;i++)
            {
                if(c[i]=='(' || c[i]=='[' || c[i]=='{')
                {
                    stk.push(c[i]);
                }
                else
                {
                    if(stk.isEmpty())
                    {
                        return 0;
                        //break;
                    }
                    else
                    {

                        char cc=c[i];
                        if(cc==')' && stk.peek()=='(' )
                        {
                            stk.pop();
                        }
                        else if(cc==']' && stk.peek()=='[' )
                        {

                            stk.pop();
                        }
                        else if(cc=='}' && stk.peek()=='{' )
                        {

                            stk.pop();
                        }
                    }
                }

            }
            if(stk.isEmpty())
            {
                return 1;
            }else
            {
                return 0;
            }
        }



    }

}

Answer 20

我在下面使用javascript尝试了这个结果。

function bracesChecker(str) {
  if(!str) {
    return true;
  }
  var openingBraces = ['{', '[', '('];
  var closingBraces = ['}', ']', ')'];
  var stack = [];
  var openIndex;
  var closeIndex;
  //check for opening Braces in the val
  for (var i = 0, len = str.length; i < len; i++) {
    openIndex = openingBraces.indexOf(str[i]);
    closeIndex = closingBraces.indexOf(str[i]);
    if(openIndex !== -1) {
      stack.push(str[i]);
    }  
    if(closeIndex !== -1) {
      if(openingBraces[closeIndex] === stack[stack.length-1]) { 
        stack.pop();
      } else {
        return false;
      }
    }
  }
  if(stack.length === 0) {
    return true;
  } else {
    return false;
  }
}
var testStrings = [
  '', 
  'test', 
  '{{[][]()()}()}[]()', 
  '{test{[test]}}', 
  '{test{[test]}', 
  '{test{(yo)[test]}}', 
  'test{[test]}}', 
  'te()s[]t{[test]}', 
  'te()s[]t{[test'
];

testStrings.forEach(val => console.log(`${val} => ${bracesChecker(val)}`));

Answer 21

import java.util.*;

public class MatchBrackets {

    public static void main(String[] argh) {
        String input = "[]{[]()}";
        System.out.println  (input);

        char [] openChars =  {'[','{','('};
        char [] closeChars = {']','}',')'};

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

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

            String x = "" +input.charAt(i);

            if (String.valueOf(openChars).indexOf(x) != -1)
            {
                stack.push(input.charAt(i));
            }
            else
            {
                Character lastOpener = stack.peek();
                int idx1 = String.valueOf(openChars).indexOf(lastOpener.toString());
                int idx2 = String.valueOf(closeChars).indexOf(x);

                if (idx1 != idx2)
                {
                    System.out.println("false");
                    return;
                }
                else
                {
                    stack.pop();
                }
            }
        }

        if (stack.size() == 0)
            System.out.println("true");
        else
            System.out.println("false");
    }
}

Answer 22

如果你想看看我的代码。仅供参考

public class Default {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int numOfString = Integer.parseInt(br.readLine());
        String s;
        String stringBalanced = "YES";
        Stack<Character> exprStack = new Stack<Character>();

        while ((s = br.readLine()) != null) {
            stringBalanced = "YES";
            int length = s.length() - 1;
            for (int i = 0; i <= length; i++) {
                char tmp = s.charAt(i);

                if(tmp=='[' || tmp=='{' || tmp=='('){
                    exprStack.push(tmp);
                }else if(tmp==']' || tmp=='}' || tmp==')'){
                    if(!exprStack.isEmpty()){
                        char peekElement = exprStack.peek();
                        exprStack.pop();
                        if(tmp==']' && peekElement!='['){
                            stringBalanced="NO";
                        }else if(tmp=='}' && peekElement!='{'){
                            stringBalanced="NO";
                        }else if(tmp==')' && peekElement!='('){
                            stringBalanced="NO";
                        }
                    }else{
                        stringBalanced="NO";
                        break;
                    }
                }

            }

            if(!exprStack.isEmpty()){
                stringBalanced = "NO";
            }

            exprStack.clear();
            System.out.println(stringBalanced);
        }
    }
}

Answer 23

public static bool IsBalanced(string input)
    {
        Dictionary<char, char> bracketPairs = new Dictionary<char, char>() {
        { '(', ')' },
        { '{', '}' },
        { '[', ']' },
        { '<', '>' }
    };

        Stack<char> brackets = new Stack<char>();

        try
        {
            // Iterate through each character in the input string
            foreach (char c in input)
            {
                // check if the character is one of the 'opening' brackets
                if (bracketPairs.Keys.Contains(c))
                {
                    // if yes, push to stack
                    brackets.Push(c);
                }
                else
                    // check if the character is one of the 'closing' brackets
                    if (bracketPairs.Values.Contains(c))
                    {
                        // check if the closing bracket matches the 'latest' 'opening' bracket
                        if (c == bracketPairs[brackets.First()])
                        {
                            brackets.Pop();
                        }
                        else
                            // if not, its an unbalanced string
                            return false;
                    }
                    else
                        // continue looking
                        continue;
            }
        }
        catch
        {
            // an exception will be caught in case a closing bracket is found, 
            // before any opening bracket.
            // that implies, the string is not balanced. Return false
            return false;
        }

        // Ensure all brackets are closed
        return brackets.Count() == 0 ? true : false;
    }

Answer 24

public String checkString(String value) {
    Stack<Character> stack = new Stack<>();
    char topStackChar = 0;
    for (int i = 0; i < value.length(); i++) {
        if (!stack.isEmpty()) {
            topStackChar = stack.peek();
        }
        stack.push(value.charAt(i));
        if (!stack.isEmpty() && stack.size() > 1) {
            if ((topStackChar == '[' && stack.peek() == ']') ||
                    (topStackChar == '{' && stack.peek() == '}') ||
                    (topStackChar == '(' && stack.peek() == ')')) {
                stack.pop();
                stack.pop();
            }
        }
    }
    return stack.isEmpty() ? "YES" : "NO";
}

Answer 25

这是Python中的解决方案。

#!/usr/bin/env python

def brackets_match(brackets):
    stack = []
    for char in brackets:
        if char == "{" or char == "(" or char == "[":
            stack.append(char)
        if char == "}":
            if stack[-1] == "{":
                stack.pop()
            else:
                return False
        elif char == "]":
            if stack[-1] == "[":
                stack.pop()
            else:
                return False
        elif char == ")":
            if stack[-1] == "(":
                stack.pop()
            else:
                return False
    if len(stack) == 0:
        return True
    else:
        return False

if __name__ == "__main__":
    print(brackets_match("This is testing {([])} if brackets have match."))

Answer 26

在现场编码面试中被要求实现此算法，这是我在 C# 中重构的解决方案：

Git 测试

Answer 27

package com.balance.braces;

import java.util.Arrays;
import java.util.Stack;

public class BalanceBraces {

public static void main(String[] args) {

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

    String[] rsult = match(values);

    Arrays.stream(rsult).forEach(str -> System.out.println(str));
}

static String[] match(String[] values) {

    String[] returnString = new String[values.length];

    for (int i = 0; i < values.length; i++) {
        String value = values[i];

        if (value.length() % 2 != 0) {
            returnString[i] = "NO";
            continue;
        } else {

            Stack<Character> buffer = new Stack<Character>();
            for (char ch : value.toCharArray()) {

                if (buffer.isEmpty()) {
                    buffer.add(ch);
                } else {
                    if (isMatchedBrace(buffer.peek(), ch)) {
                        buffer.pop();
                    } else {
                        buffer.push(ch);
                    }
                }
                if (buffer.isEmpty()) {
                    returnString[i] = "YES";
                } else {
                    returnString[i] = "FALSE";
                }
            }
        }

    }

    return returnString;
}

static boolean isMatchedBrace(char start, char endmatch) {
    if (start == '{')
        return endmatch == '}';
    if (start == '(')
        return endmatch == ')';
    if (start == '[')
        return endmatch == ']';
    return false;
}

}

Answer 28

在 java 中，您不想通过 == 符号比较字符串或字符。你会使用equals方法。equalsIgnoreCase 或类似的东西。如果你使用 == 它必须指向相同的内存位置。在下面的方法中，我尝试使用整数来解决这个问题。在此处使用字符串索引中的整数，因为每个左大括号都有一个右大括号。我想使用位置匹配而不是比较匹配。但我认为这样你必须有意识地放置字符串的字符。为简单起见，我们还考虑 Yes = true 和 No = false。这个答案假设您传递了一个字符串数组来检查并需要一个数组，如果是（他们匹配）或否（他们没有）

import java.util.Stack; 

    public static void main(String[] args) {

    //String[] arrayOfBraces = new String[]{"{[]}","([{}])","{}{()}","{}","}]{}","{[)]()}"};
    // Example: "()" is balanced
    // Example: "{ ]" is not balanced.
    // Examples: "()[]{}" is balanced.
    // "{([])}" is balanced
    // "{([)]}" is _not_ balanced

    String[] arrayOfBraces  = new String[]{"{[]}","([{}])","{}{()}","()[]{}","}]{}","{[)]()}","{[)]()}","{([)]}"};
    String[] answers        = new String[arrayOfBraces.length];     
    String openers          = "([{";
    String closers          = ")]}";
    String stringToInspect  = ""; 
    Stack<String> stack     = new Stack<String>();


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

        stringToInspect = arrayOfBraces[i];
        for (int j = 0; j < stringToInspect.length(); j++) {            
            if(stack.isEmpty()){
                if (openers.indexOf(stringToInspect.charAt(j))>=0) {
                    stack.push(""+stringToInspect.charAt(j));   
                }
                else{
                    answers[i]= "NO";
                    j=stringToInspect.length();
                }                   
            }
            else if(openers.indexOf(stringToInspect.charAt(j))>=0){
                stack.push(""+stringToInspect.charAt(j));   
            }
            else{
                String comparator = stack.pop();
                int compLoc = openers.indexOf(comparator);
                int thisLoc = closers.indexOf(stringToInspect.charAt(j));

                if (compLoc != thisLoc) {
                    answers[i]= "NO";
                    j=stringToInspect.length();                     
                }
                else{
                    if(stack.empty() && (j== stringToInspect.length()-1)){
                        answers[i]= "YES";
                    }
                }
            }
        }
    }

    System.out.println(answers.length);         
    for (int j = 0; j < answers.length; j++) {
        System.out.println(answers[j]);
    }       
}

Answer 29

  Check balanced parenthesis or brackets with stack-- 
  var excp = "{{()}[{a+b+b}][{(c+d){}}][]}";
   var stk = [];   
   function bracket_balance(){
      for(var i=0;i<excp.length;i++){
          if(excp[i]=='[' || excp[i]=='(' || excp[i]=='{'){
             stk.push(excp[i]);
          }else if(excp[i]== ']' && stk.pop() != '['){
             return false;
          }else if(excp[i]== '}' && stk.pop() != '{'){

            return false;
          }else if(excp[i]== ')' && stk.pop() != '('){

            return false;
          }
      }

      return true;
   }

  console.log(bracket_balance());
  //Parenthesis are balance then return true else false

Answer 30

不使用堆栈的括号匹配程序

在这里，我使用字符串来替换堆栈实现，如推送和弹出操作。

`包java_prac; 导入 java.util.*；公共类括号检查器{

    public static void main(String[] args) {
        System.out.println("- - - Brackets Checker [ without stack ] - - -\n\n");
        Scanner scan=new Scanner(System.in);
        System.out.print("Input : " );
        String s = scan.nextLine();
        scan.close();
        System.out.println("\n...working...\n");
        String o="([{";
        String c=")]}";
        String x=" ";
        int check =0;
        for (int i = 0; i < s.length(); i++) {
            if(o.contains(String.valueOf(s.charAt(i)))){
                x+=s.charAt(i);     
                 //System.out.println("In : "+x); // stack in
            }else if(c.contains(String.valueOf(s.charAt(i)))) { 
                char temp = s.charAt(i);
                if(temp==')') temp = '(';
                if(temp=='}') temp = '{';
                if(temp==']') temp = '[';
                if(x.charAt(x.length()-1)==temp) {
                    x=" "+x.substring(1,x.length()-1);
                    //System.out.println("Out : "+x);   // stack out
            }else {
            check=1;    
            }
            }
    }   
        if(x.length()==1 && check==0 ) {
            System.out.println("\n\nCompilation Success \n\n© github.com/sharanstark 2k19");
        }else {
            System.out.println("\n\nCompilation Error \n\n© github.com/sharanstark 2k19" );
        }
    }
}`