求布尔表达式值的算法

Question

我的节目采访由3名面试官组成，每次45分钟。前两位面试官给了我2-3个简短的编码问题(即反向链接列表，使用rand(5)等实现rand(7) )，第三位面试官用整段时间来回答单个问题：

给您一个字符串，该字符串表示由字符T、F、&、x、！、(、)一个空格组成的括号形布尔表达式。T代表真，F代表假，&表示逻辑，并表示逻辑或！！为了否定。&有更大的优先级。这些字符中的任何一个后面都是输入字符串中的空格。我要评估表达式的价值并打印出来(输出应该是T或F)。示例:输入：！(t=F&F)产出：

为了解决这个问题，我试图实现分流场算法的变异(以后缀形式转换输入，然后对后缀表达式进行评估)，但未能在给定的时间框架内对其进行适当的编码，因此我最终用伪代码和我想要的单词解释了问题。

我的招聘人员说，前两名面试官给了我“聘用”，而第三名面试官给了我“不录用”，因为最后的决定是“合乎逻辑和”的，他感谢我的时间。

我的问题是:你认为这个问题适合在白板上大约编码。40分钟？在我看来，这么短的时间间隔和白板尺寸的代码太多了。对于这个问题，是否有比使用调车场算法更短的方法？

Answer 1

嗯，一旦你对解析器有了一定的经验，后缀算法就很简单了。1.从左到右计算每个字符:如果操作数为操作数，则按堆栈。如果它的操作符pop A，然后pop B然后将B操作数A推到堆栈上。堆栈上的最后一项将是结果。如果没有或超过一个意味着您做错了(假设后缀符号是有效的)。

也非常简单。尽管如此，如果你不知道算法，我认为40分钟内这是一个不合适的任务。下面是我在某个阶段编写的布尔后缀评估方法(也使用Lambda )：

public static boolean evaluateBool(String s)
{
    Stack<Object> stack = new Stack<>();
    StringBuilder expression =new StringBuilder(s);
    expression.chars().forEach(ch->
    {
        if(ch=='0') stack.push(false);  
         else if(ch=='1') stack.push(true); 
          else if(ch=='A'||ch=='R'||ch=='X')
          {
              boolean op1 = (boolean) stack.pop();
              boolean op2 = (boolean) stack.pop();
              switch(ch)
              {
                case 'A' : stack.push(op2&&op1); break;
                case 'R' : stack.push(op2||op1); break;
                case 'X' : stack.push(op2^op1); break;
              }//endSwitch  
          }else 
              if(ch=='N')
                {
                  boolean op1 = (boolean) stack.pop();
                  stack.push(!op1);
                }//endIF
    });
    return (boolean) stack.pop();
}

在您的示例中，要使它正常工作(使用该代码段)，您首先必须解析表达式，并将特殊字符替换为"!“、”AC.26“、"^”等简单的字母，或者在您的if情况下只需使用整数字符值。