隊列給出錯誤的數據

Question

所以我試圖用一個隊列來解析一些輸入，將前綴數學表達式轉化爲帶括號的中綴數學表達式。例如：+++ 12 20 3 4變成（（（12 + 20）+3）+4）。大多數情況下，我的算法是有效的，除了一個特定的事情。當數字長於2位數時，輸出變得很奇怪。我會給你一些例子，而不是試圖解釋。

Examples: +++12 200 3 4 becomes (((12+3)+3)+4) 
+++12 2000 3 4 becomes (((12+20004)+3)+4) 
+++12 20005 3 4 becomes (((12+20004)+3)+4) 
+++12 20005 3 45 becomes (((12+20004)+3)+45) 
+++12 20005 3 456 becomes (((12+20004)+3)+() 

希望這就是足夠的例子，如果你需要更多，請問。

我在Mac OSX 10.6.2上的XCode中使用GCC 4.2。

這裏是做這個奇妙的東西代碼：

#include "EParse.h" 
#include <iostream> 
#include <iomanip> 


EParse::EParse(char* s) 
{ 
    this->s = s; 
    len = strlen(s); 
} 

void EParse::showParsed() 
{ 
    parse(s, 0, len, new std::queue< char* >(), new std::queue<char>()); 
} 

void EParse::parse(char* str, int beg, int len, std::queue< char* > *n, std::queue<char> *ex) 
{ 
    //ex is for mathematical expressions (+, -, etc.), n is for numbers 
    if(beg == len) 
    { 
     if(ex->size() > n->size()) 
     { 
      std::cout << "Malformed expression. Too many mathematical expressions to too few numbers." << std::endl; 
      std::cout << ex->size() << " mathematical expressions." << std::endl; 
      std::cout << n->size() << " number(s)." << std::endl; 
      return; 
     } 
     else 
     { 
      std::string *s = new std::string(); 
      output(n, ex, 0, s); 
      std::cout << s->c_str(); 
      return; 
     } 
    } 

    if(str[ beg ] == ' ' && beg != (len - 1)) 
     beg++; 
    if(num(str[ beg ])) 
    { 
     std::string *s = new std::string(); 
     getNum(s, str, beg, len); 
     //std::cout << s->c_str() << std::endl; 
     n->push(const_cast< char* >(s->c_str())); 
     delete s; 
     parse(str, beg, len, n, ex); 
    } 
    else if(mathexp(str[ beg ])) 
    { 
     ex->push(str[ beg ]); 
     parse(str, beg + 1, len, n, ex); 
    } 
} 

void EParse::getNum(std::string *s, char* str, int &beg, int len) 
{ 
    if(num(str[ beg ])) 
    { 
     char *t = new char[ 1 ]; 
     t[ 0 ] = str[ beg ]; 
     s->append(t); 
     beg += 1; 
     getNum(s, str, beg, len); 
    } 
} 

bool EParse::num(char c) 
{ 
    return c == '0' || c == '1' || c == '2' || c == '3' || c == '4' || 
    c == '5' || c == '6' || c == '7' || c == '8' || c == '9'; 
} 

bool EParse::mathexp(char c) 
{ 
    return c == '+' || c == '*' || c == '/' || c == '%' || c == '-'; 
} 

void EParse::output(std::queue< char* > *n, std::queue<char> *ex, int beg, std::string *str) 
{ 
    if(ex->empty()) 
    { 
     return; 
    } 

    char *t = new char[1]; 
    t[ 0 ] = ex->front(); 
    ex->pop(); 
    if(beg == 0) 
    { 
     str->insert(0, "("); 
     str->append(n->front()); 
     beg += 1 + strlen(n->front()); 
     n->pop(); 
     str->append(t); 
     str->append(n->front()); 
     str->append(")"); 
     beg += 2 + strlen(n->front()); 
     n->pop(); 
    }  
    else 
    { 
     str->insert(0, "("); 
     str->insert(beg, t); 
     str->insert(beg + 1, n->front()); 
     beg += 1 + strlen(n->front()); 
     str->insert(beg, ")"); 
     n->pop(); 
     beg++; 
    } 

    //ex->pop(); 
    output(n, ex, beg + 1, str); 
    //std::cout << str << std::endl; 
} 

如果您需要任何評論或究竟某些東西呢，請讓我知道解釋，我會檢查回到這裏相當頻繁今晚。

Answer 1

雖然我沒有確切的答案，你的問題，我也注意到這一點：

std::string *s = new std::string(); 
getNum(s, str, beg, len); 
//std::cout << s->c_str() << std::endl; 
n->push(const_cast< char* >(s->c_str())); 
delete s; 

問題有你正在推動s到隊列中，那麼你將其刪除。然後，隊列將引用一個不再有效的字符串值，這可能會導致您正在描述的錯誤。

爲了讓生活變得更輕鬆爲你，我會建議您更改隊列類型：

std::queue<std::string> 

然後你可以把和彈出整個std::string！而非指向它們的數據：

n->push(s); 

請注意，您必須將例程的API從char*更改爲std::string&，但您可以像修改char *一樣修改字符串的值。

Answer 2

順便提一句，您可能希望在上面的代碼中再次看看您的內存管理。很多new分配沒有delete在那裏，所以泄漏的內存。