C++中一个简单堆栈问题的意外答案

提问者：小点点

C++中一个简单堆栈问题的意外答案

class Solution {
public:
bool isValid(string s) {
    map<char , char> m;
    m[')'] = '(';
    m['}'] = '{';
    m[']'] = '[';
    
    stack<char> st;
    
    if(s[0] != '(' || s[0] != '{' || s[0] != '[')
        return "false";
    
    for(int i = 0; i<s.length(); i++)
    {
        if(s[i] == '(' || s[i]== '{' || s[i]== '[')
        {
            st.push(s[i]);
        }
        else if(st.top() == m[s[i]])
        {
            st.pop();
        }
        else if(st.top() != m[s[i]])
        {
            return "false";
        }

    }
    
    if(st.empty())
        return "true";
    else
        return "false";
}
};

代码对于像“(]”这样的基本示例是失败的，我不明白这是怎么可能的。

（首先进入堆栈

（地图不是用来的）

所以它应该返回“false”。但它返回true。

共2个答案

匿名用户

关于你的表达:

(s[0] != '(' || s[0] != '{' || s[0] != '[')

首先，除非S[0]是一个奇怪的量子变量，它可以同时包含三种东西，否则这个表达式永远不会是假的。想想一些可能性:

Character  != '('  != '{'  != '['  || all
---------  ------  ------  ------  ------
    (       false   true    true    true
    {       true    false   true    true
    [       true    true    false   true
    x       true    true    true    true

如您所见，每个字符表达式的计算值都为true。您可能应该使用&&而不是。

此外，从函数返回一个C样式字符串，该字符串是非零指针，在布尔上下文中将转换为true，如下所示:

#include <iostream>
bool returnT() { return "true"; }
bool returnF() { return "false"; }
int main() {
    std::cout << returnT() << '\n';
    std::cout << returnF() << '\n';
}

输出:

1
1

所以我更倾向于从这样的内容开始:

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        map<char, char> m;
        m[')'] = '('; m['}'] = '{'; m[']'] = '[';

        if (s[0] != '(' && s[0] != '{' && s[0] != '[') {
            return false;
        }

        for (int i = 0; i < s.length(); ++i) {
            if (s[i] == '(' || s[i]== '{' || s[i]== '[') {
                st.push(s[i]);
            } else if (st.top() == m[s[i]]) {
                st.pop();
            } else if (st.top() != m[s[i]]) {
               return false;
            }
        }

        return st.empty();
    }
};

但要注意一件事。如果您的有效输入字符被限制在六个括号内，您应该可以。

但是如果您希望允许不影响堆栈的其他字符，例如:

[14^{6+(2x3)}]

则您的代码将无法工作，因为第一个1字符将被视为不匹配。要处理这个问题，您需要修改它以将它们考虑在内。

例如:

for (int i = 0; i < s.length(); ++i) {
    if (s[i] == '(' || s[i]== '{' || s[i]== '[') {
        // Handle open brackets: store.

        st.push(s[i]);
    } else if (s[i] == ')' || s[i]== '}' || s[i]== ']') {
        // Handle close brackets: check.

        if (st.top() == m[s[i]]) {
            st.pop();
        } else {
            return false;
        }
    }

    // Anything else is just a "noise" character, ignore.
}

匿名用户

显然，在ascii代码中，“）”必须靠近“（”。

class Solution {
public:
    bool isValid(string s) {
        stack<char> st; st.push('\0');
        for (auto c : s) {
            if (isalpha(c)) continue;
            else if (c - st.top() <= 3 && c - st.top() > 0)
                st.pop();
            else
                st.push(c);
        }
        return st.size() == 1;
    }
};
int main() {
    Solution solu;
    cout << solu.isValid("[](){}") << endl;
    cout << solu.isValid(")(") << endl;
}

C++中一个简单堆栈问题的意外答案

共2个答案

相关问题