RRRRR - 54.147.203.105

Обсуждения-аналоги

Скрыть / Показать Сортировать по дате
2010-01-22 15:02:30
Сычев С.В., Лебедев К.А. » Всем

5. КАК РЕШАЕМ


Для наглядности приведем в таблице случай, когда все операции в выражениях имеют равный приоритет:


Выражение в инфиксной нотации

Выражение в нотации ПОЛИЗ

3 + 5

3 5 +

3 + 5 + 1

3 5 1 + +

3 + 5 + 1 + 2

3 5 1 2 + + +

 
Чтобы выполнить оба противоречивых требования, нам необходимо... снова представить идеальное решение.


Совершим первую попытку сделать это.


Идеально, если:


"Токены, записанные в привычной инфиксной нотации, попадая на вход алгоритма,

  • сами, не усложняя требований к программе, чудесным образом разделятся на "операнды" и "операции";
  • сами перестроятся так, что "операнды" сгруппируются раньше "операций";
  • "операции" сами "развернутся" и выстроятся в инверсном порядке так, что "будут последние первыми, и первые последними" (От Матфея 20:16).

Или, если образно:

  • "маленькие человечки токены", переступая порог, видят указатель:
    • "Операндам - сразу налево друг за другом (в очередь)",
    • "Операциям аналогично друг за другом, но направо (в отстойник стек)";
  • затем "операции" в обратном порядке, начиная с последнего вошедшего, выходят из стека и пристраиваются в хвост "операндам".


На языке программирования C++ алгоритм будет выглядеть таким образом:

TParser Input;

std::vector<TToken> Output;

std::vector<TToken> Operations;

TToken token;


while (Input.GetToken(&token))

{

switch (token.GetType())
{

case Operand:

      Output.push_back(token);

      break;

case Operation:

      Operations.push_back(token);

      break;

case EndOfSequence:

      {

while (!Operations.empty())

{

      Output.push_back(Operations.back());

      Operations.pop_back();


}

}

break;

}

}


Далее...




Яндекс.Метрика