c++ - 队列给出错误数据

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* 一样。