5. Как решаем

2010-01-22 15:02:30

Сычев С.В., Лебедев К.А. [sch@triz-ri.ru; askofen@mail.ru] » Всем

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;

}

Ответить Сообщение для всех [Нет ответов на это сообщение]

TRIZ-RI Group