基于栈的C++函数实现：正确测试语言L={a^(n-1)b^n}的疑问

首先咱们得先明确这个语言的核心规则：所有的'a'必须出现在所有的'b'之前，并且'b'的总数恰好比'a'的总数多1。这就意味着像aba、bababa这种交错出现a和b的字符串，从根本上就不符合这个语言的结构，咱们的函数第一步就要把这种情况拦下来。

核心思路 #

用栈来跟踪'a'的数量，同时要严格保证：一旦遇到第一个'b'之后，就不能再出现任何'a'了。具体步骤如下：

• 遍历字符串的每个字符：
  1. 遇到'a'时：如果还没碰到过'b'，就把'a'压入栈；如果已经碰到过'b'，直接判定为非法（因为a不能出现在b后面）。
  2. 遇到'b'时：如果栈里还有'a'，就弹出一个'a'（相当于用一个b抵消一个a）；如果栈已经空了，就记录这个额外的b（因为最终需要恰好剩下1个这样的b）。
• 遍历结束后，需要满足两个条件才合法：
  • 栈必须是空的（所有的a都被b抵消完了）。
  • 额外记录的b的数量恰好是1（因为总b数 = a数 + 1，抵消a数的b后，剩下1个）。
  • 另外，空字符串直接非法，因为这个语言的最小合法串是b（n=1的情况）。

C++代码实现 #

#include <iostream>
#include <stack>
#include <string>

bool isInLanguage(const std::string& s) {
    std::stack<char> aStack;
    bool encounteredB = false;
    int extraBCount = 0;

    for (char c : s) {
        if (c == 'a') {
            // 如果已经遇到过b，再出现a直接非法
            if (encounteredB) {
                return false;
            }
            aStack.push(c);
        } else if (c == 'b') {
            encounteredB = true;
            if (!aStack.empty()) {
                // 用b抵消一个a
                aStack.pop();
            } else {
                // 栈空了，记录额外的b
                extraBCount++;
            }
        } else {
            // 遇到非a非b的字符，直接非法
            return false;
        }
    }

    // 最终条件：栈空，且额外的b恰好是1，同时字符串不能是空串
    return aStack.empty() && extraBCount == 1 && !s.empty();
}

// 测试用例
int main() {
    // 合法用例
    std::cout << std::boolalpha;
    std::cout << "b: " << isInLanguage("b") << std::endl;          // true
    std::cout << "abb: " << isInLanguage("abb") << std::endl;      // true
    std::cout << "aabbb: " << isInLanguage("aabbb") << std::endl;  // true

    // 非法用例
    std::cout << "aba: " << isInLanguage("aba") << std::endl;      // false
    std::cout << "bababa: " << isInLanguage("bababa") << std::endl;// false
    std::cout << "abababa: " << isInLanguage("abababa") << std::endl;// false
    std::cout << "aaab: " << isInLanguage("aaab") << std::endl;    // false（b数量不够）
    std::cout << "bb: " << isInLanguage("bb") << std::endl;        // false（没有a，额外b是2）
    std::cout << "aaa: " << isInLanguage("aaa") << std::endl;      // false（没有b）
    std::cout << "\"\": " << isInLanguage("") << std::endl;         // false

    return 0;
}

代码解释 #

• encounteredB变量用来标记是否已经开始处理b，一旦为true，再遇到a直接返回false，完美解决了交错字符串的问题。
• extraBCount用来统计栈空之后遇到的b的数量，最终必须等于1，保证b的总数比a多1。
• 额外处理了非a非b的字符，避免无效输入干扰结果。

这个实现可以正确处理你担心的交错格式字符串，比如aba在遍历到第三个字符'a'时，因为已经遇到过'b'，直接返回false；bababa第一个字符就是'b'，encounteredB变为true，后续遇到'a'都会直接返回false。

内容的提问来源于stack exchange，提问作者Erin Murphy