將（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））等字符串轉換爲相應的真值

回答

相關問題