c++ - 分流场算法中缀到前缀实现

Question

我已经成功地在 C++ 中实现了分流场算法，将中缀表达式转换为后缀表达式 (RPN)。我需要修改我的算法以返回前缀（抛光）表达式，但我不知道如何。

void Prefix::fromInfix()
{
//The stack contain the operators
std::stack<std::string> pile;
//This is the output
std::vector<std::string> sortie;
//The input is the std::vector<std::string> _expression

pile.push("(");
_expression.push_back(")");

for (auto iter = _expression.begin(); iter != _expression.end(); iter++)
{
    //statOperator detect if the token is an operator and the priority of the operator.
    short op = statOperator(*iter);
    if (*iter == "(")
        pile.push(*iter);
    else if (*iter == ")")
    {
        while (pile.top() != "(")
        {
            sortie.push_back(pile.top());
            pile.pop();
        }
        pile.pop();
    }
    else if (op)
    {
        while (!pile.empty())
        {
            short op2 = statOperator(pile.top());
            //if op2 is is have the priority and isn't a parenthesis.
            if (op <= op2 && op2 != 3)
            {
                sortie.push_back(pile.top());
                pile.pop();
            }
            else
                break;
        }
        pile.push(*iter);
    }
    else
        sortie.push_back(*iter);
}
_expression = sortie;
}

Answer 1

我只需要从右到左读取输入。

for (auto iter = _expression.rbegin(); iter != _expression.rend(); iter++)

完全颠倒括号的作用。

_expression.insert(_expression.begin(), "(");
pile.push(")");

并在循环中。

if (*iter == ")")
    pile.push(*iter);
else if (*iter == "(")
{
    while (pile.top() != ")")
    {
        sortie.push(pile.top());
        pile.pop();
    }
    pile.pop();
}

并反转输出（我使用了堆栈）。

while (!sortie.empty())
{
    _expression.push_back(sortie.top());
    sortie.pop();
}