在三元字符串中处理一元NOT运算符的调车场算法

Question

我目前正在编写三元逻辑字符串的Infix到Prefix传输。具体来说，字符串中只有三个操作数T、F、U和三个运算符and、NOT、OR和方括号。Not的优先级高于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;
}

Answer 1

在代码中，您可以检查优先级：

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

在你在评论中引用的程序中，它肯定不是最初的调车场实现，代码是

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

弹出堆栈的各种循环之间的相似性应该表明简化，这通常在操作员优先解析器中实现(调车场就是一个例子)。