我究竟做错了什么？使用堆栈实现中缀到后缀

Question

我正在尝试使用堆栈编写中缀到后缀表达式转换器。基本上，它是维基百科上的 Shunting Yard algorithm 的实现。

/*
    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; 
}

我希望此代码 return 一个有效的后缀表达式，其形式为包含相关标记的向量。

下面的计算函数 return 是我正在测试的更长表达式的奇怪数字。

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。

更新： 我包含了 wikipedia 中的关联函数。我还更新了表达式结果。

更新二： 合并了使此代码起作用的注释。

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 是堆栈中较高的操作数。交换他们。

我究竟做错了什么？使用堆栈实现中缀到后缀

What am I doing wrong? Implementing infix to postfix using a stack

shunting-yard

c++11