(，)，{，}，[ 和
]的字符串，确定输入字符串是否为输入字符串有效。要使输入字符串有效：
开括号必须用相同类型的括号闭合。
开括号必须以正确的顺序闭合。
请注意，空字符串被视为有效。
示例1：
输入：
() 输出：true
示例2：
输入：
()[]{} 输出：true
示例3：
输入：
(] 输出：false
示例4：
输入：
([)] 输出：false
示例5：
输入：
{[]} 输出：true
using System;
using System.Collections.Generic;
using Microsoft.VisualStudio.TestTools.UnitTesting;
namespace StackQuestions
{
[TestClass]
public class ValidParentheses
{
[TestMethod]
public void OpenOpenClosedClosedMixTest()
{
string input = "([)]";
bool result = IsValid(input);
Assert.IsFalse(result);
}
[TestMethod]
public void OnePairTest()
{
string input = "()";
bool result = IsValid(input);
Assert.IsTrue(result);
}
public bool IsValid(string s)
{
Stack<char> myStack = new Stack<char>();
foreach (var curr in s)
{
if (curr == '(')
{
myStack.Push(curr);
}
else if (curr == '[')
{
myStack.Push(curr);
}
else if (curr == '{')
{
myStack.Push(curr);
}
else if (curr == ')')
{
if (myStack.Count > 0)
{
var top = myStack.Pop();
if (top != '(')
{
return false;
}
}
else
{
return false;
}
}
else if (curr == ']')
{
if (myStack.Count > 0)
{
var top = myStack.Pop();
if (top != '[')
{
return false;
}
}
else
{
return false;
}
}
else if (curr == '}')
{
if (myStack.Count > 0)
{
var top = myStack.Pop();
if (top != '{')
{
return false;
}
}
else
{
return false;
}
}
}
return myStack.Count == 0;
}
}
}
请复习编码风格，因为这是一次面试，需要30分钟进行编码。
#1 楼
您可以在30分钟内完成工作，并且可以使用堆栈，因此这是一个不错的开始。我认为您正在编写过多（重复）的代码，如果使用switch -statement代替，它可能更容易阅读：public bool IsValidReview(string s)
{
Stack<char> endings = new Stack<char>();
foreach (var curr in s)
{
switch (curr)
{
case '(':
endings.Push(')');
break;
case '[':
endings.Push(']');
break;
case '{':
endings.Push('}');
break;
case ')':
case ']':
case '}':
if (endings.Count == 0 || endings.Pop() != curr)
return false;
break;
}
}
return endings.Count == 0;
}
在这里，将相应的结尾括号而不是开头的括号推入堆栈，这使得更容易检查结尾出现的时间。在上下文中更有意义。
评论
\ $ \ begingroup \ $
非常感谢，我想知道是否可以使用开关盒
\ $ \ endgroup \ $
–吉拉德
19年1月29日在10:52
\ $ \ begingroup \ $
@Gilad我认为词典非常适合。也检查我的答案。
\ $ \ endgroup \ $
– aloisdg移至codidact.com
19年1月29日在12:59
\ $ \ begingroup \ $
@Henrik Hansen代码审查刚刚使您对我的问题的回答更加困惑，这就是为什么我们获得这么多+1出色的工作！
\ $ \ endgroup \ $
–吉拉德
19年1月29日在20:54
\ $ \ begingroup \ $
@Voile我反对使用default作为包罗万象的内容来涵盖最后三种情况。在输入与任何预期情况都不匹配的情况下，应使用default，并且我希望无论如何都要将它们保留为不同的情况，以使代码的意图更加清晰。我同意对于无效的输入处理应该有一个通用的默认值。
\ $ \ endgroup \ $
– Abion47
19年1月29日在23:27
\ $ \ begingroup \ $
@solarflare您不需要在此级别中编写。我的代码通过了这次面试。这里的目标是尝试改善自己。如您所见，总是有一个空间。
\ $ \ endgroup \ $
–吉拉德
19年1月30日在5:19
#2 楼
这是@Henrik Hansen的跟进。取而代之的是，我将使用Dictionary<T, K>进行切换。词典有两个主要优点：提高可读性和抑制函数中的每个魔术字符串。public static readonly Dictionary<char, char> brackets = new Dictionary<char, char>
{
{'(', ')'},
{'[', ']'},
{'{', '}'}
};
public static bool IsValidReview(string input)
{
var endings = new Stack<char>();
foreach (var current in input)
{
if (brackets.ContainsKey(current))
{
endings.Push(brackets[current]);
}
else if (endings.Count == 0 || endings.Pop() != current)
{
return false;
}
}
return endings.Count == 0;
}
在线尝试！
评论
\ $ \ begingroup \ $
只需添加，您也可以使用Tuple数组。 var（opening，closeing）=（'（'，'）'）现在应该是有效的语法。这样一来，您可以多次关闭，反之亦然。它还使您可以使用C＃的有限结构来使其更加符合人体工程学。
\ $ \ endgroup \ $
–user29920
19年1月29日在22:25
\ $ \ begingroup \ $
我不同意使用字典可以提高可读性。很难说出这段代码应该做什么，特别是如果我还不知道它的目的的时候，而@HenrikHansen的答案非常清晰明了。 “魔术字符串抑制”是一个公平的观点，尽管在这种特殊情况下，魔术字符串（或更确切地说，字符）的用法是有限的，而且足够清楚，以至于我不必在生产代码中看到它。
\ $ \ endgroup \ $
– Abion47
19年1月29日在23:31
\ $ \ begingroup \ $
当然，开关解决方案具有魔力，但它的性能更快，性能更高（对象减少1个），可读性更高2。
\ $ \ endgroup \ $
–某人
19年1月30日，下午5:35
\ $ \ begingroup \ $
实际上，从技术上讲，魔术弦是非常罕见的……这些不是魔术弦。它们之所以如此，是很清楚的。另一方面，魔术数很常见
\ $ \ endgroup \ $
–某人
19年1月30日，下午5:35
\ $ \ begingroup \ $
@aloisdg您的解决方案的时间复杂度为O（n ^ 2），另一个解决方案的时间复杂度为O（n）。使用多键字典可以提高时间复杂度
\ $ \ endgroup \ $
– Node.JS
19年1月30日在6:06
#3 楼
要添加一些小问题：也许不适用于定时面试，但是有关公共成员的内联文档（
///）总是很不错，并且有助于解释否则模糊的IsValid方法名。如果遇到其他任何字符，我想抛出一个异常，因为该行为是未定义和未记录的。规范说，假设字符串中仅出现
()[]{}，这意味着任何不正确使用它的人（包括这样的字符）都应该被告知（也许他们假设它也处理<>？）。如果客户要依靠仅忽略此类字符的这种（未记录的）行为，则将来会有另一个未记录的“功能”要维护（否则会使客户不满意）。由于任何原因，该方法都不可行
static？除了概念上的好处之外，将其设置为静态将明确表明它不会与任何状态混淆，并且使其更易于使用。这是一组非常有限的测试用例：您根本不需要测试
{}。
评论
应该IsValidReview（“）（”）））;是真的吗？