给定表达式字符串exp，编写一个程序来检查exp中的
对和
"{","}","(",")","[","]"
的顺序是否正确。 />
例如，对于
exp = "[()]{}{[()()]()}"
该程序应打印true，对于
exp = "[(])"
该程序应打印false />
复杂度：
时间复杂度：O（n）其中n是字符串的长度
空间复杂度：O（n / 2）其中n是字符串字符串的长度
寻找代码复习，优化和最佳实践。
public final class BalancedParanthesis {
private static final Map<Character, Character> brackets = new HashMap<Character, Character>();
static {
brackets.put('[', ']');
brackets.put('{', '}');
brackets.put('(', ')');
}
private BalancedParanthesis() {};
/**
* Returns true is parenthesis match open and close.
* Understands [], {}, () as the brackets
* It is clients responsibility to include only valid paranthesis as input.
* A false could indicate that either parenthesis did not match or input including chars other than valid paranthesis
*
* @param str the input brackets
* @return true if paranthesis match.
*/
public static boolean isBalanced(String str) {
if (str.length() == 0) {
throw new IllegalArgumentException("String length should be greater than 0");
}
// odd number would always result in false
if ((str.length() % 2) != 0) {
return false;
}
final Stack<Character> stack = new Stack<Character>();
for (int i = 0; i < str.length(); i++) {
if (brackets.containsKey(str.charAt(i))) {
stack.push(str.charAt(i));
} else if (stack.empty() || (str.charAt(i) != brackets.get(stack.pop()))) {
return false;
}
}
return true;
}
public static void main(String[] args) {
assertEquals(true, isBalanced("{}([])"));
assertEquals(false,isBalanced("([}])"));
assertEquals(true, isBalanced("([])"));
assertEquals(true, isBalanced("()[]{}[][]"));
}
}
#1 楼
我只想写代码对我来说看起来就很好，直到...我个人希望函数返回一个空字符串
true而不是抛出异常。Stack已过时。我会改用Deque的实现。空间复杂度。评论
\ $ \ begingroup \ $
是的。 O（n / 2）与O（n）相同。这是否是教师的意图是一个不同的问题...
\ $ \ endgroup \ $
–托马斯
2014年4月1日在18:34
\ $ \ begingroup \ $
好的O标记不是我的强项。但是您可以修改代码，使其仅需要存储n / 2 + 1个字符。
\ $ \ endgroup \ $
–RoToRa
2014年4月1日在22:51
\ $ \ begingroup \ $
@fgrieu：对不起，它会断言。调用isBalanced（“ [[”）时，两个方括号（[）仅会压入堆栈。 for循环中if语句的第二个子句（以及pop（）s）从不被调用，因此它达到最终返回true。请参阅ideone.com/Ed5eiU（不使用assert，但将true输出到stdout）。
\ $ \ endgroup \ $
–RoToRa
2014年4月2日在13:46
\ $ \ begingroup \ $
@RoToRa：我的立场是正确的。
\ $ \ endgroup \ $
– fgrieu
2014年4月2日13:50
\ $ \ begingroup \ $
返回stack.isEmpty（）
\ $ \ endgroup \ $
–吉万
16年3月3日在21:18
#2 楼
assertEquals vs assertTrue我看到您正在使用：
assertEquals(true, isBalanced("{}([])"));
assertEquals(false,isBalanced("([}])"));
assertEquals(true, isBalanced("([])"));
assertEquals(true, isBalanced("()[]{}[][]"));
这不是最好的方法声明布尔值。您应该使用：
assertTrue(isBalanced("{}([])"));
assertFalse(isBalanced("([}])"));
assertTrue(isBalanced("([])"));
assertTrue(isBalanced("()[]{}[][]"));
这很清楚，因为很明显您正在检查是非。
分离
/>
您的所有测试仍然处于主要状态，我再次强烈建议将这些测试提取到测试类中，并为每种情况创建一个方法。如果您将相关的名称命名为测试名称，以便乍看一下您要进行的测试，这将有所帮助。是例外，正常情况等。
#3 楼
这段代码基本上是完美的（省去了RoToRa所发现的那个小错误）：文档说了什么巧妙的短路
使用显式堆栈的实现
但是，有几点我们可以讨论：
JavaDoc没有提到字符串必须包含至少两个字符。我希望字符串
""确实是平衡的。对我来说，平衡的字符串将由以下EBNF语法描述：<Balanced> ::=
'(' <Balanced> ')'
| '{' <Balanced> '}'
| '[' <Balanced> ']'
| epsilon
，即，通过此递归定义可以使用空字符串。相反，您为以下语法实现了识别器：
<Balanced> ::=
'(' <InnerBalanced> ')'
| '{' <InnerBalanced> '}'
| '[' <InnerBalanced> ']'
<InnerBalanced> ::=
<Balanced>
| epsilon
您忘记测试
str != null 您可以使用菱形运算符调用对通用参数的推论：
Map<Character, Character> brackets = new HashMap<>() Stack<Character> stack = new Stack<>() 。最好启用一些自定义功能，否则默认使用
<…>。如果启用自定义括号，则可能会有些含糊-每个打开括号都与一组可能的关闭括号关联。请注意，在给定O（1）成员资格测试的情况下，这不会影响代码的算法复杂性。示例：
(…)（数学的标准算子/ |…|），abs（量子物理学的Bra-ket表示法），|…>（统计中的均值/期望值）。通常也将包含非括号的文本。给定定界符<…>的函数对于q{foo($bar{baz} .= do {my $x = '('; bless $x})}返回true，将在实际应用中有用。不幸的是，这使您无法检查字符串必须为偶数长度。您仅支持将单个“字符”用作分隔符。允许任意字符串会更加灵活。请注意，Java的
{…}不是真正的Unicode字符，而实际上只是16位代码单元。为了表示任何Unicode代码点，我们需要一个或两个Java字符（请考虑：“ Character是新的int”）。还要注意，这仅适用于单个代码点，而一个逻辑字符（“字素”）可能包含多个代码点。评论
\ $ \ begingroup \ $
“允许任意字符串会更灵活”，但是由于可能的重叠，问题变得更加棘手。如果允许自定义单字符括号，而右括号与左括号重合，则会发生相同的问题。另外，为什么需要显式检查null？文档没有说明null为有效输入，并且默认情况下我不会假定为null，因此NullPointerException还不够吗？
\ $ \ endgroup \ $
–尼古拉斯B.
2014年4月1日19:55
\ $ \ begingroup \ $
@NiklasB。带有自定义错误消息的显式NPE使调用者更容易调试。留下未指定的行为是便宜的警察。另外，防御性编程也是最佳实践。再明确一点：只要设置了一些规则来决定如何解析输入，即使在给定的算法复杂性约束下，这也不是问题。重叠标记成为具有最长标记匹配的非问题，使用提交而不是回溯可以保留O（n）行为，并且我们可以决定使用右括号而不是右括号。进一步的问题？ :)
\ $ \ endgroup \ $
–阿蒙
2014年4月1日在21:12
\ $ \ begingroup \ $
当然，您可以指定贪婪的解析，但这可能与用户的直觉相反，这些用户会认为解析器只是实现您的答案中给出的直接的，上下文无关的语法（这样将很难解析）。只是想指出，如果走那条路，您将需要考虑很多细节。 W.r.t防守，只是说“除非另有说明，否则null永远不是有效的输入”是否可以接受？我通常就是这样做的（对于整个库，而不仅仅是某些方法），并且不会留下任何未指定的内容
\ $ \ endgroup \ $
–尼古拉斯B.
2014年4月1日21:16
\ $ \ begingroup \ $
@NiklasB。是的，当然，我只添加了有关如何使isBalanced更通用的建议。我认为，为“用户”提供更多功能比提供一组受限制的“安全”操作更可取，即使更多的功能意味着更多的东西可能出问题。 （出于某些不可思议的原因，与Python相比，我更喜欢Perl，而Java则更喜欢Scala。）哦，我忘了提到另一种处理歧义的好方法。：遇到歧义时就抛出异常（可能最早是在收集所有大括号时）数据结构）。
\ $ \ endgroup \ $
–阿蒙
2014年4月1日在21:37
#4 楼
该类的名称错误：BalancedParanthesis应该是BalancedParentheses。由于无法平衡一个括号，因此“ Paranthesis”应拼写为“ Parenthesis”，并应使其成为“ Parentheses”的复数形式。不只是括号。#5 楼
对于其他回答，我只有一个补充内容对于使用
java.util.Stack的堆栈，这似乎是一个显而易见的选择，但它是预收集时间的残余，是java.util.Vector的子类，因此synchronized。您不需要同步开销，最好使用java.util.ArrayDeque。这是一个双端队列，但是如果仅从顶部访问，则可以完美地用作堆栈。实际上，Stack的javadoc建议您改用ArrayDeque。评论
\ $ \ begingroup \ $
LinkedList会更合适吗？链表针对推和弹出操作进行了优化，这就是这里使用的。
\ $ \ endgroup \ $
–RoToRa
2014年4月1日在23:13
\ $ \ begingroup \ $
ArrayDeque的推入和弹出操作仅更改一个int索引，仅当数组需要增长时，才需要执行System.arrayCopy（），LinkedList将必须在每次推入时创建一个新的Node。因为我们知道确切的最大所需容量，所以我们可以确保ArrayDeque不需要增长，从而消除了ArrayDeque的一个缺点。即使我们没有设置容量，我也认为ArrayDeque在此算法中的表现将优于LinkedList。
\ $ \ endgroup \ $
– Bowmore
2014年4月2日在4:52
#6 楼
即使您的brackets是私人的，也要使这些键值持有者不可变，这也是一个好习惯。因此，您的代码private static final Map<Character, Character> brackets = new HashMap<Character, Character>();
static {
brackets.put('[', ']');
brackets.put('{', '}');
brackets.put('(', ')');
}
可以重写为
private static final Map<Character, Character> brackets = Collections.unmodifiableMap(new HashMap<Character, Character>() {{
put('[', ']');
put('{', '}');
put('(', ')');
}});
这更简洁，也很有效文档，即使您的
Map是private，即使您没有设置器也是如此。 > private static final Map<Character, Character> guavaBracket = ImmutableMap.of('[', ']','{', '}','(', ')');
评论
\ $ \ begingroup \ $
建议您使用实例初始值设定项块，在现实生活中会引起很多混乱，尤其是当您以现有方式违反Java代码样式准则时。
\ $ \ endgroup \ $
–rolfl
2014年4月6日13:55
\ $ \ begingroup \ $
是的..只有在不可变性很差并且更冗长的代码在“现实生活”中不太混乱的情况下。
\ $ \ endgroup \ $
–senseiwu
2014年4月6日15:54
\ $ \ begingroup \ $
不变性很好，但是带有实例初始化程序块且具有非标准代码格式的匿名子类令人困惑……这就是我的第一句话。更详细的代码或格式正确的可读代码。...称呼您想要的，但是在任何通用参考文献中，推荐的方法都不是最佳实践。
\ $ \ endgroup \ $
–rolfl
2014年4月6日15:58
\ $ \ begingroup \ $
您似乎对不变性表示同意，我不知道在这种情况下是否存在针对/反对匿名子类化的最佳实践建议。在我回顾过的生产代码中，我也看到了大部分没有匿名的方法。您似乎更喜欢的子类。但是最近，我看到了越来越多的人提出使用我建议的方法，尤其是那些使用非Java语言进行编码的人。一般而言，代码审查涉及一些主观意见，有时还涉及偏好，样式等问题。
\ $ \ endgroup \ $
–senseiwu
14年4月6日在16:19
\ $ \ begingroup \ $
至少，代码的“开头” {{应该用换行符分隔，并正确缩进。结束符}}也应分开。内部的{}是一个代码块，应该像方法块或任何其他复合语句一样单独使用。
\ $ \ endgroup \ $
–rolfl
14年4月6日在16:23
#7 楼
一些注意事项：正如已接受的答案中正确指出的那样，该代码已被破坏。将
return true更改为return stack.empty()似乎可以解决此问题（免责声明：我没有运行代码）。 （n）”要求（想一想对于由大量偶数stack.push组成的输入会发生什么：每次按入都会增加堆栈）。因此，我将使用单个辅助字符串'{'数组（而不是stack对象）而不是char[]对象作为堆栈，并在其中建立索引。这足以完成工作，往往会使代码更简单，并且速度明显更快（尤其是因为我从这个答案中学到的str.length()/2是stack）。 n）”的要求，但它的等价C的正则表达式将不会正好相反，因为synchronized为O（n），因此语句为O（n2）。我建议在输入时将变量for (int i = 0; i < str.length(); i++)设置为strlen()，这可能会稍微加快速度，澄清代码并略微缩短代码，在任何情况下都不会造成太大损害。字符串是完全可以接受的。从问题的陈述中还不清楚，
n中的6个字符以外的其他任何字符都不能被禁止使用，尤其是空格。改变1后，测试
str.length()变得多余了，我会说不需要（独立于上一项）。我认为添加
{}[]()为(str.length() % 2) != 0的测试并不有用，因为在这种情况下str会抛出异常，对我来说很好。不过，这在C语言中还是不错的样式。评论
\ $ \ begingroup \ $
1）好的一点是Stack.push（）可能需要比O（1）时间更长的时间。谨慎地调用Stack.ensureCapacity（）以避免必须扩展堆栈的任何可能的代价。您也可以使用char []数组。字符串在Java中是不可变的，因此不合适。
\ $ \ endgroup \ $
– 200_success
2014年4月2日在10:17
\ $ \ begingroup \ $
@ 200_success：非常正确！解决它。您猜对了，我不是一个真正的Java程序员（我主要使用智能卡中使用的Java Card 2方言，在这种变体中，变量不能为int，我们只有简称）
\ $ \ endgroup \ $
– fgrieu
2014年4月2日在10:32
\ $ \ begingroup \ $
我会反对测试null字符串，因为如果您知道将抛出NullPointerException而不是进行期望异常的测试，那么我会反对。如果由于某种原因发生了变化，并且不再抛出异常，您将知道这一点！
\ $ \ endgroup \ $
–马克·安德烈（Marc-Andre）
2014年4月2日，12：56
评论
最佳实践：1）使用Snobol（其中大多数程序都简化为BAL x，其中x是要检查平衡的字符串）。您的代码是否为“ [[]]”返回false？
@konijn是的。
为什么不平衡一个空字符串？
我不知道为什么没人指出，但是输入（A + B）+（C-D）会失败