队列给出错误的数据

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在那里，所以泄漏的内存。