我已经重构了我以前的一项家庭作业（主要是利用std::stack和一些C ++ 11），但仍然很难避免重复。

它读取文本文件中的字符按字符，并确定所有左括号和右括号（{}，()和[]）是否正确匹配。其他所有字符都将被忽略。

如果发现不匹配，将显示一条错误消息以指定特定字符，程序将终止。否则，最后会显示一条消息，表明它们都匹配。

以下是可能的错误类型：



丢失打开支架：

int main() { /*...*/ } ] // missing [



缺少关闭支架：

int main() { /*...*/     // missing }



打开支架用错误的闭合支架闭合：

int main() { /*...*/ ]   // should close with }



我的问题：


将每个打开的支架推入堆栈这样做的实际方法？我觉得我的方法不太实用，因为它涉及很多条件。找到闭合括号后，必须有某种方法来确定它们是否正确匹配。
std::map可以用作查找表来将打开和闭合支架相互关联吗？我觉得在这里进行DRY可能会有所帮助。
尽管将所有错误检查维护在一个函数中似乎很容易，但是否仍应将它们拆分为单独的函数？如果是这样，应该在消息中还是在消息中显示消息？
如果程序由于匹配错误而终止但没有文件错误，则返回main()是否有意义？我不确定是否应该返回EXIT_SUCCESS，即使如果无法打开文件也已经返回EXIT_FAILURE。

如果这个程序不太实用，我不介意采用完全不同的程序。如果您有更复杂的想法，请分享。我想以正确的方式进行处理。

#include <cstdlib>
#include <fstream>
#include <iostream>
#include <stack>
#include <string>

typedef std::stack<char> Brackets;

void pushOpeningBrackets(Brackets& opening, char ch)
{
    if (ch == '{')
        opening.push('{');
    else if (ch == '(')
        opening.push('(');
    else if (ch == '[')
        opening.push('[');
}

bool errorsFound(Brackets& stack, char openingBracket, char closingBracket)
{
    // unmatched?
    if (stack.empty())
    {
        std::cerr << "Unmatched " << closingBracket;
        return true;
    }

    char topBracket = stack.top();
    stack.pop();

    // not a match?
    if (topBracket != openingBracket)
    {
        if (topBracket == '{')
            std::cerr << "Expected } but found " << closingBracket;
        else if (topBracket == '(')
            std::cerr << "Expected ) but found " << closingBracket;
        else if (topBracket == '[')
            std::cerr << "Expected ] but found " << closingBracket;

        return true;
    }

    return false;
}

int main()
{   
    std::cout << "Enter a text file name: ";
    std::string filename;
    std::getline(std::cin, filename);

    std::ifstream inFile(filename.c_str(), std::ios::in);

    if (!inFile) return EXIT_FAILURE;

    Brackets stack;
    std::string fileLine;

    while (inFile >> fileLine)
    {
        for (char ch : fileLine)
        {
            pushOpeningBrackets(stack, ch);

            if (ch == '}')
            {
                if (errorsFound(stack, '{', '}'))
                {
                    return EXIT_SUCCESS;
                }
            }
            else if (ch == ')')
            {
                if (errorsFound(stack, '(', ')'))
                {
                    return EXIT_SUCCESS;
                }
            }
            else if (ch == ']')
            {
                if (errorsFound(stack, '[', ']'))
                {
                    return EXIT_SUCCESS;
                }
            }
        }
    }

    // checks for missing bracket or full match
    if (!stack.empty())
    {
        char topBracket = stack.top();
        stack.pop();

        if ('{' == topBracket)
            std::cerr << "Missing }";
        else if ('(' == topBracket)
            std::cerr << "Missing )";
        else if ('[' == topBracket)
            std::cerr << "Missing ]";
    }
    else
        std::cout << "All brackets match!";
}


评论

由于这是由“所有其他字符均被忽略”所覆盖的，所以我只想评论一下，在不需要匹配的情况下（例如，用引号引起来或在注释中），匹配方括号的语言会使用它们。这可能是一个不错的扩展。
至少必须处理字符串和char文字。请注意，由于文字的原因，您的代码几乎肯定无法验证自己。

#1 楼

代替... 

void pushOpeningBrackets(Brackets& opening, char ch)
{
    if (ch == '{')
        opening.push('{');
    else if (ch == '(')
        opening.push('(');
    else if (ch == '[')
        opening.push('[');
}


...使用... 

void pushOpeningBrackets(Brackets& opening, char ch)
{
    switch (ch)
    {
        case '{':
        case '(':
        case '[':
            opening.push(ch);
            break;
    }
}


或使用std:map ：

std::map<char,char> charmap;
charmap['('] = ')';
...etc...

void pushOpeningBrackets(Brackets& opening, char ch)
{
    if (charmap.find(ch) != charmap.end())
        opening.push(ch);
}


同样，代替... 

if (topBracket != openingBracket)
{
    if (topBracket == '{')
        std::cerr << "Expected } but found " << closingBracket;
    else if (topBracket == '(')
        std::cerr << "Expected ) but found " << closingBracket;
    else if (topBracket == '[')
        std::cerr << "Expected ] but found " << closingBracket;

    return true;
}




if (topBracket != openingBracket)
{
    char expected;
    switch (topBracket)
    {
        case '{': expected = '}'; break;
        case '(': expected = ')'; break;
        case '[': expected = ']'; break;
        default: ; // WHAT TO DO HERE?!
    }
    std::cerr << "Expected " << expected << " but found " << closingBracket;
    return true;
}


...或... 

if (topBracket != openingBracket)
{
    std::cerr << "Expected " << charmap[topBracket] << " but found " << closingBracket;
    return true;
}



在现有代码中，在三个不同的位置定义对：例如在这里... 

if (errorsFound(stack, '{', '}'))


...在这里... 

    if ('{' == topBracket)
        std::cerr << "Missing }";


...和在这里... 

    if (topBracket == '{')
        std::cerr << "Expected } but found " << closingBracket;


您可以通过以下方式解决此问题：编写子例程char getCloseOf(char) { ... }和/或使用std::map或类似容器在数据中定义它。


您尚未在源代码中实现转义字符串和注释。此外，正在解析的文本中的C ++宏可能会使它混乱，例如#define FOO a(



虽然在一个功能中维护所有错误检查似乎很容易，但是否仍应将它们拆分为单独的功能？如果是这样，应该在消息中还是在main（）中显示消息？


我不太喜欢您的子例程。例如，pushOpeningBrackets仅被调用一次，并且其实现很短（通过阅读其实现比通过阅读其名称更容易理解它）。因此，您最好将该代码内联而不是作为子例程使用，可能带有注释// push opening brackets。



如果程序从a终止，返回EXIT_SUCCESS是否有意义？匹配错误但不是文件错误？我不确定是否应该返回EXIT_FAILURE，即使它无法打开文件也是如此。


您可以记录几个返回代码，例如：


0：源语法分析-可以
1：源语法分析-BADLY
-2：无法语法分析源-内存错误


#2 楼

我将通过三项主要更改对其进行重写：




保持最小的main()并改善用户界面。

根据“单一责任原则”，将main()限制为仅使用适当的参数调用主函数是一个好主意。在这种情况下，功能可以非常清晰地拆分。

作为Unix / Linux用户，我希望看到遵循某些Unixy约定的工具：


从命令行上命名的文件中获取输入，如果没有命令行参数，则从标准输入获取输入。
成功后，保持沉默并返回0（除非您添加了对--verbose标志的支持，而我没有这样做）麻烦去实现）。

在此程序的上下文中，我将认为无法打开输入文件是要报告给std::cerr的错误条件，而定界符不匹配将是正常输出。报告给std::cout。 （要回答您的问题3，我只是走了一条简单的路线，并在遇到错误时将其打印出来。这可能不是最优雅的方法，但是它免除了将不匹配编码为某种表示形式的麻烦。当

回答有关程序退出状态的问题4：0表示成功； 2表示程序退出状态。除此之外，还没有通用的约定。


使用std::string::find_first_of()。

这样可以避免一个又一个字符的繁琐乏味。


将预期的结束定界符保留在堆栈中。

这似乎减少了代码中的冗余。这解决了您的问题1和2。此外，我还对其进行了增强以跟踪行号和列号，以帮助查找不匹配的位置。如果您跟踪每个推入堆栈的定界符的位置，则诊断可能会提供更多信息。

#include <cstdlib>
#include <cstring>
#include <fstream>
#include <iostream>
#include <stack>
#include <string>

bool bracketsMatch(std::istream &in) {
    std::stack<char> expectedDelimiters;
    int lineNum = 0;
    std::string line;
    while (std::getline(in, line)) {
        lineNum++;
        size_t pos = 0; 
        while (std::string::npos != (pos = line.find_first_of("(){}[]", pos))) {
            int colNum = pos + 1;
            switch (line[pos]) {
              case '(': expectedDelimiters.push(')'); break;
              case '{': expectedDelimiters.push('}'); break;
              case '[': expectedDelimiters.push(']'); break;

              case ']':
              case '}':
              case ')':
                if (expectedDelimiters.empty()) {
                    std::cout << "Mismatched " << line[pos]
                              << " at line " << lineNum << ", col " << colNum
                              << std::endl;
                    return false;
                }
                if (line[pos] != expectedDelimiters.top()) {
                    std::cout << "Expected " << expectedDelimiters.top()
                              << ", found " << line[pos]
                              << " at line " << lineNum << ", col " << colNum
                              << std::endl;
                    return false;
                }
                expectedDelimiters.pop();
            }
            pos = colNum;
        }
    }
    // Should check for a possible input error here, but I didn't bother.
    if (!expectedDelimiters.empty()) {
        std::cout << "Expected " << expectedDelimiters.top()
                  << " at end of file" << std::endl;
        return false;
    }
    return true;
}

int main(int argc, const char *argv[]) {
    // The command-line parsing below is a bit sloppy (no validation,
    // help message, or option handling, for example).
    std::ifstream f;
    std::istream &in = (argc > 1) ? (f.open(argv[1]), f) : std::cin;
    if (!in) {
        std::cerr << argv[0] << ": " << argv[1] << ": "
                  << std::strerror(errno) << std::endl;
        return 2;   // A rather arbitrary error code
    }
    return bracketsMatch(in) ? EXIT_SUCCESS : EXIT_FAILURE;
}


#3 楼

您正在寻找的技术称为“数据驱动”编程：

static char map[256]  = {0}; // init all the data to 0.

map['{']   = 1;
map['[']   = 1;
map['(']   = 1;
map['}']   = '{';
map[']']   = '[';
map[')']   = '(';

for(char ch: data) {
    char action = map[ch];
    if (action == 0) {
         /* do nothing */
    }
    else if (action == 1) {
         stack.push(ch);
    }
    else {
         if (stack.empty()) {
             // Error
         } else {
             char open = stack.top();
             stack.pop();
             if (open != action) {
                 // Error
             }
         }
     }
}
if (!stack.empty()) {
    // Error
}



将每个开口支架推入堆栈中是否是一种实用的方法？


是的


我觉得我的方法不太实用，因为它涉及很多条件。找到右方括号后，必须有某种方法来确定它们是否正确匹配。


是的，您正在做太多的编程，如果您的需求发生变化，这将涉及更改代码一点点。通过使用数据驱动的方法，您的代码将变得更加灵活，并且只需对用于驱动代码的数据结构进行少量修改，就可以使代码正常运行。


std::map会是有益的用作将开括号和闭括号彼此关联的查找表？我觉得在这里进行DRY可能会有所帮助。


Overkill。
但是需要一个数据结构。
我使用了一个字符数组来保存我的决策状态。如果使用的是unicode或其他较大的字符类型，则使用向量。决策集的大小很小，因此线性扫描也不会花费太多。对于较小的n，\ $ O（ln（n））+ K1 \ $可能大于\ $ O（n）+ K2 \ $。您的n为6。
我喜欢单一日志功能的概念。您可以在单个位置保持一致的格式化消息的方式。


如果是这样，应该在消息中还是在消息中显示消息？main()中？


您可以将消息移到资源文件中，以简化L10N和I18N。


如果程序由于匹配错误而终止但没有文件错误，则返回EXIT_SUCCESS是否有意义？我不确定是否应该返回EXIT_FAILURE，即使文件无法打开也已经返回EXIT_FAILURE。


考虑在UNIX环境中的用法。任何错误都应返回q4312079q，以便使用命令强制脚本正确停止（或不继续输入无效内容）。

评论

\ $ \ begingroup \ $
混合使用0、1，{，[和（虽然值确实可以工作，但感觉有些黑。
\ $ \ endgroup \ $
– 200_success
2014年1月31日上午9:22
\ $ \ begingroup \ $
hackish表示C。是。如果问题更复杂，那我就不会这样做。但是，在这样一个琐碎的问题上变得毫无意义。
\ $ \ endgroup \ $
–马丁·约克
2014年1月31日上午9:28
\ $ \ begingroup \ $
@LokiAstari：我只是再次看了一下，除了if（action == 0）以外，我几乎理解了它。有什么意义吗？它与任何预设的错误条件都不对应，也不是通过添加非括号字符触发的（这是我根据外观尝试过的）。
\ $ \ endgroup \ $
– Jamal♦
2014年4月26日在1:26


\ $ \ begingroup \ $
@Jamal：如果（action == 0）是默认操作。如果不是打开或关闭（所以是最常见的情况）。大多在文档中说“如果我们看不到任何预期的情况，那就什么也不做”
\ $ \ endgroup \ $
–马丁·约克
2014年4月26日在3:31
\ $ \ begingroup \ $
@AkshatAgarwal：将所有位置初始化为0；
\ $ \ endgroup \ $
–马丁·约克
16年5月29日在3:47

#4 楼

让我们回答您首先遇到的问题：


为此可以使用堆栈。您需要跟踪遇到的令牌的顺序，以LIFO方式删除它们-几乎是堆栈的定义。
std::map对于3个代币而言是多余的。我将它们存储起来，但是存储在一个（gasp！）普通堆栈分配的数组中。由于std::map的实现方式，其查找常数要比普通阵列高得多。当然，处理大量数据时，可以使用O(log n)而不是O(n)进行搜索，但是，交叉点很可能在几千中某个位置（取决于所有因素）。速度在这里并不是很重要（不是），但是搜索起来反而会更简单。
我认为在一个函数中具有错误功能是完全可以的。将事物拆分成单独的功能是一件好事，尽管如此简单，但我发现没有什么意义。实际上，在函数中再次输出错误是可以的-它具有此时所需的所有信息。如果改为在main中处理此问题，则必须找出一个返回值，该返回值要么为“这就是我所期望的，这是我发现的，但是有一个错误”，或者“一切正常”。
就我个人而言，如果一切都很好（一切都正确匹配），我认为应该返回EXIT_SUCESS，否则返回EXIT_FAILURE。考虑在某种管道中使用此方法，在该管道中文件必须经过一堆又一堆的检查-然后，您希望它在继续之前没有任何错误。传达一切的最佳方式是什么？使用EXIT_SUCCESS。

好吧，还有其他一些建议：

保留令牌列表（作为简单数组）：

constexpr char tokenList[] = {'{', '(', '['};


然后可以将pushOpeningBrackets更改为：

void pushOpeningBrackets(Brackets& opening, char ch)
{
    for(char tok : tokenList)
    {
        if(ch == tok) 
            opening.push(tok);
    }
}


这样做还有一个好处，就是如果您想添加另一个令牌，只需要将其添加到您的tokenList中，而不必添加另一个else if语句。

一个地方可以使用map（为简单起见）在errorsFound中，
，您需要关联的带有开括号的闭合大括号：

const std::map<char, char> closing = {{'{', '}'}, {'(', ')'}, {'[', ']'}};

bool errorsFound(Brackets& stack, char openingBracket, char closingBracket)
{
    if(stack.empty()) 
    {
        std::cout << "Unmatched " << closingBracket;
        return true;
    }

    char topBracket = stack.top();
    stack.pop();

    if(topBracket != openingBracket) {
        auto expectedClosing = closing.find(topBracket);
        std::cout << "Expected " << expectedClosing->second << " but found "
                  << closingBracket;
        return true;
    }

    return false;
}


也可以用来简化检查main的底部以类似的方式。

#5 楼

您的typedef 

typedef std::stack<char> Brackets;


…对我来说似乎很尴尬。

如果没有typedef，则您的堆栈可能已声明为

std::stack<char> brackets;


但是，对于typedef，最终却是Brackets stack，不幸的是倒退了，因为我希望stack是类型而不是变量名。

评论

\ $ \ begingroup \ $
是的，我对命名有点草率。我会回去修复其中的一些问题。
\ $ \ endgroup \ $
– Jamal♦
2014年1月31日上午8:35

#6 楼

首先，要使其真正有用，请将您解析的原始行添加到混合文件中。这样，用户不必手动手动扫描可能很大的文档。


我想说的是，您应该将错误检查放到一个函数中。我也强烈建议保持跟踪错误的位置。手动解析一个很长的行以解决一个微小的错误，没有什么比这更有趣了，就像解析一个特定行的巨大文件一样。

typedef std::pair<std::string, size_t> lineNumber
std::vector<lineNumber> readFile(const std::string &fileName) {
    std::ifstream fileStream(fileName.c_str(), std::ios::in);
    if (fileStream.fail()) {
        throw std::runtime_error("Cannot open file " + fileName + "\n");
    }

    std::vector<lineNumber> lines;
    std::string temp;
    while (getline(fileStream, temp)) {
        lines.push_back(std::make_pair(temp, lines.size()+1));
    }

    if (lines.empty()) {
        throw std::runtime_error("Empty file " + fileName + "\n");
    }
    fileStream.close();

    return lines;
}



现在您可以添加自定义异常来告诉您的用户代码有什么问题，并使错误警告标准化。显然这可能是一个过大的杀伤力，但是我将其用于我编写的解析器中，自然会增加不同错误的数量。 

void checkBrackets(const std::vector<lineNumber> &lines) {
    std::map<char, char> bracketPairs= {std::make_pair(')', '('),
                                        std::make_pair(']', '['),
                                        std::make_pair('}', '{')};
    std::stack<std::pair<char, size_t>> brackets;
    for (lineNumber line : lines) {
        for (auto it = line.first.begin(); it != line.first.end(); ++it) {
            switch (*it) {
            case '(':
            case '[':
            case '{':
                brackets.push(std::make_pair(*it, std::distance(line.first.begin(), it)));
                break;
            case ')':
            case ']':
            case '}':
                if (brackets.empty()) {
                    throw bracketException(MISSING_OPENING_BRACKET, line, 
                                           std::distance(line.first.begin(), it));
                } else if (brackets.top().first != bracketPairs[*it]) {
                    throw bracketException(MISSING_CLOSING_BRACKET, line,
                                             brackets.top().second);
                }
                brackets.pop();
                break;
            default:
                continue;
            }
        }
        if (!brackets.empty()) {
            throw bracketException(MISSING_CLOSING_BRACKET, line,
                                     brackets.top().second);
        }
    }
}