題目是Valid Parentheses,{、[、(三種括號必須由各自對應的括號填補,順序不能調
例如'([])' : value ; '([)]' : invaild ; ']' : invaild
原文網址:https://leetcode.com/problems/valid-parentheses/
下面是我的程式碼,遇到題目是 '}' 、 ']' 、 ')' 都會runtime error
(原文Line 836: Char 45: runtime error: pointer index expression with base 0x000000000000 overflowed to 0xffffffffffffffff (stl_iterator.h)SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/8/../../../../include/c++/8/bits/stl_iterator.h:845:45)
想請問是哪裡有錯誤或是我應該怎麼找錯誤,謝謝!
bool isValid(string s) {
vector<char> left;//store (, [, {
for( auto c : s ){
switch(c){
case('('):
case('['):
case('{'):
//store in left vector with order
left.push_back(c);
break;
//for the other cases
case(')'):
if(left.back() == '('){
left.pop_back();
//the last is matched, pop out
}
else if(left.back() != '(' || left.empty() ){
return false;
//if not match the last letter or no any letter
}
break; //end case
case(']'):
if(left.back() == '['){
left.pop_back();
}
else if(left.back() != '[' || left.empty() ){
return false;
}
break;
case('}'):
if(left.back() == '{'){
left.pop_back();
}
else if(left.back() != '{' || left.empty() ){
return false;
}
break;
default: //the string start and end with ' '
break;
}
}
if( !left.empty() )return false;//no any letter not match
return true;
}
當 vector 為 empty 時
left.pop_back 會造成錯誤
left.back 可能也會造成錯誤(我沒仔細測,不確定)
解決的方法是
在對 vector 做「讀/取動作」之前
先檢查是否是 empty
如果是 empty 表示符號不成對-->return false
如果不是 empty 才繼續往下做
簡單修補程式如下
#include <iostream>
#include <vector>
using namespace std;
bool isValid(string s) {
vector<char> left;//store (, [, {
for( auto c : s ){
switch(c){
case('('):
case('['):
case('{'):
//store in left vector with order
left.push_back(c);
break;
//for the other cases
case(')'):
if (left.empty()) { return false; }
if(left.back() == '('){
left.pop_back();
//the last is matched, pop out
}
else if(left.back() != '(' || left.empty() ){
return false;
//if not match the last letter or no any letter
}
break; //end case
case(']'):
if (left.empty()) { return false; }
if(left.back() == '['){
left.pop_back();
}
else if(left.back() != '[' || left.empty() ){
return false;
}
break;
case('}'):
if (left.empty()) { return false; }
if(left.back() == '{'){
left.pop_back();
}
else if(left.back() != '{' || left.empty() ){
return false;
}
break;
default: //the string start and end with ' '
break;
}
}
if( !left.empty() )return false;//no any letter not match
return true;
}
int main()
{
string s = "([])";
cout << s << " is " << isValid(s) << endl;
s = "([)]";
cout << s << " is " << isValid(s) << endl;
s = "}";
cout << s << " is " << isValid(s) << endl;
s = "[[[]]]]";
cout << s << " is " << isValid(s) << endl;
return 0;
}