C++中的Shunting-yard算法

Question

我需要一个函数，它接收一个中缀字符串（如“3 + 4 * 9”），并将其转换为后缀形式（如“4 9 * 3 +”）。

到目前为止，我已经让它工作了，直到你在括号中添加另一个括号。我一整天都在解决这个问题，但无法弄清楚我做错了什么 - 也许有一个头脑清醒的人能够看到它？我感觉离成功很近！

谢谢！以下是代码：

    string ExpressionManager::infixToPostfix(string infixExpression)
    {
cout << "itop Testing : " << infixExpression << endl;
string posnums = "0123456789";
string posops = "+-*/%(){}[]";
string onlyops = "+-/%*";
string space = " ";
string openbra = "([{";
string closebra = ")]}";
stack <string> nums;
stack <string> ops;
string output = "";

//check to make sure expression is valid

if (!(isBalanced(infixExpression)))
{
    cout << "Infix Expression isn't balanced!" << endl;
    return "invalid";
}


for (int i=0; i<infixExpression.size(); i++)
{
    if ((posnums.find(infixExpression[i])!=string::npos) || (posops.find(infixExpression[i])!=string::npos) || (space.find(infixExpression[i])!=string::npos))
    {}

    else
    {
        cout << "Invalid character " << infixExpression[i] << " found." << endl;
        return "invalid";
    }
}


int numcount = 0;
int opcount = 0;
//Numbers vs. Operators
for (int i = 0; i < infixExpression.size(); i++)
{
    if (posnums.find(infixExpression[i]) != -1)
    {

        while(infixExpression[i] != ' ')
        {
            if (i == (infixExpression.size()-1))
                break;
            i++;
        }
        numcount++;
    }

    if (onlyops.find(infixExpression[i]) != -1)
    {
        opcount++;
    }
}


if (opcount == (numcount - 1))
{
}
else
{
    cout << "Bad operators to numbers ratio!" << endl;
    return "invalid";
}

//Get rid of proceeding whitespaces.
int safety = 0;
int net = infixExpression.size();

while (infixExpression[0] == ' ')
{
    infixExpression.erase(0,1);
    safety++;

    if (safety>=net)
        break;
}

//cout << "At this point, it is " << postfixExpression << endl;

//the fun part! Set up stacks

for (int i =0; i< infixExpression.size(); i++)
{
    cout << "It gets hung up on character " << infixExpression[i] << endl;
    if(openbra.find(infixExpression[i]) != -1)
    {

        string word = "";
        word += infixExpression[i];
        ops.push(word);

        cout << "Pushing onto stack: " << word << endl;
    }
    else if(closebra.find(infixExpression[i]) != -1)
    {
            cout << "contents of remaining ops stack: "<< endl;
            stack <string> temp;
            temp = ops;
                for (int j = 0; j < temp.size(); j++)
                {
                    cout << "\t" << temp.top() << endl;
                    temp.pop();
                }

        while (openbra.find(ops.top()) == -1)
        {


            output += " " + ops.top();
            cout << "Pushing from stack: " << ops.top() << endl;
            ops.pop();
        }

        cout << "Pushing from stack: " << ops.top() << endl;
        ops.pop();

    }

    else if (posnums.find(infixExpression[i]) != -1)
    {

        string word = "";
        while (infixExpression[i] != ' ')
        {
            word += infixExpression[i];
            i++;
            if (i== infixExpression.size())
                break;
        }
        output += " " + word;

    }

    else if (onlyops.find(infixExpression[i]) != -1)
    {

        if (ops.size() == 0)
        {
            string word = "";
        word += infixExpression[i];
        ops.push(word);
        }
        else
        {
        int o1p = 0;
        int o2p = 0;

        if ((infixExpression[i] == '+') || (infixExpression[i] == '-'))
            o1p = 0;
        else
            o1p = 1;

        if ((ops.top() == "+") || (ops.top() == "-"))
            o2p = 0;
        else
            o2p = 1;

        while ((ops.size() > 0) && (o1p <= o2p))
        {
            output += " " + ops.top();
            cout << "(odd) Pushing from stack: " << ops.top() << endl;

        if ((ops.top() == "+") || (ops.top() == "-"))
            o2p = 0;
        else
            o2p = 1;

        if (ops.size() > 0)
        {
            ops.pop();
        }
        else
        {
            break;
        }
        }

        string word = "";
        word += infixExpression[i];
        ops.push(word);
        }
    }

}

while (output[0] == ' ')
{
    output.erase(0,1);
}

return output;
    }

- user1311736

---

如果一开始就是递归下降而不是移位运算符，那该多好啊 :) - user166390

哇，移位-规约解析器闪回。我以为这样的问题在很久以前的大学就已经离开了我。 - WhozCraig

正确的输出应该是"3 4 9 * +"。当你稍后解析它时，你需要遍历所有元素直到找到第一个运算符。然后，你替换那个运算符和前面的两个操作数为该运算的结果，然后继续寻找下一个运算符。 - Atle

Answer 1

我的建议是直接查阅相关的维基页面，这些页面描述了以下内容：

1. Shunting Yard算法
2. 逆波兰表示法

我已经在Java和C++中实现了Shunting Yard算法，并发现维基页面非常好且是一个很好的帮助来源。它们提供了足够详细的信息，使您能够逐步在您喜欢的编程语言中实现该算法。

另一个建议是熟悉栈和队列的实际使用，因为这些在这些算法中随处可见。

请参阅此博客文章，其中包含所述Shunting Yard算法的C++和Java实现。

它还包含一个进一步的部分（正在进行中），如果您希望包括其他数学运算符（sin、cos、log等）以及更复杂的表达式和子表达式。

- AndyUK

Answer 2

我个人认为你需要更加努力地学习逆波兰算法。

因为你说输出结果应该是 "4 9 * 3 +"，但是根据我所了解的算法和栈操作，正确的输出应该是（像 "9 4 * 3 +"）

重要的问题是，在对数字和运算符进行分类后，根据设置的条件从运算符栈中弹出所有内容，并将其推入数字栈中。

- Jeff Bootsholz

Answer 3

这里是（最新版本的）解决方案。在某些步骤中，它使用Dijkstra的调度场算法（在traverse()成员函数的末尾，output_成员包含input_表达式的逆波兰表示形式，如果我们以正确的方式遍历它）。

- Tomilov Anatoliy