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

Question

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";
}
};

该代码对于诸如"；我不明白这怎么可能。

1. (首先进入堆栈

2. (不是的地图(

所以它应该返回"；false"；。但事实并非如此。

Answer 1

关于您的表达式：

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

首先，除非s[0]是一个奇怪的量子变量，可以同时是三件事，否则该表达式永远不会为false。思考一些可能性：

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)}]

那么您的代码将不起作用，因为第一个CCD_ 4字符将被视为不匹配。要处理此问题，您需要对其进行修改以将其考虑在内。

例如：

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.
}

Answer 2

显然，ascii代码中的"("必须接近"("。

class Solution {
public:
bool isValid(string s) {
stack<char> st; st.push('');
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;
}