iT邦幫忙

0

leetcode遇到的runtime error

題目是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;
}

1 個回答

0
海綿寶寶
iT邦大神 1 級 ‧ 2020-07-03 22:46:13

當 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;
}
silisili iT邦新手 5 級 ‧ 2020-07-03 23:08:50 檢舉

咦咦原來還有這樣子的!謝謝你!我找好久!

silisili iT邦新手 5 級 ‧ 2020-07-03 23:13:09 檢舉

後來做了修正,確實是沒確認empty的問題,感恩!

我要發表回答

立即登入回答