gpt4 book ai didi

boolean - 评估 boolean 表达式值的算法

转载 作者:行者123 更新时间:2023-12-01 19:37:31 28 4
gpt4 key购买 nike

我参加了编程面试,由 3 名面试官组成,每人 45 分钟。虽然前两位面试官给了我 2-3 个简短的编码问题(即反向链表、使用 rand(5) 实现 rand(7) 等),但第三位面试官使用了整个时间段来回答单个问题:

You are given string representing correctly formed and parenthesized boolean expression consisting of characters T, F, &, |, !, (, ) an spaces. T stands for True, F for False, & for logical AND, | for logical OR, ! for negate. & has greater priority than |. Any of these chars is followed by a space in input string. I was to evaluate value of expression and print it (output should be T or F). Example: Input: ! ( T | F & F ) Output: F

我尝试实现调车场算法的变体来解决问题(将输入转换为后缀形式,然后计算后缀表达式),但未能在给定的时间范围内正确编码,所以我最终用伪代码进行了解释和说出我想要的。

我的招聘人员说前两位面试官给了我“聘用”,而第三位面试官给了我“不聘用”,由于最终的决定是“逻辑与”,他感谢我抽出时间。

我的问题:您认为这个问题适合在白板上编写大约 10 分钟的代码吗? 40分钟?对我来说,对于如此短的时间段和白板尺寸来说,代码似乎太多了。对于这个问题,是否有比使用调车场算法更短的方法?

最佳答案

好吧,一旦您对解析器有了一定的经验,后缀算法就非常简单了。1. 从左到右评估每个字符:如果是操作数,则压入堆栈。如果它的操作符,pop A,然后pop B,然后将B操作数A压入堆栈。堆栈上的最后一项将是结果。如果没有或多个则意味着您做错了(假设后缀表示法有效)。

中缀到后缀也很简单。话虽如此,如果您不了解算法,我认为 40 分钟的任务并不合适。这是我在某个阶段编写的 boolean 后缀评估方法(也使用 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();
}

在您的情况下,要使其正常工作(使用该片段),您首先必须解析表达式并将特殊字符(如“!”、“|”、“^”等)替换为简单的字母或仅使用整数字符在你的 if 案例中的值(value)。

关于boolean - 评估 boolean 表达式值的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16762057/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com