評估布爾表達式的值的算法

我進行了面試程序設計，其中包括3名面試官，每人45分鐘。雖然前兩個面試官給了我2-3短編碼問題（即反向鏈接的列表，使用蘭特（5）等（7）實施蘭特）第三面試官用於單問題全時隙：評估布爾表達式的值的算法

您將得到的字符串代表正確形成和加括號由字符T，F，&，|，！，（，）和空格組成的布爾表達式。 T代表True，F代表假，&代表邏輯AND，|對於邏輯OR，！否定。 &的優先級高於|。所有這些字符後跟輸入字符串中的空格。我要評估表達式的值並打印它（輸出應該是T或F）。例如：輸入：！（T | F & F）輸出：F

我試圖執行調度場算法的變化來解決問題（轉動中後綴形式輸入，然後以評價後綴表達式），但未能編碼它在給定的時間範圍內，所以我最終以僞代碼和文字解釋我想要的內容。

我的招聘人員說，前兩名面試官給我「HIRE」，而第三位面試官給了我「不打招呼」，由於最終決定是「合乎邏輯的」，他感謝我的時間。

我的問題：你認爲這個問題適合於在白板上的代碼大約是： 40分鐘？對我來說，對於如此短的時間段和白板尺寸來說，似乎有很多代碼。有沒有比使用Shunting碼算法解決這個問題更短的方法？

來源

2013-05-26 Nikola Bogdanovic

那麼，一旦你有解析器postfix算法的一些經驗是相當簡單的。 1.從左到右評估每個char：（如果其操作數），則推入堆棧。如果它的操作符彈出A，然後彈出B然後將B操作數A推入堆棧。最後的項目將是結果。如果沒有或多於一個意味着你做錯了（假定後綴符號是有效的）。

infix to 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(); 
}

在你的情況下，使之工作（與片段），您必須先解析表達式和替換特殊字符像「！」，「|」，「^」等與簡單的像字母或只是在你的情況下使用整數字符值。

來源

2016-07-20 14:32:26

評估布爾表達式的值的算法

回答

相關問題