Что я делаю неправильно? Реализация инфикса для постфикса с использованием стека

Question

Я пытаюсь написать конвертер выражений инфикса в постфикс, используя стек. По сути, это реализация алгоритма Shunting Yard, который можно найти в википедии.

/*
    This function returns the precedence of a presented token. To keep comparisons
    simple, the higher the return value, the higher the precedence. Not to be 
    confused with priority.

    From https://web.archive.org/web/20120822075917/http://en.literateprograms.org:80/Special:DownloadCode/Shunting_yard_algorithm_(Python)
*/
int precedence(string token)
{
    switch(token.at(0))
    {
        case '+':
            return 1;
        case '-':
            return 1;
        case '*':
            return 2;
        case '/':
          return 2;
        case '(':
            return 0;
        case ')':
            return 0;
    }

    return 0;
}

/*
  Returns true if the supplied token is an operator. 
*/
bool is_operator(const string& token)
{
    return token == "*" 
        || token == "/" 
        || token == "+" 
        || token == "-";
}

/*
  Returns true if the supplied token is an operand (not an operator). 
*/
bool is_operand(const string& token)
{
    return !is_operator(token) && (token != "(") && (token != ")");
}

void display(const vector<string>& v)
{
    for(unsigned int i=0; i<v.size(); i++)
    {
        cout << v[i] << " ";
    }
    cout << endl;
}

string associativity(const string& token)
{
    if(token == "*" || token == "+")
    {
        return "left";
    }
    else if(token == "/" || token =="-")
    {
        return "left";
    }

    return "?";
}

/*
    From wikipedia:

while there are tokens to be read:
    read a token.
    if the token is a number, then push it to the output queue.
    if the token is an operator, then:
        while (there is an operator at the top of the operator stack with
            greater precedence) or (the operator at the top of the operator stack has
                        equal precedence and
                        the operator is left associative) and
                      (the operator at the top of the stack is not a left bracket):
                pop operators from the operator stack, onto the output queue.
        push the read operator onto the operator stack.
    if the token is a left bracket (i.e. "("), then:
        push it onto the operator stack.
    if the token is a right bracket (i.e. ")"), then:
        while the operator at the top of the operator stack is not a left bracket:
            pop operators from the operator stack onto the output queue.
        pop the left bracket from the stack.
if there are no more tokens to read:
    while there are still operator tokens on the stack:
        pop the operator onto the output queue.
exit.
*/
vector<string> infix_to_postfix(const vector<string>& infix, bool& error)
{
    vector<string> postfix;
    stack<string> operators;

    for(string token : infix)
    {
        if(is_operand(token))
        {
            postfix.push_back(token);
        }
        if(is_operator(token))
        {
            while
            (
                (!operators.empty() && precedence(operators.peek()) > precedence(token))
            || (!operators.empty() && (precedence(operators.peek()) == precedence(token))   && (associativity(token) == "left") && (token != "("))
            )
            {
                string tk = operators.pop();
                if(tk != "(" && tk != ")")
                {
                    postfix.push_back(tk);
                }
            }
            operators.push(token);
        }
        if(token == "(")
        {
            operators.push(token);
        }
        if(token == ")")
        {
            while(!operators.empty() && operators.peek() != "(")
            {
                postfix.push_back(operators.pop());
            }
            if(!operators.empty())
            {
                operators.pop();
            }
        }
    }

    while(!operators.empty())
    {
        postfix.push_back(operators.pop());
    }

    return postfix; 
}

Я ожидаю, что этот код вернет правильное постфиксное выражение в виде вектора, содержащего соответствующие токены.

Следующая функция оценки возвращает странные числа для более длинного выражения, с которым я тестирую.

double evaluate(const vector<string>& postfix, bool& error)
{
    error = false;
    double result;
    stack<double> numbers;
    for(unsigned int i=0; i<postfix.size(); i++)
    {
        string token = postfix[i];

        if(is_operand(token))
        {
            numbers.push(stod(token));
        }
        else
        {
            double operand1 = numbers.pop();
            double operand2 = numbers.pop();
            switch(token.at(0))
            {
                case '+':
                    numbers.push(operand1 + operand2);
                    break;
                case '-':
                    numbers.push(operand1 - operand2);
                    break;
                case '*':
                    numbers.push(operand1 * operand2);
                    break;
                case '/':
                    numbers.push(operand1 / operand2);
                    break;
            }
        }
    }

Например, рассмотрим этот ввод и вывод:

Infix: ( 3 + 3 * 5 ) * 6 - 2 / 1 + 3 + 3 * 5 * ( 4 + 1 )
Postfix: 3 3 5 * + 6 * 2 1 / 3 3 5 4 1 + * * + + -
Result: -29.5

Google говорит, что его 184.

Обновление: я включил функцию ассоциативности из Википедии. Я также обновил результат выражения.

Обновление 2: включены комментарии, которые заставили этот код работать.

Answer 1

Очевидно, ваш вывод конверсии постфикса уже неверен. ( 3 + 3 * 5 ) должен был стать 3 3 5 * +не 3 3 + 5 *

       while
        (
            (!operators.empty() && precedence(token) <= precedence(operators.peek()))
            || (!operators.empty() && operators.peek() != "(")
        )

Эта часть неверна. Текст говорит (pred(operators.peek()) > pred(token)) || (pred(operators.peek()) == pred(token) && token != "("),

В результате вы всегда ошибочно извлекали оператор, когда он не был закрывающим, без учета приоритета оператора.

        double operand1 = numbers.pop();
        double operand2 = numbers.pop();

Эта часть также неверна. Операнд 2 находится выше в стеке. Переключите их.