Очередь, дающая ошибочные данные

Question

Итак, я пытаюсь использовать очередь для разбора некоторого ввода, превращая префиксные математические выражения в математические выражения infix с круглыми скобками. Например: +++ 12 20 3 4 превращается в (((12 + 20) +3) +4). По большей части мой алгоритм работает, за исключением одной конкретной вещи. Когда цифры больше двух цифр, выход становится странным. Я приведу несколько примеров вместо того, чтобы пытаться объяснить.

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)+() 

Надеюсь, это достаточно примеров, если вам нужно больше, просто спросите.

Я использую GCC 4.2 в XCode на Mac OSX 10.6.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 там, так утечка памяти.