括号/括号匹配使用堆栈算法
例如，如果括号/括号在以下内容中匹配：
({}) (()){}() () 依此类推，但如果括号/括号不匹配，则应返回false，例如：
{} ({}( ){}) (()
等等。 你能查一下这段代码吗？ 提前致谢。
public static boolean isParenthesisMatch(String str) { Stack stack = new Stack(); 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)); }
您的代码在处理“{”和“}”字符时会有一些混乱。 它应该与你处理’（’和’）’的方式完全平行。
此代码稍微修改后，您的代码似乎正常工作：
public static boolean isParenthesisMatch(String str) { if (str.charAt(0) == '{') return false; Stack stack = new Stack (); 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(); }
这段代码更容易理解：
public static boolean CheckParentesis(String str) { if (str.isEmpty()) return true; Stack stack = new Stack (); 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(); }
算法：
- 扫描字符串，推送到堆栈中的每一个’（’在字符串中找到
- 如果char’）’扫描，则从堆栈中弹出一个’（’）
现在，括号在两个条件下是平衡的：
- 在字符串中找到的’（’可以从堆栈中弹出’）’和’
- 堆栈末尾为空（处理整个字符串时）
public static boolean isValidExpression(String expression) { Map openClosePair = new HashMap(); openClosePair.put(')', '('); openClosePair.put('}', '{'); openClosePair.put(']', '['); Stack stack = new Stack (); 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(); }
实际上，没有必要“手动”检查任何情况。 您可以运行以下算法：
-
迭代给定的序列。 从空堆栈开始。
-
如果当前char是一个左括号，只需将其推入堆栈即可。
-
如果它是一个右括号，检查堆栈是否为空，并且步骤的顶部元素是一个合适的开口括号（它是匹配的那个）。 如果不是，请报告错误。 否则，从堆栈中弹出顶部元素。
-
最后，如果堆栈为空，则序列是正确的。
为什么这是正确的？ 下面是一个certificate草图：如果此算法报告序列已更正，则它找到了一对匹配的所有括号。 因此，根据定义，序列确实是正确的。 如果报告错误：
-
如果堆栈最后不是空的，则开启和关闭括号的平衡不为零。 因此，它不是正确的序列。
-
如果我们必须弹出元素时堆栈为空，则余额再次关闭。
-
如果堆栈顶部有错误的元素，则一对“错误”的括号应该相互匹配。 这意味着序列不正确。
我已表明：
-
如果算法报告序列正确，则表示正确。
-
如果算法报告序列不正确，则表示不正确（请注意，除了问题中提到的情况外，我没有使用其他情况）。
这两点意味着该算法适用于所有可能的输入。
public static boolean isBalanced(String s) { Map openClosePair = new HashMap(); openClosePair.put('(', ')'); openClosePair.put('{', '}'); openClosePair.put('[', ']'); Stack stack = new Stack (); 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(); }
算法是：
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) ie 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+(ef[pq])}]") ; 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); } }
输出：
- 支架检查 -
字符串是平衡的
import java.util.*; class StackDemo { public static void main(String[] argh) { boolean flag = true; String str = "(()){}()"; int l = str.length(); flag = true; Stack st = new Stack (); 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"); } }
Ganesan上面的答案不正确，StackOverflow不允许我评论或编辑他的post。 以下是正确的答案。 Ganesan有一个不正确的面对“[”并且缺少堆栈isEmpty（）检查。
如果大括号正确匹配，则以下代码将返回true。
public static boolean isValidExpression(String expression) { Map openClosePair = new HashMap(); openClosePair.put(')', '('); openClosePair.put('}', '{'); openClosePair.put(']', '['); Stack stack = new Stack (); 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(); }
//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); } } }
import java.util.Stack; class Demo { char c; public boolean checkParan(String word) { Stack sta = new Stack (); for(int i=0;i
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("{{{}}"); } }
我试过这个使用下面的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)}`));
我在这里看到了答案，几乎所有人都做得很好。 但是，我编写了自己的版本，利用Dictionary来管理括号对和堆栈来监视检测到的大括号的顺序。 我也为此写了一篇博客文章 。
这是我的课
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(); 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 BuildBracketMap() { return new Dictionary() { {'[', ']'}, {'(', ')'}, {'{', '}'} }; } }
如果你想看看我的代码。 仅供参考
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 exprStack = new Stack (); 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); } } }
public String checkString(String value) { Stack 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"; }
这是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."))
被要求在现场编码面试中实现这个算法，这是我在C＃中的重构解决方案：
Git 测试
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 buffer = new Stack (); 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; } }
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 stk = new Stack (); for(int i=0;i
import java.util.*; public class MatchBrackets { public static void main(String[] argh) { String input = "[]{[]()}"; System.out.println (input); char [] openChars = {'[','{','('}; char [] closeChars = {']','}',')'}; Stack stack = new Stack (); 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"); } }
public static bool IsBalanced(string input) { Dictionary bracketPairs = new Dictionary() { { '(', ')' }, { '{', '}' }, { '[', ']' }, { '<', '>' } }; Stack brackets = new Stack (); 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; }
在java中你不想比较字符串或字符==符号。 你会使用equals方法。 equalsIgnoreCase或类似的东西。 如果你使用==它必须指向相同的内存位置。 在下面的方法中，我尝试使用int来解决这个问题。 从字符串索引处使用ints，因为每个左大括号都有一个右大括号。 我想使用位置匹配而不是比较匹配。 但我认为，你必须有意识地放置字符串的字符。 为简单起见，还可以考虑Yes = true和No = false。 这个答案假定您传递了一个字符串数组来检查并且需要一个if的数组（它们匹配）或No（它们没有）
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 stack = new Stack (); 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]); } }