c++ - 中缀的前缀不能完全给出正确的结果

Question

我有一个非常简单的算法，它接受一个 RPN 字符串并将其转换为中缀:

   for(unsigned int i = 0; i < tokens.size(); i++)
    {
        token = tokens[i];

        if(!isOperator(token))
        {
            stack.push(token);
        }
        else
        {
            //need at least 2 values
            string a = stack.pop();
            string b = stack.pop();
            string expr = "(" + a + token + b + ")";
            stack.push(expr);
        }
    }

string converted = stack.pop();

但是，我的 RPN 字符串中也有指数。

这是一个示例 RPN:

3 4 2 * 1 5 - 2 3 ^ ^ / +

中缀看起来像:

(3+((4*2)/((1-5)^(2^3))))

这是正确的。

我修改了它以使用前缀:

for(int i = tokens.size() - 1; i >= 0; i--)
    {
        token = tokens[i];

        if(!isOperator(token))
        {
            stack.push(token);
        }
        else
        {
            //need at least 2 values
            string a = stack.pop();
            string b = stack.pop();
            string expr = "(" + a + token + b + ")";
            stack.push(expr);
        }
    }

但它给出的结果略有不同:

给定前缀:

+ 3 * 4 / 2 ^ ^ - 1 5 2 3

我得到了中缀:

(3+(4*(2/(((1-5)^2)^3))))

这有点不对。我不确定为什么 4 乘以表达式的其他部分而不是 2。

谁能告诉我哪里可能出了问题？

谢谢

Answer 1

您的算法是正确的。您得到错误的答案是因为您的测试输入错误。

相应中缀的前缀应该是

+ 3 / * 4 2 ^ - 1 5 ^ 2 3

关于prefix notation的信息(波兰表示法)I refered to.