Алгоритм маневрового двора с обработкой унарного оператора НЕ в троичной строке

Question

Алгоритм маневрового двора с обработкой унарного оператора НЕ в троичной строке

В настоящее время я пишу передачу из инфикса в префикс строки троичной логики. В частности, в строке есть только три операнда T, F, U и три оператора AND, NOT, OR и скобки. Не имеет более высокого приоритета, чем AND, OR и AND OR имеют одинаковый приоритет. Вот мой код, изменяющийся от оригинального алгоритма маневрового двора, но перевод не верен для некоторого ввода

string Infix_To_Prefix(string expression){
string prefix_expression = "";
stack<char> char_stack;
unordered_map<char,int> Precendence;
Precendence['~'] = 2;
Precendence['|'] = 1;
Precendence['&'] = 1;

for(int i=0;i<expression.size();i++)
{
char token = expression[i];
if(isOperator(token))
{
while(!char_stack.empty() and isOperator(char_stack.top()))
{
if(Precendence[token] < Precendence[char_stack.top()])
{
prefix_expression+=char_stack.top();
char_stack.pop();
continue;
}
break;
}
char_stack.push(token);
}

else if(token == '(')
{
char_stack.push(token);
}
else if(token == ')')
{
while(!char_stack.empty() and char_stack.top() != '(')
{
prefix_expression+=char_stack.top();
char_stack.pop();
}
char_stack.pop();
}
else if(isOperand(token))
{
prefix_expression+=token;
}

}
while(!char_stack.empty())
{
prefix_expression+=char_stack.top();;
char_stack.pop();
}
return prefix_expression;
}

-3

algorithm c++

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

В своем коде вы проверяете приоритет:

if(Precendence[token] < Precendence[char_stack.top()])
{
prefix_expression+=char_stack.top();
char_stack.pop();
continue;
}

В программе, которую вы указали в комментарии, которая, конечно, не является оригинальной реализацией Shunting Yard, код

if ((isAssociative(token, LEFT_ASSOC) &&
cmpPrecedence(token, stack.peek()) <= 0) ||
(isAssociative(token, RIGHT_ASSOC) &&
cmpPrecedence(token, stack.peek()) < 0))
{
out.add(stack.pop());
continue;
}

Таким образом, ваш тест такой же, как и приведенный код в случае правоассоциативной операторы, и это то, что делает ваш код. Если вы хотите, чтобы ваши операторы были левоассоциативными, вам необходимо изменить < в <=, как в коде, который вы адаптируете.

Однако это не будет работать в случае унарных операторов, потому что унарные операторы должны быть правоассоциативными, по крайней мере, в упрощенном виде, обычно показанном в реализациях алгоритма маневрового двора.

Было бы точнее сказать, что унарный оператор всегда должен помещаться в стек независимо от предшествующего ему оператора; поскольку он не требует правого оператора, он не конкурирует с предыдущим оператором, только со следующим. Поэтому унарный оператор в качестве входящего токена должен иметь более высокий приоритет, чем любой оператор в стеке, хотя унарный оператор в стеке может иметь или не иметь более высокий приоритет, чем входящие операторные токены. Если унарный оператор является оператором с наивысшим приоритетом, то его правильная ассоциация будет иметь такой эффект. Так что я думаю, что он более понятен для унарных операторов специального случая, как вы уже делаете с круглыми скобками:

for (char token: expression)  {
if (token == '(' || token == '~')
char_stack.push(token);
else if (isOperator(token)) {
while (!char_stack.empty()
and isOperator(char_stack.top())
and Precendence[token] < Precendence[char_stack.top()]) {
prefix_expression+=char_stack.top();
char_stack.pop();
}
char_stack.push(token);
}
else if(token == ')') {
while(!char_stack.empty() and char_stack.top() != '(') {
prefix_expression+=char_stack.top();
char_stack.pop();
}
char_stack.pop();
}
else if(isOperand(token))
prefix_expression+=token;
}

Сходство между различными циклами, которые заполняют стеки, должно предполагать упрощение, которое обычно реализуется в синтаксических анализаторах с приоритетами операторов (примером которых является Shunting Yard).

0