检查字符串具有平衡括号
我正在阅读算法设计手册第二版 ，这是一个练习题。 引用这个问题
编译器和文本编辑器的一个常见问题是确定字符串中的括号是否是平衡的并且是否正确嵌套。 例如，字符串（（（））（））（）包含正确嵌套的括号对，字符串（）（和（））不包含。 如果字符串包含正确嵌套和平衡的括号，则给出一个返回true的算法，否则返回false。 如果字符串没有正确嵌套和平衡，请确定第一个有问题的括号的位置。
问题在堆栈，队列和列表类别下。 这是我在C＃中写的内容。
const char LeftParenthesis = '('; const char RightParenthesis = ')'; bool AreParenthesesBalanced(string str, out int errorAt) { var items = new Stack(str.Length); errorAt = -1; for (int i = 0; i 0) { errorAt = items.Peek() + 1; return false; } return true; } 这很好用。 但我不确定这是解决这个问题的正确方法。 欢迎任何更好的想法。
我认为这是意图，但如果你只是处理括号，你真的需要减少和增加一个计数器。 如果你正在处理方括号，尖括号，花括号或你想要使用的任何字符配对的配对，你需要像你所做的那样堆栈。
你也可以使用一个列表，关闭和打开head元素，但实际上堆栈可能是作为列表实现的 – 至少它是在ocaml中。
static public bool CheckForBalancedBracketing(string IncomingString) { /******************************************************************* * The easiest way to check for balanced bracketing is to start * * counting left to right adding one for each opening bracket, '(' * * and subtracting 1 for every closing bracket, ')'. At the end * * the sum total should be zero and at no time should the count * * fall below zero. * * * * Implementation: The bracket counting variable is an unsigned * * integer and we trap an overflow exception. This happens if the * * unsigned variable ever goes negative. This allows us to abort * * at the very first imbalance rather than wasting time checking * * the rest of the characters in the string. * * * * At the end all we have to do is check to see if the count * * is equal to zero for a "balanced" result. * * * *******************************************************************/ const char LeftParenthesis = '('; const char RightParenthesis = ')'; uint BracketCount = 0; try { checked // Turns on overflow checking. { for (int Index = 0; Index < IncomingString.Length; Index++) { switch (IncomingString[Index]) { case LeftParenthesis: BracketCount++; continue; case RightParenthesis: BracketCount--; continue; default: continue; } // end of switch() } } } catch (OverflowException) { return false; } if (BracketCount == 0) { return true; } return false; } // end of CheckForBalancedBracketing()
-
从输入字符串中删除所有非’（’和 – ‘）’字符。 这只会给你一串’（’和’）’。
-
如果字符串具有奇数长度，则返回false。
-
否则，开始阅读我们的字符串，为每个’（’和-1为每个’）的“签名”添加+1; 如果此签名永远为负，则返回false。
-
回归真实。
using System; class Solution { public int solution(string S) { int x1 = 0; int x2 = 0; for (int i = 0; i < S.Length; i++) { if (S[i] == ')') if (x1 <= 0) return 0; else x1--; else if (S[i] == '(') x1++; } if (x1 == 0) return 1; else return 0; } }
时间顺序O（n）和空间顺序O（1）
public static bool IsBalanced(string input) { int count = 0; for (int i = 0; i < input.Length; i++) { if (input[i] == '(') count++; if (input[i] == ')') count--; if (count < 0) return false; } if (count == 0) return true; return false; }
来自http://yadiragarnicabonome.com/parentheses-algorithms/
正如TheVillageIdiot所说，这很好。 您也可以递归地实现它，这可能更优雅，也可能不会。 最后，您可能希望要求匹配的括号包含它们之间有效的内容，以便允许“（a）”但不允许“（）”。
为什么有返回值和out参数可以提供相同的信息？
您可以返回一个int：-1 = balanced，否则返回错误的索引。
int i; int len; char popped; stack st; string a = "({<<"; len = a.length(); for(i=0;i' || a[i] == ')' || a[i] == ']' || a[i] == '}') { if(st.empty()) { cout << "stack is empty, when popped , not balanced" << endl; return 0; } else { popped = st.top(); st.pop(); if (!((a[i] == '>' && popped == '<') || (a[i] == ')' && popped == '(') || (a[i] == '}' && popped == '{') || (a[i] == '>' && popped == '<'))) //ok { cout << "not balanced on character" + std::string(1,a[i]) << endl; return 0; } } } } if(st.empty()) { cout << "balanced" << endl; } else { cout << "not balanced stack not empty" << endl; }
Checking balanced parentheses package parancheck; import java.util.EmptyStackException; import java.util.Stack; public class ParnCheck { public static void main(String args[]) { int pu = 0; int po = 0; String str = "()())"; System.out.println(str); Stack st = new Stack(); for(int i=0; i
import java.util.Stack; public class CheckBalancedParenthesis { public static void main (String args[]){ CheckBalancedParenthesis checker = new CheckBalancedParenthesis(); System.out.println(checker.checkBalancedParenthesis("{}}{}{}{}{}")); } public boolean checkBalancedParenthesis(String pattern){ Stack stack = new Stack(); for(int i = 0; i < pattern.length();i++){ char c = pattern.charAt(i); if(c == '{'){ stack.push(c); }else if (c == '}'){ if(!stack.isEmpty()){ stack.pop(); } else{ System.out.println("Error at - " + i); return false; } } } return stack.isEmpty(); } }
以下是validation括号的简单解决方案：
1.将起始括号和结束括号保留在一个字符串中。
2.循环给我们要validation的人并检查以下逻辑：
a）如果项目在起始括号中，则按下它
b）如果项目在结束括号中，则将其索引（在结束括号中）与堆栈的顶部项目索引（在起始括号中）进行比较。
c）如果索引是相同的POP TOP ITEM OF STACK。 否则它的无效字符串。
d）最后一步，检查堆栈是否有项目/ s，表示无效字符串。
string starters = "({[<"; string enders = ")}]>"; Stack stack = new Stack(); foreach(char c in txtValue.Text.Trim()) { if(starters.Contains(c)) { stack.Push(c); } else if (enders.Contains(c)) { if (stack.Count > 0) { if (enders.IndexOf(c) == starters.IndexOf(Convert.ToChar(stack.Peek()))) { stack.Pop(); } else { lblResult.Text = "Invaluid string"; } } } } if(stack.Count == 0) { lblResult.Text = "Valid string"; } else { lblResult.Text = "InValid string"; }
小猪回到@Russell的想法：
public class BalancedBrackets { private readonly char[] _leftBrackets = new char[] {'[', '(', '{', '<'}; private readonly char[] _rightBrackets = new char[] {']', ')', '}', '>'}; public bool IsBalanced(string input) { int count = 0; foreach (var character in input.ToCharArray()) { if (_leftBrackets.Contains(character)) count++; if (_rightBrackets.Contains(character)) count--; } return count == 0; } }
这是使用System.Linq进行C＃的单行程序：
expression.Aggregate(0, (state, ch) => state == -1 ? -1 : state + (ch == '(' ? 1 : ch == ')' ? -1 : 0)) == 0
它利用了字符串实际上是IEnumerable of chars这一事实，因此我们可以在其上运行Aggregate函数。 当我们遇到’（’char并将它减少1’）’char时，我们将计数器增加1。 一旦我们达到-1的负值，我们会留在那里以指示无效状态。
它没有任何早期退出实现，因此它将比这里介绍的大多数实现慢，但也许有人会发现它有用:)
这应该工作：
public class Balanced { public static boolean isbalanced(String input) { int open = 0; int close = 0; for (int i=0; i< input.length();i++) { switch (input.charAt(i)) { case '{': case '(': case '[': open++; break; case '}': case ')': case ']': close++; default: break; } } if (open == close){ return true; } else { return false; } } public static void main(String args[]) { System.out.println(Balanced.isbalanced("()")); } }
这适用于() ， {}和[] 。
还检测错误，如： ([)] ， )[]()和()( ，…
bool isWellFormatted(string line) { Stack lastOpen = new Stack (); foreach (var c in line) { switch (c) { case ')': if (lastOpen.Count == 0 || lastOpen.Pop() != '(') return false; break; case ']': if (lastOpen.Count == 0 || lastOpen.Pop() != '[' ) return false; break; case '}': if (lastOpen.Count == 0 || lastOpen.Pop() != '{') return false; break; case '(': lastOpen.Push(c); break; case '[': lastOpen.Push(c); break; case '{': lastOpen.Push(c); break; } } if (lastOpen.Count == 0) return true; else return false; }