我有编程面试,其中包括3名面试官,每人45分钟。虽然前两位采访者给了我2-3个简短的编码问题(即反向链接列表,使用rand(5)实现rand(7)等)第三位采访者使用整个时间段来解决单个问题:
您将获得表示正确形成的字符串和带括号的布尔表达式,其中包含字符T,F,&,|,!,(,)空格。 T代表True,F代表False,&代表逻辑AND,|对于逻辑OR,!否定。并且优先于|。任何这些字符后跟输入字符串中的空格。我是要评估表达式的值并打印它(输出应该是T或F)。示例:输入:! (T | F&F)输出:F
我尝试实现Shunting Yard算法的变体来解决问题(以后缀形式转换输入,然后评估后缀表达式),但未能在给定的时间范围内正确编码,所以我最终用伪代码和单词解释我的内容通缉。
我的招聘人员说,前两位面试官给了我“HIRE”,而第三位面试官给了我“NO HIRE”,由于最终的决定是“合乎逻辑的”,他感谢我的时间。
我的问题:你认为这个问题适合于大约在白板上的代码。 40分钟?对我来说,似乎很多代码都是为了这么短的时间段和白板的尺寸。是否有比使用调车码算法更短的方法来解决这个问题?
好吧,一旦你对解析器有一些经验,postfix算法就很简单了。 1.从左到右评估每个char:如果是操作数,则按下堆栈。如果它的运算符弹出A,然后弹出B然后将B操作数A推入堆栈。堆栈上的最后一项将是结果。如果没有或多于一个意味着你做错了(假设后缀符号有效)。
Infix到postfix也很简单。话虽如此,如果您不了解算法,我认为这不是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();
}
在你的情况下,为了使它工作(使用该片段)你首先必须解析表达式并用类似字母的东西替换像“!”,“|”,“^”等特殊字符,或者在你的字母中使用整数字符值如果是案件。