将（0＆（1 | 0）| 1）＆（0 | 1））等字符串转换为相应的真值

我在面试论坛上发现了这个问题，并认为这是一个有趣的问题。有什么简单的方法可以在C++中完成这个任务吗？例如，假设我们有函数声明：将（0＆（1 | 0）| 1）＆（0 | 1））等字符串转换为相应的真值

bool _transform(string x); 
/* x is a combination of (,), 0, 1, &, and | such that all expressions 
    start with a open and ending brace, and the function evaluates the 
    strings actual truth value 
*/

是否有任何有效且相对简单的方法来执行此操作？我想递归式地使用括号，但问题似乎很难。

来源

2014-04-09 user3340001

你能假设这个字符串是一个有效的表达式吗？我相当肯定这会改变实施相当多。 – Matthew

@Human对不起，不是澄清，但是，字符串将始终有效，错误检查不（可能）需要。为了简单起见，我只是说表达式总是正确的形式。 – user3340001

在表达式解析和评估中，这只是一个相当简单的练习，用逻辑运算符而不是算术运算。微不足道。查找“递归下降表达式解析”或Dijkstra调车码算法。 @Human这些算法可以检测到无效输入：它根本没有任何区别。 – EJP

这只是一个相当简单的练习，用表达式解析和评估，用逻辑运算符代替算术运算。微不足道。查找“递归下降表达式解析”或Dijkstra调车码算法。警告：后者有许多本土和其他近似等价物，其中大多数具有微妙的缺陷或非线性表现。使用源代码。

NB在标题的表达式的值是1.

来源

2014-04-09 03:57:22 EJP

的简单的解决这个问题是一个基于堆栈的解析器。 [递归下降会过度。]

For each character in the string 
    If it's a value (0 1) 
    If top of stack is an operator 
     Pop operator and value, evaluate 
    Push value on the stack 
    If it's an operator (&|) push it on the stack 
    If it's a left parenthesis push it on the stack 
    If it's a right parenthesis pop the value and the LP, push the value 
At end, pop the value off the stack.

更多的代码需要妥善处理错误，但你明白了。它也忽略了优先级。

这个概念很容易扩展到任何类型的算术表达式，但是您需要处理优先级以获得正确的答案。实际上，这将表达式从中缀转换为后缀符号，并即时评估。

来源

2014-04-09 04:04:44

这不太正确......用你当前的逻辑“1＆0” - >“push [1]”，“pop 2 values” - oops。 –

@TonyD：很高兴有人在看。自从我做了其中一个以来，已经有一段时间了查看修改。当优先支持不需要时（+1）， –

看起来很棒。 –

将（0＆（1 | 0）| 1）＆（0 | 1））等字符串转换为相应的真值

回答

相关问题