алгоритм маневрового домика в префиксную реализацию

Question

Я успешно реализовал алгоритм маневрового двора в C++ для преобразования выражения infix в постфиксное выражение (RPN). Мне нужно изменить свой алгоритм, чтобы вернуть выражение префикса (polish), и я не знаю, как это сделать.

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(); 
}