Как создать математическое выражение из операторов и операндов в очереди

Я пытаюсь построить математическое выражение (включая скобки) с операторами и операндами, включенными в очередь.

Вот мой код:

string createExp (queue<char> q) {
    string s;
    string s1, s2;
    char c;

    while (!q.empty()) {

        c = q.front();

        if (c == 'x') {
            s += "x";
            q.pop();
        }

        else if (c == 'y') {
            s += "y";
            q.pop();
        }

        else if (c == 'a') {
            s += "avg(";
            q.pop();

            s1 = createExp(q);
            q.pop();
            s2 = createExp(q);
            q.pop();
            s += s1;
            s += ',';
            s += s2;
            s += ')';
        }

        else if (c == 's') {
            s += "sin(pi*";
            q.pop();
            op++;
        }
        else if (c == 'c') {
            s += "cos(pi*";
            q.pop();
            op++;
        }
        else {
            s += "*";
            q.pop();
        }
    }

    while (op > cp) {
        s += ")";
        cp++;
    }

    return (s);
}

Как видите, в случае среднего (avg) я пытаюсь рекурсивно вызвать функцию, чтобы получить следующую последовательность значений.

Например, если моя очередь содержит следующие значения:

s m a y x y

Выражение должно быть таким:

грех (пи * (ср (у, х) * у)

Но мой код возвращает эту последовательность:

sin (pi ** avg (yyx) yyxyyx

Не могли бы вы мне с этим помочь?

Большое тебе спасибо.


c++ mathematical-expressions
person elena.bdc    schedule 16.12.2015    source источник
comment
Вы пробовали отлаживать пошагово?   -  person sop    schedule 16.12.2015
comment
Или, по крайней мере, с более короткими / простыми входами?   -  person Ben Voigt    schedule 16.12.2015
comment
Где определены ваши op и cp? Они глобальные?   -  person sop    schedule 17.12.2015

Ответы (4)


arrow_upward
3
arrow_downward

Эта часть обработки avg(-,-) ужасно нарушена:

s1 = createExp(q);
q.pop();
s2 = createExp(q);
q.pop();

Вы передаете очередь по значению, что создает ее копию. Тогда вы не сможете узнать, сколько раз рекурсия появлялась в очереди. Но вы магическим образом предполагаете, что нужно удалить ровно один элемент. Что, если бы в одном из аргументов был вызов функции или оператор.

Что еще хуже, рекурсия обрабатывает всю оставшуюся часть очереди, а не только одно выражение.

person Ben Voigt    schedule 16.12.2015
comment
Итак, на ваш взгляд, как лучше всего решить эту проблему? Может быть, использовать рекурсию во всех функциях? - person elena.bdc; 16.12.2015
comment
Да, рекурсия, без цикла, и я бы передал очередь по ссылке, чтобы рекурсивные вызовы контролировали, сколько операндов удаляется. - person Ben Voigt; 16.12.2015
comment
А как могла быть эта функция? - person elena.bdc; 16.12.2015

arrow_upward
1
arrow_downward

** происходит как от m в строке, так и от того, что вы явно пишете sin(pi* в коде.

Кроме того, рекурсия в avg (при создании s1 кажется, что индексируется все выражение, так что вы получаете yyx). Вы должны убедиться, что он считывает из стека только одно полное выражение, а не все остальное. Это сложно, потому что вам нужно, например, различать avg(x,y) и avg(x+y,y*x).

person gt6989b    schedule 16.12.2015
comment
Это происходит из того, что m помещает * в строку вывода немедленно, вместо того, чтобы анализировать два операнда и помещать * между ними. - person Ben Voigt; 16.12.2015
comment
@BenVoigt да, разве я не писал то же самое? - person gt6989b; 16.12.2015

arrow_upward
0
arrow_downward

Я сделал небольшую модификацию вашего кода, и он отлично работает:

int cp = 0,  op = 0;

std::string createExp(std::queue< char >& q)
{
    std::string s;
    std::string s1, s2;
    char c;

    while (!q.empty())
    {
        c = q.front();

        if (c == 'x')
        {
            s += "x";
            q.pop();
        }
        else if (c == 'y')
        {
            s += "y";
            q.pop();
        }
        else if (c == 'a')
        {
            s += "avg(";
            q.pop();

            s1 = q.front(); // here
            q.pop();
            s2 = q.front(); // and here
            q.pop();
            s += s1;
            s += ',';
            s += s2;
            s += ')*';
        }
        else if (c == 's')
        {
            s += "sin(pi*";
            q.pop();
            op++;
        }
        else if (c == 'c')
        {
            s += "cos(pi*";
            q.pop();
            op++;
        }
        else
        {
//             s += "*";
            q.pop();
        }
    }

    while (op > cp)
    {
        s += ")";
        cp++;
    }

    return (s);
}

Но это будет работать, только если ваш оператор всегда *. Если вам нужны и другие операторы, вам понадобится более сложная вещь.

person sop    schedule 17.12.2015

arrow_upward
0
arrow_downward

Вот мое последнее рекурсивное решение:

int cp = 0,  op = 0;

string recursiveExp (queue<char>& q) {
    char e;

    if (!q.empty()) {
        e = q.front();
        if (e == 'x' || e == 'y') {
            q.pop();
            s += e;
        }

        else if (e == 's') {
            q.pop();
            s += "sin(pi*";
            op++;
            recursiveExp(q);
            s += ")";
            cp++;
        }

       else if (e == 'c') {
            q.pop();
            s += "cos(pi*";
            op++;
            recursiveExp(q);
            s += ")";
            cp++;
        }

        else if (e == 'a') {
            q.pop();
            s += "avg(";
            op++;
            recursiveExp(q);
            s += ",";
            recursiveExp(q);
            s += ")";
            cp++;
        }

        else if (e == 'm'){
            q.pop();
            s += "(";
            op++;
            recursiveExp(q);
            s += "*";
            recursiveExp(q);
            s += ")";
            cp++;
        }
    }
    return s;
}

Спасибо всем :)

person elena.bdc    schedule 17.12.2015